凸优化理论与应用课件.ppt

《凸优化理论与应用课件.ppt》由会员分享，可在线阅读，更多相关《凸优化理论与应用课件.ppt（217页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、可编辑可编辑1 1凸优化理论与应用凸优化理论与应用庄 伯 金B可编辑可编辑2 2优化理论概述n什么是优化问题？什么是优化问题？Objective functionConstraint functions可编辑可编辑3 3几类经典的优化问题n线性规划问题线性规划问题n最小二乘问题最小二乘问题n凸优化问题凸优化问题凸优化问题理论上有凸优化问题理论上有有效的方法进行求解！有效的方法进行求解！可编辑可编辑4 4本课程的主要内容n理论部分理论部分n凸集和凸函数凸集和凸函数n凸优化问题凸优化问题n对偶问题对偶问题n应用部分应用部分n逼近与拟合逼近与拟合n统计估计统计估计n几何问题几何问题n算法部分算法部分

2、n非约束优化方法非约束优化方法n等式约束优化方法等式约束优化方法n内点法内点法可编辑可编辑5 5n熟悉了解凸优化理论的基本原理和基本方法；熟悉了解凸优化理论的基本原理和基本方法；n掌握实际问题转化为凸优化问题的基本方法；掌握实际问题转化为凸优化问题的基本方法；n掌握最优化问题的经典算法。掌握最优化问题的经典算法。课程要求可编辑可编辑6 6参考书目nStephen Boyd and Lieven Vandenberghe,“Convex Optimization”,Cambridge University Press.n袁亚湘、孙文瑜，袁亚湘、孙文瑜，“最优化理论与方法最优化理论与方法”，科学出

3、版，科学出版社，社，1999。可编辑可编辑7 7凸优化理论与应用凸优化理论与应用第一章第一章凸集凸集可编辑可编辑8 8仿射集(Affine sets)n直线的表示：直线的表示：n线段的表示：线段的表示：可编辑可编辑9 9仿射集(Affine sets)n仿射集的定义：过集合仿射集的定义：过集合C内任意两点的直线均在集合内任意两点的直线均在集合C内，则称集合内，则称集合C为仿射集。为仿射集。n仿射集的例：直线、平面、超平面仿射集的例：直线、平面、超平面可编辑可编辑1010仿射集n仿射包：包含集合仿射包：包含集合C的最小的仿射集。的最小的仿射集。n仿射维数：仿射包的维数。仿射维数：仿射包的维数。可

4、编辑可编辑1111仿射集n内点（内点（interior）：）：n相对内点（相对内点（relative interior）：）：可编辑可编辑1212凸集(Convex Sets)n凸集的定义：集合凸集的定义：集合C内任意两点间的线段均在集合内任意两点间的线段均在集合C内，则称集合内，则称集合C为凸集。为凸集。可编辑可编辑1313凸集n凸包的定义：包含集合凸包的定义：包含集合C的最小的凸集。的最小的凸集。可编辑可编辑1414锥(Cones)n锥的定义：锥的定义：n凸锥的定义：集合凸锥的定义：集合C既是凸集又是锥。既是凸集又是锥。n锥包的定义：集合锥包的定义：集合C内点的所有锥组合。内点的所有锥组合

5、。可编辑可编辑1515超平面和半空间n超平面超平面(hyperplane)：n半空间半空间(Halfspace)：可编辑可编辑1616欧氏球和椭球n欧氏球欧氏球(euclidean ball):n椭球椭球(ellipsoid):可编辑可编辑1717范数球和范数锥n范数范数(norm)：n范数球范数球(norm ball)：n范数锥范数锥(norm cone)：可编辑可编辑1818多面体(Polyhedra)n多面体：多面体：n单纯形单纯形(simplex)：可编辑可编辑1919半正定锥(Positive semidefinite cone)nn阶对称矩阵集：阶对称矩阵集：nn阶半正定矩阵集：阶

6、半正定矩阵集：nn阶正定矩阵集：阶正定矩阵集：n阶半正定矩阵集为阶半正定矩阵集为凸锥！凸锥！可编辑可编辑2020保持凸性的运算n集合交运算集合交运算n仿射变换仿射变换n透视透视/投射函数投射函数(perspective function)可编辑可编辑2121保持凸性的运算n线性分式函数线性分式函数(linear-fractional function)可编辑可编辑2222真锥(proper cone)n真锥的定义：锥真锥的定义：锥 满足如下条件满足如下条件K具有内点具有内点K内不含直线内不含直线可编辑可编辑2323广义不等式n真锥真锥 下的下的偏序关系偏序关系：n例：例：n逐项不等式逐项不等式

7、n矩阵不等式矩阵不等式广义不等式广义不等式严格广义不等式严格广义不等式可编辑可编辑2424广义不等式的性质可编辑可编辑2525严格广义不等式的性质可编辑可编辑2626最值和极值n最小元的定义：设最小元的定义：设 ，对，对 ，都有，都有 成立，则称成立，则称 为为 的最小元。的最小元。n极小元的定义：设极小元的定义：设 ，对于，对于 ，若，若 ，则，则 成立，则称成立，则称 为为 的极小元。的极小元。可编辑可编辑2727分割超平面(separating hyperplane)n定理：设定理：设 和和 为两不相交凸集，则存在超平面将为两不相交凸集，则存在超平面将 和和 分离。即：分离。即：可编辑可

8、编辑2828支撑超平面(supporting hyperplane)n定义：设集合定义：设集合 ，为为 边界上的点。若存在边界上的点。若存在 ，满足对任意满足对任意 ，都有，都有 成立，则称超平成立，则称超平面面 为集合为集合 在点在点 处的支撑超平面。处的支撑超平面。n定理：凸集边界上任意一点均存在支撑超平面。定理：凸集边界上任意一点均存在支撑超平面。n定理：若一个闭的非中空集合，在边界上的任意一点定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。存在支撑超平面，则该集合为凸集。可编辑可编辑2929对偶锥(dual cone)n对偶锥的定义：设对偶锥的定义：设 为

9、锥，则集合为锥，则集合 称为对偶锥。称为对偶锥。n对偶锥的性质：对偶锥的性质：真锥的对偶锥仍真锥的对偶锥仍然是真锥！然是真锥！可编辑可编辑3030对偶广义不等式n广义不等式与对偶等价性质广义不等式与对偶等价性质n最小元的对偶特性：最小元的对偶特性：可编辑可编辑3131对偶广义不等式n极小元的对偶特性极小元的对偶特性反过来不一定成反过来不一定成立！立！可编辑可编辑3232作业nP60 2.8nP60 2.10nP60 2.14nP62 2.16nP62 2.18nP64 2.30nP64 2.31nP64 2.33可编辑可编辑3333凸优化理论与应用凸优化理论与应用第二章第二章 凸函数凸函数可编

10、辑可编辑3434凸函数的定义1.定义域定义域 为凸集；为凸集；2.，有，有n凸函数的定义：函数凸函数的定义：函数 ，满足，满足n凸函数的扩展定义：若凸函数的扩展定义：若 为凸函数，则可定义其扩为凸函数，则可定义其扩展函数展函数 为为凸函数的凸函数的扩展函数扩展函数也是凸函也是凸函数！数！可编辑可编辑3535凸函数的一阶微分条件n若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 一阶可微，一阶可微，则函数则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对可编辑可编辑3636凸函数的二阶微分条件n若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 二阶可微，二

11、阶可微，则函数则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对 ，其，其Hessian矩阵矩阵可编辑可编辑3737凸函数的例n幂函数幂函数n负对数函数负对数函数n负熵函数负熵函数n范数函数范数函数n指数函数指数函数可编辑可编辑3838凸函数的例可编辑可编辑3939下水平集(sublevel set)n定理：凸函数的任一下水平集均为凸集。定理：凸函数的任一下水平集均为凸集。n任一下水平集均为凸集的函数任一下水平集均为凸集的函数不一定不一定为凸函数。为凸函数。称为称为 的的 下水平集。下水平集。n定义：集合定义：集合可编辑可编辑4040函数上半图(epigraph)n定理：函数定

12、理：函数 为凸函数为凸函数当且仅当当且仅当 的上半图为凸集。的上半图为凸集。称为函数称为函数 的上半图。的上半图。n定义：集合定义：集合可编辑可编辑4141Jensen不等式n 为凸函数，则有：为凸函数，则有：nJensen不等式的另外形式：不等式的另外形式：可编辑可编辑4242保持函数凸性的算子n凸函数的逐点最大值凸函数的逐点最大值n凸函数与仿射变换的复合凸函数与仿射变换的复合n凸函数的非负加权和凸函数的非负加权和可编辑可编辑4343保持函数凸性的算子n复合运算复合运算n最小值算子最小值算子n凸函数的透视算子凸函数的透视算子可编辑可编辑4444共轭函数(conjugate function)

13、n定义：设函数定义：设函数 ，其共轭函数，其共轭函数 ，定义为，定义为n共轭函数的例共轭函数的例共轭函数共轭函数具有凸性！具有凸性！可编辑可编辑4545共轭函数的性质nFenchels inequalityn性质：若性质：若 为凸函数，且为凸函数，且 的上半图是闭集，则有的上半图是闭集，则有n性质：设性质：设 为凸函数，且可微，对于为凸函数，且可微，对于 ，若，若则则可编辑可编辑4646准凸函数(quasiconvex function)n准凸函数的例准凸函数的例n定义：设函数定义：设函数 ，若函数的定义域和任意下水，若函数的定义域和任意下水平集平集则称函数则称函数 为准凸函数。为准凸函数。可

14、编辑可编辑4747准凸函数的判定定理n定理：函数定理：函数 为准凸函数，当且仅当为准凸函数，当且仅当 为凸集，且为凸集，且对对 ，有，有n定理：若函数定理：若函数 一阶可微，则一阶可微，则 为准凸函数，当且仅为准凸函数，当且仅当当 为凸集，且对为凸集，且对 ，有，有 ，有，有n定理：若函数定理：若函数 二阶可微，且满足对二阶可微，且满足对则函数则函数 准凸函数。准凸函数。可编辑可编辑4848n最小值函数最小值函数n非负权值函数的最大值函数非负权值函数的最大值函数保持准凸性的算子n复合函数复合函数可编辑可编辑4949准凸函数的凸函数族表示n若若 为准凸函数，根据为准凸函数，根据 的任意的任意 下

15、水平集，我们下水平集，我们可以构造一个凸函数族可以构造一个凸函数族 ，使得，使得n性质：若性质：若 为准凸函数为准凸函数 的凸函数族表示，对每一个的凸函数族表示，对每一个 ，若，若 ，则有，则有可编辑可编辑5050对数凸函数 为凸集为凸集为凸函数。为凸函数。n定义：函数定义：函数 称为对数凸函数，若函数称为对数凸函数，若函数 满足：满足：n定理：函数定理：函数 的定义域为凸集，且的定义域为凸集，且 ，则，则 为为对数凸函数，当且仅当对对数凸函数，当且仅当对 有有n对数凸函数的例对数凸函数的例可编辑可编辑5151对数凸函数和凹函数的性质n性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封性质：

16、对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。闭。n定理：函数定理：函数 二阶可微，则二阶可微，则 为对数凸函数当且仅为对数凸函数当且仅当当n性质：对数凸性对函数加运算保持封闭。但对数凹性对函数性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。加运算不封闭。n推论：函数推论：函数 对每一个对每一个 在在 上对数凸，则函数上对数凸，则函数 也是对数凸函数。也是对数凸函数。可编辑可编辑5252对数凸函数和凹函数的性质n定理：函数定理：函数 为对数凹函数，则函为对数凹函数，则函数数 是对数凹函数。是对数凹函数。可编辑可编辑5353广义不等式下的凸性n广义单调性的定义：设广义单调性

17、的定义：设 为真锥，函数为真锥，函数 称为称为 单调增，若函数单调增，若函数 满足：满足：n广义凸函数的定义：设广义凸函数的定义：设 为真锥，函数为真锥，函数 称为称为 凸，若函数凸，若函数 满足对满足对 均有均有n定理定理(对偶等价对偶等价)：函数函数 为为 凸函数，当且仅当对所有凸函数，当且仅当对所有 ，为凸函数。为凸函数。可编辑可编辑5454作业(1)nP116 3.16nP116 3.21可编辑可编辑5555作业(2)nP121 3.41nP122 3.49 (1)(2)可编辑可编辑5656凸优化理论与应用凸优化理论与应用第三章第三章 凸优化凸优化可编辑可编辑5757优化问题的基本形式

18、n优化问题的基本描述：优化问题的基本描述：优化变量优化变量不等式约束不等式约束等式约束等式约束无约束优化无约束优化可编辑可编辑5858优化问题的基本形式最优化值最优化值最优化解最优化解 优化问题的域优化问题的域 可行点可行点(解解)(feasible)满足约束条件满足约束条件 可行域可行域(可解集可解集)所有可行点的集合所有可行点的集合可编辑可编辑5959局部最优问题n局部最优问题局部最优问题可编辑可编辑6060优化问题的等价形式(1)n定理：若定理：若 则原优化问题与以下优化问题等价则原优化问题与以下优化问题等价可编辑可编辑6161优化问题的等价形式(2)n定理：设定理：设 为一一对应，且为

19、一一对应，且 则原优化问题与以下优化问题等价则原优化问题与以下优化问题等价可编辑可编辑6262优化问题的等价形式(3)n定理：设定理：设 为严格单调增函数；为严格单调增函数；满满足足 当且仅当当且仅当 ；满足满足 当当且仅当且仅当 。则原优化问题与以下优化问题等价。则原优化问题与以下优化问题等价可编辑可编辑6363优化问题的等价形式(4)n定理：原优化问题与以下优化问题等价定理：原优化问题与以下优化问题等价n 称为松弛变量称为松弛变量可编辑可编辑6464优化问题的等价形式(5)n定理：设定理：设 满足等式满足等式 成立，当且仅当成立，当且仅当 。则原优化问题与以下优化。则原优化问题与以下优化问

20、题等价问题等价可编辑可编辑6565可分离变量优化问题n性质：性质：其中其中可以分离变量可以分离变量n定理：优化问题定理：优化问题可编辑可编辑6666优化问题的上半图形式可编辑可编辑6767凸优化问题的基本形式n凸优化问题的基本描述：凸优化问题的基本描述：为仿射函数为仿射函数 为凸函数为凸函数 若若 为准凸函数，则优化问题称为准凸优化问题。为准凸函数，则优化问题称为准凸优化问题。性质：凸优化问题的可行域是凸集。性质：凸优化问题的可行域是凸集。可编辑可编辑6868凸优化问题的例n例：例：等价于凸优化问题等价于凸优化问题可编辑可编辑6969凸优化问题的局部最优解n定理：凸优化问题的局部最优解均是全局

21、最优解。定理：凸优化问题的局部最优解均是全局最优解。可编辑可编辑7070凸优化问题最优解的微分条件n定理：设定理：设 为凸优化问题的可行域，为凸优化问题的可行域，可微。则可微。则 为最优解当且仅当为最优解当且仅当 成立。成立。n定理：非约束凸优化问题中，若定理：非约束凸优化问题中，若 可微。则可微。则 为最为最优解当且仅当优解当且仅当 成立。成立。可编辑可编辑7171凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，且存在向量，且存在向量 满足满足 n定理：设凸优化问题仅有等式约束定理：设凸优化问题仅有等式约束可编辑可编辑7272凸优化问题的等价形式则则 为最优解当且仅当为最优解当

22、且仅当 ，且，且 n定理：设凸优化问题定理：设凸优化问题可编辑可编辑7373凸优化问题的等价形式等价于等价于 n定理：设凸优化问题定理：设凸优化问题其中其中 可编辑可编辑7474凸优化问题的等价形式等价于等价于 n定理：设凸优化问题定理：设凸优化问题可编辑可编辑7575准凸优化问题 为准凸函数，为准凸函数，为凸函数。为凸函数。n准凸优化问题的基本描述准凸优化问题的基本描述n注：准凸优化问题的局部最优解不一定是全局最优解。注：准凸优化问题的局部最优解不一定是全局最优解。可编辑可编辑7676准凸优化问题的上半图形式n设设 为准凸函数为准凸函数 的凸函数族表示，即的凸函数族表示，即 则准凸优化问题的

23、可行解问题为则准凸优化问题的可行解问题为n设设 为准凸优化问题的最优解，若上述问题可解，则为准凸优化问题的最优解，若上述问题可解，则 。否则。否则 。可编辑可编辑7777准凸优化问题二分法求解n给定一个足够小的给定一个足够小的 和足够大的和足够大的 ，使得区间，使得区间 能包含最优解能包含最优解 。给定。给定nLOOP：n令令n求解可行解问题；求解可行解问题；n若可解，则令若可解，则令 ，否则令，否则令n若若 ，则结束，否则，则结束，否则goto LOOP。可编辑可编辑7878线性规划(linear program,LP)nLP问题的一般描述问题的一般描述可编辑可编辑7979LP问题的几种类型

24、n标准标准LP问题问题n不等式形式不等式形式LP问题问题可编辑可编辑8080标准LP问题的转换可编辑可编辑8181LP问题的例nChebyshev center of a polyhedronnPiecewise-linear minimizationnLinear-fractional programming可编辑可编辑8282Chebyshev center of a polyhedronn多面体nChebyshev center：到多面体边界距离最大的内点（最深的点）n问题描述nLP形式可编辑可编辑8383Piecewise-linear minimizationn问题描述n上半图形式n

25、LP形式可编辑可编辑8484Linear-fractional programmingn问题描述nLP形式可编辑可编辑8585二次规划(quadratic program,QP)nQP问题的基本描述问题的基本描述可编辑可编辑8686二次约束二次规划nquadratically constrained quadratic program(QCQP)可编辑可编辑8787QP问题的例nLeast-squares and regressionnDistance between polyhedra可编辑可编辑8888Least-squares and regressionn问题描述可编辑可编辑8989D

26、istance between polyhedran问题描述nQP形式可编辑可编辑9090Second-order cone program,SOCPnSOCP问题的基本描述n二次锥约束条件可编辑可编辑9191SOCP问题的例Robust linear programmingn问题描述其中 不是完全确定的常数。n例：为确定的常数，为变量，其范围满足SOCP形式可编辑可编辑9292几何规划(Geometric programming)n单项式与多项式n几何规划的基本描述可编辑可编辑9393几何规划的凸形式转换n令n几何规划的凸形式可编辑可编辑9494广义不等式约束n广义不等式约束的优化问题nSO

27、CP的描述可编辑可编辑9595凸优化理论与应用凸优化理论与应用第四章第四章 对偶问题对偶问题可编辑可编辑9696优化问题的拉格朗日函数n设优化问题：设优化问题：n拉格朗日拉格朗日(Lagrangian)函数：函数：n对固定的对固定的 ，拉格朗日函数，拉格朗日函数 为关于为关于 和和 的的仿仿射函数射函数。可编辑可编辑9797拉格朗日对偶函数n拉格朗日对偶函数拉格朗日对偶函数(lagrange dual function)：若拉格朗日函数没有下界，则令若拉格朗日函数没有下界，则令n拉格朗日对偶函数为拉格朗日对偶函数为凹函数凹函数。n对对 和和 ，若原最优化问题有最优值，若原最优化问题有最优值 ，

28、则，则可编辑可编辑9898对偶函数的例nLeast-squares solution of linear equationsnStandard form LPnTwo-way partitioning problem可编辑可编辑9999Least-squares solution of linear equationsn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：可编辑可编辑100100Standard form LPn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：可编辑可编辑101101Two-way partit

29、ioning problemn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：可编辑可编辑102102对偶函数与共轭函数n共轭函数共轭函数n共轭函数与对偶函数存在密切联系共轭函数与对偶函数存在密切联系n具有线性不等式约束和线性等式约束的优化问题：具有线性不等式约束和线性等式约束的优化问题：对偶函数：对偶函数：可编辑可编辑103103Equality constrained norm minimizationn问题描述：问题描述：n共轭函数：共轭函数：n对偶函数：对偶函数：可编辑可编辑104104Entropy maximizationn原始问题：原始问题：n

30、共轭函数：共轭函数：n对偶函数对偶函数：可编辑可编辑105105Minimum volume covering ellipsoidn原始问题：原始问题：n对偶函数：对偶函数：n共轭函数：共轭函数：可编辑可编辑106106拉格朗日对偶问题n拉格朗日对偶问题的描述：拉格朗日对偶问题的描述：n对偶可行域对偶可行域n最优值最优值n最优解最优解可编辑可编辑107107LP问题的对偶问题n标准标准LP问题问题n对偶函数对偶函数n对偶问题对偶问题n等价描述等价描述可编辑可编辑108108弱对偶性n定理（弱对偶性）定理（弱对偶性）：设原始问题的最优值为：设原始问题的最优值为 ，对偶问，对偶问题的最优值为题的最

31、优值为 ，则，则 成立。成立。noptimal duality gapn可以利用对偶问题找到原始问题最优解的下界。可以利用对偶问题找到原始问题最优解的下界。可编辑可编辑109109强对偶性n强对偶性并不是总是成立的。强对偶性并不是总是成立的。n定义（强对偶性）定义（强对偶性）：设原始问题的最优值为：设原始问题的最优值为 ，对偶问，对偶问题的最优值为题的最优值为 。若。若 成立，则称原始问题和对成立，则称原始问题和对偶问题之间具有偶问题之间具有强对偶性强对偶性。n凸优化问题凸优化问题通常（但并不总是）通常（但并不总是）具有强对偶性。具有强对偶性。nSlater定理：若凸优化问题存在严格可行解，即

32、存在定理：若凸优化问题存在严格可行解，即存在 ，满足，满足则优化问题具有强对偶性。该条件称为则优化问题具有强对偶性。该条件称为Slater条件条件。可编辑可编辑110110强对偶性存在存在 ，满足，满足n弱化的弱化的Slater条件：若不等式约束条件的前条件：若不等式约束条件的前 个为线性不个为线性不等式约束条件，则等式约束条件，则Slater条件可以弱化为：条件可以弱化为：可编辑可编辑111111Least-squares solution of linear equationsn原问题：原问题：n对偶问题：对偶问题：n具有强对偶性具有强对偶性可编辑可编辑112112Lagrange dua

33、l of QCQPnQCQP：n拉格朗日函数：拉格朗日函数：n对偶函数：对偶函数：可编辑可编辑113113Lagrange dual of QCQPn对偶问题对偶问题：nSlater条件：存在条件：存在 ，满足，满足可编辑可编辑114114Entropy maximizationn原始问题：原始问题：n对偶函数：对偶函数：n对偶问题对偶问题：可编辑可编辑115115Entropy maximizationn弱化的弱化的Slater条件：存在条件：存在 ，满足，满足可编辑可编辑116116Minimum volume covering ellipsoidn原始问题：原始问题：n对偶函数：对偶函数

34、：n对偶问题：对偶问题：可编辑可编辑117117Minimum volume covering ellipsoidn弱化的弱化的Slater条件总成立，因此该优化问题具有强对偶性。条件总成立，因此该优化问题具有强对偶性。n弱化的弱化的Slater条件：存在条件：存在 ，满足，满足可编辑可编辑118118对偶可行解的不等式对偶可行解的不等式n对于一优化问题，若对于一优化问题，若 为一可行解，为一可行解，为对偶问题可行解，为对偶问题可行解，则有如下不等式：则有如下不等式：为为 次优解，其中次优解，其中n不等式可以用于对次优解的精度估计不等式可以用于对次优解的精度估计可编辑可编辑119119互补松弛

35、条件互补松弛条件所以所以n设设 为原始优化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则若两者具有强对偶性，则即即可编辑可编辑120120KKT优化条件优化条件n设优化问题中，函数设优化问题中，函数 可微。设可微。设 为原始优化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，且两者为对偶问题的最优解，且两者具有强对偶性，则具有强对偶性，则 满足如下条件：满足如下条件：KKT条件为条件为必要条件！必要条件！可编辑可编辑121121凸优化问题的凸优化问题的KKT条件条件可微。设可微。设 满足满足KKT条件，则条件，则 为原始问题的最优

36、解，而为原始问题的最优解，而 为对偶问题的最优解，且两者具有强对偶性。为对偶问题的最优解，且两者具有强对偶性。n设原始问题为凸优化问题中，函数设原始问题为凸优化问题中，函数可编辑可编辑122122例例n原始凸优化问题原始凸优化问题KKT条件条件可编辑可编辑123123例例其中其中解得解得可编辑可编辑124124凸优化问题的对偶求解凸优化问题的对偶求解存在唯一解存在唯一解 。若。若 为原始问题的可行解，则为原始问题的可行解，则 即为原始问题即为原始问题的最优解；若的最优解；若 不是原始问题的可行解，则原始问题不存在最不是原始问题的可行解，则原始问题不存在最优解。优解。n设原始优化问题与对偶问题具

37、有强对偶性，且设原始优化问题与对偶问题具有强对偶性，且 为对偶问为对偶问题的最优解。题的最优解。存在唯一的最小解，即存在唯一的最小解，即可编辑可编辑125125扰动问题扰动问题n扰动问题：扰动问题：n当当 时即为原始问题。时即为原始问题。n若若 为正，则第为正，则第 个不等式约束被放宽；若个不等式约束被放宽；若 为负，则第为负，则第 个个不等式约束被收紧。不等式约束被收紧。n记记 为扰动问题的最优解。若扰动问题无最优解，则记为扰动问题的最优解。若扰动问题无最优解，则记可编辑可编辑126126灵敏度分析灵敏度分析n设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰设对偶问题存在最优解，且与

38、原始问题具有强对偶性，若非干扰问题的最优对偶解为问题的最优对偶解为 ，则有，则有n若若 在在 处可微，则处可微，则可编辑可编辑127127n定义（弱选择性）：若两个不等式（等式）系统，至多有一个可定义（弱选择性）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。解，则称这两个系统具有弱选择性。选择定理选择定理n对偶不等式组对偶不等式组n设原始问题的约束条件：设原始问题的约束条件：n对偶问题对偶问题n原始问题的约束条件与对偶不等式组具有弱选择性。原始问题的约束条件与对偶不等式组具有弱选择性。可编辑可编辑128128选择定理选择定理n对偶不等式组对偶不等式组n设原始问题的严格

39、不等式约束条件：设原始问题的严格不等式约束条件：n原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。可编辑可编辑129129n定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。则称这两个系统具有强选择性。选择定理选择定理n对偶不等式组对偶不等式组n设原始问题为凸优化问题，其严格不等式约束条件为：设原始问题为凸优化问题，其严格不等式约束条件为：n若存在若存在 ，满足，满足 ，则上述两不等式约束系统，则上述两不等式约束系统具有强选择性。具有强选

40、择性。可编辑可编辑130130选择定理选择定理n对偶不等式组对偶不等式组n设原始问题为凸优化问题，其不等式约束条件为：设原始问题为凸优化问题，其不等式约束条件为：则原始问题的不等式约束条件与对偶不等式组具有强选择性。则原始问题的不等式约束条件与对偶不等式组具有强选择性。n若存在若存在 ，满足，满足 ，且下述优化问题存在最优，且下述优化问题存在最优解解可编辑可编辑131131罚函数的例n 范数：范数：n死区线性罚函数：死区线性罚函数：n对数门限罚函数对数门限罚函数可编辑可编辑132132鲁棒的罚函数n若若 大到一定程度时，罚函数为大到一定程度时，罚函数为 的线性函数，则称的线性函数，则称该罚函数

41、为鲁棒的罚函数。该罚函数为鲁棒的罚函数。nHuber罚函数罚函数可编辑可编辑133133最小范数问题最小范数问题n问题描述：问题描述：其中其中 为方程组为方程组 的解。的解。n可以消去等式约束将其转换为范数逼近问题：可以消去等式约束将其转换为范数逼近问题：可编辑可编辑134134最小范数问题最小范数问题n最小平方范数问题：范数最小平方范数问题：范数 ，最优解满足：，最优解满足：n最小罚问题：最小罚问题：n绝对值和最小问题：范数绝对值和最小问题：范数 ，原问题可转换为，原问题可转换为LP问问题：题：可编辑可编辑135135正则逼近正则逼近n二元矢量优化问题描述：二元矢量优化问题描述：n正则化问题

42、：正则化问题：最优解描述了两分量的一条折中曲线。最优解描述了两分量的一条折中曲线。可编辑可编辑136136正则逼近正则逼近nTikhonov正则化问题：正则化问题：为二次优化问题：为二次优化问题：最优解的形式最优解的形式：可编辑可编辑137137正则逼近正则逼近nTikhonov光滑正则化问题：光滑正则化问题：为二阶差分算子：为二阶差分算子：可编辑可编辑138138信号复原信号复原n已知加噪信号：已知加噪信号：信号复原问题的描述：信号复原问题的描述：函数函数 为正则函数或光滑函数。为正则函数或光滑函数。可编辑可编辑139139信号复原信号复原可编辑可编辑140140信号复原信号复原可编辑可编辑

43、141141信号复原信号复原可编辑可编辑142142鲁棒逼近鲁棒逼近n问题描述：问题描述：n随机鲁棒逼近：随机鲁棒逼近：为随机变量，逼近问题转换为最小化为随机变量，逼近问题转换为最小化期望期望n例：例：随机鲁棒逼近为：随机鲁棒逼近为：转换为转换为：可编辑可编辑143143随机鲁棒逼近随机鲁棒逼近n 为随机变量：为随机变量：最小平方随机鲁棒逼近为：最小平方随机鲁棒逼近为：转换为转换为：其中其中可编辑可编辑144144最坏情况鲁棒逼近最坏情况鲁棒逼近n考虑考虑 ，最坏情况鲁棒逼近为：，最坏情况鲁棒逼近为：n例：例：随机鲁棒逼近为：随机鲁棒逼近为：转换为转换为：可编辑可编辑145145凸优化理论与应

44、用凸优化理论与应用第第6 6章章 统计估计统计估计可编辑可编辑146146概率分布的参数估计n随机变量的概率密度为随机变量的概率密度为 ，其中，其中 为概率分布的参数，为概率分布的参数，且参数未知。参数估计的目标就是通过一些已知样本估且参数未知。参数估计的目标就是通过一些已知样本估计获得参数的最优近似值。计获得参数的最优近似值。n问题描述问题描述n 为样本观测值；为样本观测值；n 为对数似然函数；为对数似然函数；n若似然函数为凹函数，则优化问题为凸优化问题。若似然函数为凹函数，则优化问题为凸优化问题。可编辑可编辑147147具有独立同分布噪声的线性测量n线性测量模型：线性测量模型：n 为观测值

45、或测量值；为观测值或测量值；n 为未知参数向量；为未知参数向量；n 独立同分布噪声，其概率密度为独立同分布噪声，其概率密度为 。n似然函数为似然函数为n最大似然估计问题为：最大似然估计问题为：可编辑可编辑148148例例n高斯白噪声高斯白噪声对数似然函数：对数似然函数：n区间区间 上均匀分布的噪声：上均匀分布的噪声：对数似然函数：对数似然函数：可编辑可编辑149149逻辑回归n随机变量随机变量 的概率分布为：的概率分布为：n 为参数；为参数；n 为可观测的解释变量；为可观测的解释变量；为观察值。为观察值。对数似然函数对数似然函数：可编辑可编辑150150假定测验n随机变量随机变量 ，有，有 种

46、可能（假定）的分布；种可能（假定）的分布；n假定假定 ：的概率分布为的概率分布为n假定测验的目标：由观察值猜测随机变量最有可能服从假定测验的目标：由观察值猜测随机变量最有可能服从哪种假定的分布。哪种假定的分布。n当当 时，称为二元假定测验。时，称为二元假定测验。n随机检测子：非负元素矩阵随机检测子：非负元素矩阵 可编辑可编辑151151假定测验n 为当为当 实际服从第实际服从第1种假定分布而猜测为第种假定分布而猜测为第2种假定种假定分布的概率；分布的概率；n 为当为当 实际服从第实际服从第2种假定分布而猜测为第种假定分布而猜测为第1种假定种假定分布的概率；分布的概率；n多目标优化形式多目标优化

47、形式：n检测概率矩阵检测概率矩阵可编辑可编辑152152假定测验n最小最大值形式最小最大值形式n尺度优化形式：尺度优化形式：可编辑可编辑153153例例n 在两种假设下的概率分布为：在两种假设下的概率分布为：可编辑可编辑154154例例可编辑可编辑155155实验设计实验设计n线性测量问题线性测量问题n最大似然估计值：最大似然估计值：n 独立同分布高斯白噪声，服从分布独立同分布高斯白噪声，服从分布 。n估计误差估计误差 均值为均值为0，方差为，方差为信赖椭圆为信赖椭圆为可编辑可编辑156156实验设计实验设计n实验设计的目标：寻找实验设计的目标：寻找 ，使得误差的方差，使得误差的方差矩阵最小。

48、矩阵最小。n向量优化形式：向量优化形式：n为整数问题，求解较困难。为整数问题，求解较困难。可编辑可编辑157157实验设计实验设计n当当 时，令时，令 近似为一连续实数，原问题近似为一连续实数，原问题可松弛转换为连续实数优化：可松弛转换为连续实数优化：可编辑可编辑158158凸优化理论与应用凸优化理论与应用第第7 7章章 无约束优化无约束优化可编辑可编辑159159无约束优化问题n问题描述：问题描述：n无约束问题求解的两种方法：无约束问题求解的两种方法：n迭代逼近：迭代逼近：n求解梯度方程：求解梯度方程：n 为凸函数，且二次可微。为凸函数，且二次可微。可编辑可编辑160160例梯度方程梯度方程

49、n二次优化：二次优化：可编辑可编辑161161迭代起始点迭代起始点n满足条件满足条件2的几种函数：的几种函数：n起始点起始点 满足：满足：n函数函数 任意下水平集都是闭集；任意下水平集都是闭集；n函数的定义域为函数的定义域为n当当 时，时，可编辑可编辑162162强凸性n定义：函数定义：函数 在在 上具有强凸性，若上具有强凸性，若 满足满足n若函数若函数 具有强凸性，则有具有强凸性，则有n 为最优值，则为最优值，则可编辑可编辑163163强凸性则有则有n 为最优值，则为最优值，则n若函数若函数 在在 上具有强凸性，则可以证明存在上具有强凸性，则可以证明存在 ，满足，满足 可编辑可编辑16416

50、4强凸性n对于对于 ，矩阵，矩阵 的特征值从大到小依次的特征值从大到小依次为为 。则有：。则有：n定义：矩阵定义：矩阵 的条件数为最大特征值与最小的条件数为最大特征值与最小特征值之比，即特征值之比，即 。n条件数的上界：条件数的上界：可编辑可编辑165165下降法n下降法的基本原理：下降法的基本原理：迭代迭代 ，满足，满足 为下降方向，为下降方向，为步长因子为步长因子。n对于凸函数对于凸函数 ，当，当 满足满足 时，存在某时，存在某个个 ，使得，使得 。可编辑可编辑166166下降法n下降法的一般步骤：下降法的一般步骤：n给出初始点给出初始点 ；n循环迭代循环迭代n计算下降方向计算下降方向 ；