庄老师凸优化课件.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理论部分理论部分

2、n凸集和凸函数凸集和凸函数n凸优化问题凸优化问题n对偶问题对偶问题n应用部分应用部分n逼近与拟合逼近与拟合n统计估计统计估计n几何问题几何问题n算法部分算法部分n非约束优化方法非约束优化方法n等式约束优化方法等式约束优化方法n内点法内点法信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5 5n熟悉了解凸优化理论的基本原理和基本方法；熟悉了解凸优化理论的基本原理和基本方法；n掌握实际问题转化为凸优化问题的基本方法；掌握实际问题转化为凸优化问题的基本方法；n掌握最优化问题的经典算法。掌握最优化问题的经典算法。课程要求信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6 6参考书目nSteph

3、en Boyd and Lieven Vandenberghe,“Convex Optimization”,Cambridge University Press.n袁亚湘、孙文瑜，袁亚湘、孙文瑜，“最优化理论与方法最优化理论与方法”，科学出版，科学出版社，社，1999。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7 7凸优化理论与应用凸优化理论与应用第一章第一章凸集凸集信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8 8仿射集(Affine sets)n直线的表示：直线的表示：n线段的表示：线段的表示：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9 9仿射集(Affine

4、 sets)n仿射集的定义：过集合仿射集的定义：过集合C内任意两点的直线均在集合内任意两点的直线均在集合C内，则称集合内，则称集合C为仿射集。为仿射集。n仿射集的例：直线、平面、超平面仿射集的例：直线、平面、超平面信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1010仿射集n仿射包：包含集合仿射包：包含集合C的最小的仿射集。的最小的仿射集。n仿射维数：仿射包的维数。仿射维数：仿射包的维数。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1111仿射集n内点（内点（interior）：）：n相对内点（相对内点（relative interior）：）：信息与通信工程学院信息与通信工程学

5、院 庄伯金庄伯金 1212凸集(Convex Sets)n凸集的定义：集合凸集的定义：集合C内任意两点间的线段均在集合内任意两点间的线段均在集合C内，则称集合内，则称集合C为凸集。为凸集。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1313凸集n凸包的定义：包含集合凸包的定义：包含集合C的最小的凸集。的最小的凸集。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1414锥(Cones)n锥的定义：锥的定义：n凸锥的定义：集合凸锥的定义：集合C既是凸集又是锥。既是凸集又是锥。n锥包的定义：集合锥包的定义：集合C内点的所有锥组合。内点的所有锥组合。信息与通信工程学院信息与通信工程学院

6、庄伯金庄伯金 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)：信息与通信工程学院

7、信息与通信工程学院 庄伯金庄伯金 1919半正定锥(Positive semidefinite cone)nn阶对称矩阵集：阶对称矩阵集：nn阶半正定矩阵集：阶半正定矩阵集：nn阶正定矩阵集：阶正定矩阵集：n阶半正定矩阵集为阶半正定矩阵集为凸锥！凸锥！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2020保持凸性的运算n集合交运算集合交运算n仿射变换仿射变换n透视透视/投射函数投射函数(perspective function)信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2121保持凸性的运算n线性分式函数线性分式函数(linear-fractional function)信息与

8、通信工程学院信息与通信工程学院 庄伯金庄伯金 2222真锥(proper cone)n真锥的定义：锥真锥的定义：锥 满足如下条件满足如下条件K具有内点具有内点K内不含直线内不含直线信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2323广义不等式n真锥真锥 下的下的偏序关系偏序关系：n例：例：n逐项不等式逐项不等式n矩阵不等式矩阵不等式广义不等式广义不等式严格广义不等式严格广义不等式信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2424广义不等式的性质信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2525严格广义不等式的性质信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2

9、626最值和极值n最小元的定义：设最小元的定义：设 ，对，对 ，都有，都有 成立，则称成立，则称 为为 的最小元。的最小元。n极小元的定义：设极小元的定义：设 ，对于，对于 ，若，若 ，则，则 成立，则称成立，则称 为为 的极小元。的极小元。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2727分割超平面(separating hyperplane)n定理：设定理：设 和和 为两不相交凸集，则存在超平面将为两不相交凸集，则存在超平面将 和和 分离。即：分离。即：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2828支撑超平面(supporting hyperplane)n定义：设集

10、合定义：设集合 ，为为 边界上的点。若存在边界上的点。若存在 ，满足对任意满足对任意 ，都有，都有 成立，则称超平成立，则称超平面面 为集合为集合 在点在点 处的支撑超平面。处的支撑超平面。n定理：凸集边界上任意一点均存在支撑超平面。定理：凸集边界上任意一点均存在支撑超平面。n定理：若一个闭的非中空集合，在边界上的任意一点定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。存在支撑超平面，则该集合为凸集。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2929对偶锥(dual cone)n对偶锥的定义：设对偶锥的定义：设 为锥，则集合为锥，则集合 称为对偶锥。称为

11、对偶锥。n对偶锥的性质：对偶锥的性质：真锥的对偶锥仍真锥的对偶锥仍然是真锥！然是真锥！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3030对偶广义不等式n广义不等式与对偶等价性质广义不等式与对偶等价性质n最小元的对偶特性：最小元的对偶特性：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3131对偶广义不等式n极小元的对偶特性极小元的对偶特性反过来不一定成反过来不一定成立！立！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3232作业nP60 2.8nP60 2.10nP60 2.14nP62 2.16nP62 2.18nP64 2.30nP64 2.31nP64 2.33信

12、息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3333凸优化理论与应用凸优化理论与应用第二章第二章 凸函数凸函数信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3434凸函数的定义1.定义域定义域 为凸集；为凸集；2.，有，有n凸函数的定义：函数凸函数的定义：函数 ，满足，满足n凸函数的扩展定义：若凸函数的扩展定义：若 为凸函数，则可定义其扩为凸函数，则可定义其扩展函数展函数 为为凸函数的凸函数的扩展函数扩展函数也是凸函也是凸函数！数！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3535凸函数的一阶微分条件n若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 一阶可微

13、，一阶可微，则函数则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3636凸函数的二阶微分条件n若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 二阶可微，二阶可微，则函数则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对 ，其，其Hessian矩阵矩阵信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3737凸函数的例n幂函数幂函数n负对数函数负对数函数n负熵函数负熵函数n范数函数范数函数n指数函数指数函数信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3838凸函数的例信息与通信工程学院

14、信息与通信工程学院 庄伯金庄伯金 3939下水平集(sublevel set)n定理：凸函数的任一下水平集均为凸集。定理：凸函数的任一下水平集均为凸集。n任一下水平集均为凸集的函数任一下水平集均为凸集的函数不一定不一定为凸函数。为凸函数。称为称为 的的 下水平集。下水平集。n定义：集合定义：集合信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4040函数上半图(epigraph)n定理：函数定理：函数 为凸函数为凸函数当且仅当当且仅当 的上半图为凸集。的上半图为凸集。称为函数称为函数 的上半图。的上半图。n定义：集合定义：集合信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4141Je

15、nsen不等式n 为凸函数，则有：为凸函数，则有：nJensen不等式的另外形式：不等式的另外形式：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4242保持函数凸性的算子n凸函数的逐点最大值凸函数的逐点最大值n凸函数与仿射变换的复合凸函数与仿射变换的复合n凸函数的非负加权和凸函数的非负加权和信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4343保持函数凸性的算子n复合运算复合运算n最小值算子最小值算子n凸函数的透视算子凸函数的透视算子信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4444共轭函数(conjugate function)n定义：设函数定义：设函数 ，其共轭函数

16、，其共轭函数 ，定义为，定义为n共轭函数的例共轭函数的例共轭函数共轭函数具有凸性！具有凸性！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4545共轭函数的性质nFenchels inequalityn性质：若性质：若 为凸函数，且为凸函数，且 的上半图是闭集，则有的上半图是闭集，则有n性质：设性质：设 为凸函数，且可微，对于为凸函数，且可微，对于 ，若，若则则信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4646准凸函数(quasiconvex function)n准凸函数的例准凸函数的例n定义：设函数定义：设函数 ，若函数的定义域和任意下水，若函数的定义域和任意下水平集平集则称

17、函数则称函数 为准凸函数。为准凸函数。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4747准凸函数的判定定理n定理：函数定理：函数 为准凸函数，当且仅当为准凸函数，当且仅当 为凸集，且为凸集，且对对 ，有，有n定理：若函数定理：若函数 一阶可微，则一阶可微，则 为准凸函数，当且仅为准凸函数，当且仅当当 为凸集，且对为凸集，且对 ，有，有 ，有，有n定理：若函数定理：若函数 二阶可微，且满足对二阶可微，且满足对则函数则函数 准凸函数。准凸函数。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4848n最小值函数最小值函数n非负权值函数的最大值函数非负权值函数的最大值函数保持准凸性的算

18、子n复合函数复合函数信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4949准凸函数的凸函数族表示n若若 为准凸函数，根据为准凸函数，根据 的任意的任意 下水平集，我们下水平集，我们可以构造一个凸函数族可以构造一个凸函数族 ，使得，使得n性质：若性质：若 为准凸函数为准凸函数 的凸函数族表示，对每一个的凸函数族表示，对每一个 ，若，若 ，则有，则有信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5050对数凸函数 为凸集为凸集为凸函数。为凸函数。n定义：函数定义：函数 称为对数凸函数，若函数称为对数凸函数，若函数 满足：满足：n定理：函数定理：函数 的定义域为凸集，且的定义域为凸集，且

19、 ，则，则 为为对数凸函数，当且仅当对对数凸函数，当且仅当对 有有n对数凸函数的例对数凸函数的例信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5151对数凸函数和凹函数的性质n性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。闭。n定理：函数定理：函数 二阶可微，则二阶可微，则 为对数凸函数当且仅为对数凸函数当且仅当当n性质：对数凸性对函数加运算保持封闭。但对数凹性对函数性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。加运算不封闭。n推论：函数推论：函数 对每一个对每一个 在在 上对数凸，则函数上对数凸，则函数

20、也是对数凸函数。也是对数凸函数。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5252对数凸函数和凹函数的性质n定理：函数定理：函数 为对数凹函数，则函为对数凹函数，则函数数 是对数凹函数。是对数凹函数。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5353广义不等式下的凸性n广义单调性的定义：设广义单调性的定义：设 为真锥，函数为真锥，函数 称为称为 单调增，若函数单调增，若函数 满足：满足：n广义凸函数的定义：设广义凸函数的定义：设 为真锥，函数为真锥，函数 称为称为 凸，若函数凸，若函数 满足对满足对 均有均有n定理定理(对偶等价对偶等价)：函数函数 为为 凸函数，当且仅当对

21、所有凸函数，当且仅当对所有 ，为凸函数。为凸函数。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5454作业(1)nP116 3.16nP116 3.21信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5555作业(2)nP121 3.41nP122 3.49 (1)(2)信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5656凸优化理论与应用凸优化理论与应用第三章第三章 凸优化凸优化信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5757优化问题的基本形式n优化问题的基本描述：优化问题的基本描述：优化变量优化变量不等式约束不等式约束等式约束等式约束无约束优化无约束优化信息与

22、通信工程学院信息与通信工程学院 庄伯金庄伯金 5858优化问题的基本形式最优化值最优化值最优化解最优化解 优化问题的域优化问题的域 可行点可行点(解解)(feasible)满足约束条件满足约束条件 可行域可行域(可解集可解集)所有可行点的集合所有可行点的集合信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5959局部最优问题n局部最优问题局部最优问题信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6060优化问题的等价形式(1)n定理：若定理：若 则原优化问题与以下优化问题等价则原优化问题与以下优化问题等价信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6161优化问题的等价形式(

23、2)n定理：设定理：设 为一一对应，且为一一对应，且 则原优化问题与以下优化问题等价则原优化问题与以下优化问题等价信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6262优化问题的等价形式(3)n定理：设定理：设 为严格单调增函数；为严格单调增函数；满满足足 当且仅当当且仅当 ；满足满足 当当且仅当且仅当 。则原优化问题与以下优化问题等价。则原优化问题与以下优化问题等价信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6363优化问题的等价形式(4)n定理：原优化问题与以下优化问题等价定理：原优化问题与以下优化问题等价n 称为松弛变量称为松弛变量信息与通信工程学院信息与通信工程学院 庄伯

24、金庄伯金 6464优化问题的等价形式(5)n定理：设定理：设 满足等式满足等式 成立，当且仅当成立，当且仅当 。则原优化问题与以下优化。则原优化问题与以下优化问题等价问题等价信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6565可分离变量优化问题n性质：性质：其中其中可以分离变量可以分离变量n定理：优化问题定理：优化问题信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6666优化问题的上半图形式信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6767凸优化问题的基本形式n凸优化问题的基本描述：凸优化问题的基本描述：为仿射函数为仿射函数 为凸函数为凸函数 若若 为准凸函数，则优化问

25、题称为准凸优化问题。为准凸函数，则优化问题称为准凸优化问题。性质：凸优化问题的可行域是凸集。性质：凸优化问题的可行域是凸集。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6868凸优化问题的例n例：例：等价于凸优化问题等价于凸优化问题信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6969凸优化问题的局部最优解n定理：凸优化问题的局部最优解均是全局最优解。定理：凸优化问题的局部最优解均是全局最优解。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7070凸优化问题最优解的微分条件n定理：设定理：设 为凸优化问题的可行域，为凸优化问题的可行域，可微。则可微。则 为最优解当且仅当为最

26、优解当且仅当 成立。成立。n定理：非约束凸优化问题中，若定理：非约束凸优化问题中，若 可微。则可微。则 为最为最优解当且仅当优解当且仅当 成立。成立。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7171凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，且存在向量，且存在向量 满足满足 n定理：设凸优化问题仅有等式约束定理：设凸优化问题仅有等式约束信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7272凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，且，且 n定理：设凸优化问题定理：设凸优化问题信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7373凸优

27、化问题的等价形式等价于等价于 n定理：设凸优化问题定理：设凸优化问题其中其中 信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7474凸优化问题的等价形式等价于等价于 n定理：设凸优化问题定理：设凸优化问题信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7575准凸优化问题 为准凸函数，为准凸函数，为凸函数。为凸函数。n准凸优化问题的基本描述准凸优化问题的基本描述n注：准凸优化问题的局部最优解不一定是全局最优解。注：准凸优化问题的局部最优解不一定是全局最优解。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7676准凸优化问题的上半图形式n设设 为准凸函数为准凸函数 的凸函数族表示

28、，即的凸函数族表示，即 则准凸优化问题的可行解问题为则准凸优化问题的可行解问题为n设设 为准凸优化问题的最优解，若上述问题可解，则为准凸优化问题的最优解，若上述问题可解，则 。否则。否则 。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7777准凸优化问题二分法求解n给定一个足够小的给定一个足够小的 和足够大的和足够大的 ，使得区间，使得区间 能包含最优解能包含最优解 。给定。给定nLOOP：n令令n求解可行解问题；求解可行解问题；n若可解，则令若可解，则令 ，否则令，否则令n若若 ，则结束，否则，则结束，否则goto LOOP。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 787

29、8线性规划(linear program,LP)nLP问题的一般描述问题的一般描述信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7979LP问题的几种类型n标准标准LP问题问题n不等式形式不等式形式LP问题问题信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8080标准LP问题的转换信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8181LP问题的例nChebyshev center of a polyhedronnPiecewise-linear minimizationnLinear-fractional programming信息与通信工程学院信息与通信工程学院 庄伯金庄伯

30、金 8282Chebyshev center of a polyhedronn多面体nChebyshev center：到多面体边界距离最大的内点（最深的点）n问题描述nLP形式信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8383Piecewise-linear minimizationn问题描述n上半图形式nLP形式信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8484Linear-fractional programmingn问题描述nLP形式信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8585二次规划(quadratic program,QP)nQP问题的基本描述问

31、题的基本描述信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8686二次约束二次规划nquadratically constrained quadratic program(QCQP)信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8787QP问题的例nLeast-squares and regressionnDistance between polyhedra信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8888Least-squares and regressionn问题描述信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8989Distance between poly

32、hedran问题描述nQP形式信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9090Second-order cone program,SOCPnSOCP问题的基本描述n二次锥约束条件信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9191SOCP问题的例Robust linear programmingn问题描述其中 不是完全确定的常数。n例：为确定的常数，为变量，其范围满足SOCP形式信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9292几何规划(Geometric programming)n单项式与多项式n几何规划的基本描述信息与通信工程学院信息与通信工程学院 庄伯金庄伯

33、金 9393几何规划的凸形式转换n令n几何规划的凸形式信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9494广义不等式约束n广义不等式约束的优化问题nSOCP的描述信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9595凸优化理论与应用凸优化理论与应用第四章第四章 对偶问题对偶问题信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9696优化问题的拉格朗日函数n设优化问题：设优化问题：n拉格朗日拉格朗日(Lagrangian)函数：函数：n对固定的对固定的 ，拉格朗日函数，拉格朗日函数 为关于为关于 和和 的的仿仿射函数射函数。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9

34、797拉格朗日对偶函数n拉格朗日对偶函数拉格朗日对偶函数(lagrange dual function)：若拉格朗日函数没有下界，则令若拉格朗日函数没有下界，则令n拉格朗日对偶函数为拉格朗日对偶函数为凹函数凹函数。n对对 和和 ，若原最优化问题有最优值，若原最优化问题有最优值 ，则，则信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9898对偶函数的例nLeast-squares solution of linear equationsnStandard form LPnTwo-way partitioning problem信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9999Le

35、ast-squares solution of linear equationsn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 100100Standard form LPn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 101101Two-way partitioning problemn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：信息与通信工程学院信息与通信工程学院 庄伯金庄

36、伯金 102102对偶函数与共轭函数n共轭函数共轭函数n共轭函数与对偶函数存在密切联系共轭函数与对偶函数存在密切联系n具有线性不等式约束和线性等式约束的优化问题：具有线性不等式约束和线性等式约束的优化问题：对偶函数：对偶函数：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 103103Equality constrained norm minimizationn问题描述：问题描述：n共轭函数：共轭函数：n对偶函数：对偶函数：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 104104Entropy maximizationn原始问题：原始问题：n共轭函数：共轭函数：n对偶函数对偶函数：

37、信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 105105Minimum volume covering ellipsoidn原始问题：原始问题：n对偶函数：对偶函数：n共轭函数：共轭函数：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 106106拉格朗日对偶问题n拉格朗日对偶问题的描述：拉格朗日对偶问题的描述：n对偶可行域对偶可行域n最优值最优值n最优解最优解信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 107107LP问题的对偶问题n标准标准LP问题问题n对偶函数对偶函数n对偶问题对偶问题n等价描述等价描述信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 108108弱

38、对偶性n定理（弱对偶性）定理（弱对偶性）：设原始问题的最优值为：设原始问题的最优值为 ，对偶问，对偶问题的最优值为题的最优值为 ，则，则 成立。成立。noptimal duality gapn可以利用对偶问题找到原始问题最优解的下界。可以利用对偶问题找到原始问题最优解的下界。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 109109强对偶性n强对偶性并不是总是成立的。强对偶性并不是总是成立的。n定义（强对偶性）定义（强对偶性）：设原始问题的最优值为：设原始问题的最优值为 ，对偶问，对偶问题的最优值为题的最优值为 。若。若 成立，则称原始问题和对成立，则称原始问题和对偶问题之间具有偶问题之

39、间具有强对偶性强对偶性。n凸优化问题凸优化问题通常（但并不总是）通常（但并不总是）具有强对偶性。具有强对偶性。nSlater定理：若凸优化问题存在严格可行解，即存在定理：若凸优化问题存在严格可行解，即存在 ，满足，满足则优化问题具有强对偶性。该条件称为则优化问题具有强对偶性。该条件称为Slater条件条件。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 110110强对偶性存在存在 ，满足，满足n弱化的弱化的Slater条件：若不等式约束条件的前条件：若不等式约束条件的前 个为线性不个为线性不等式约束条件，则等式约束条件，则Slater条件可以弱化为：条件可以弱化为：信息与通信工程学院信息

40、与通信工程学院 庄伯金庄伯金 111111Least-squares solution of linear equationsn原问题：原问题：n对偶问题：对偶问题：n具有强对偶性具有强对偶性信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 112112Lagrange dual of QCQPnQCQP：n拉格朗日函数：拉格朗日函数：n对偶函数：对偶函数：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 113113Lagrange dual of QCQPn对偶问题对偶问题：nSlater条件：存在条件：存在 ，满足，满足信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 114114

41、Entropy maximizationn原始问题：原始问题：n对偶函数：对偶函数：n对偶问题对偶问题：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 115115Entropy maximizationn弱化的弱化的Slater条件：存在条件：存在 ，满足，满足信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 116116Minimum volume covering ellipsoidn原始问题：原始问题：n对偶函数：对偶函数：n对偶问题：对偶问题：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 117117Minimum volume covering ellipsoidn弱化

42、的弱化的Slater条件总成立，因此该优化问题具有强对偶性。条件总成立，因此该优化问题具有强对偶性。n弱化的弱化的Slater条件：存在条件：存在 ，满足，满足信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 118118对偶可行解的不等式对偶可行解的不等式n对于一优化问题，若对于一优化问题，若 为一可行解，为一可行解，为对偶问题可行解，为对偶问题可行解，则有如下不等式：则有如下不等式：为为 次优解，其中次优解，其中n不等式可以用于对次优解的精度估计不等式可以用于对次优解的精度估计信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 119119互补松弛条件互补松弛条件所以所以n设设 为原始优

43、化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则若两者具有强对偶性，则即即信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 120120KKT优化条件优化条件n设优化问题中，函数设优化问题中，函数 可微。设可微。设 为原始优化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，且两者为对偶问题的最优解，且两者具有强对偶性，则具有强对偶性，则 满足如下条件：满足如下条件：KKT条件为条件为必要条件！必要条件！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 121121凸优化问题的凸优化问题的KKT条件条件可微。设可微。设 满足满足

44、KKT条件，则条件，则 为原始问题的最优解，而为原始问题的最优解，而 为对偶问题的最优解，且两者具有强对偶性。为对偶问题的最优解，且两者具有强对偶性。n设原始问题为凸优化问题中，函数设原始问题为凸优化问题中，函数信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 122122例例n原始凸优化问题原始凸优化问题KKT条件条件信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 123123例例其中其中解得解得信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 124124凸优化问题的对偶求解凸优化问题的对偶求解存在唯一解存在唯一解 。若。若 为原始问题的可行解，则为原始问题的可行解，则 即为原始问

45、题即为原始问题的最优解；若的最优解；若 不是原始问题的可行解，则原始问题不存在最不是原始问题的可行解，则原始问题不存在最优解。优解。n设原始优化问题与对偶问题具有强对偶性，且设原始优化问题与对偶问题具有强对偶性，且 为对偶问为对偶问题的最优解。题的最优解。存在唯一的最小解，即存在唯一的最小解，即信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 125125扰动问题扰动问题n扰动问题：扰动问题：n当当 时即为原始问题。时即为原始问题。n若若 为正，则第为正，则第 个不等式约束被放宽；若个不等式约束被放宽；若 为负，则第为负，则第 个个不等式约束被收紧。不等式约束被收紧。n记记 为扰动问题的最优

46、解。若扰动问题无最优解，则记为扰动问题的最优解。若扰动问题无最优解，则记信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 126126灵敏度分析灵敏度分析n设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为问题的最优对偶解为 ，则有，则有n若若 在在 处可微，则处可微，则信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 127127n定义（弱选择性）：若两个不等式（等式）系统，至多有一个可定义（弱选择性）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。解，则称这两个系统具有弱选择性。选择

47、定理选择定理n对偶不等式组对偶不等式组n设原始问题的约束条件：设原始问题的约束条件：n对偶问题对偶问题n原始问题的约束条件与对偶不等式组具有弱选择性。原始问题的约束条件与对偶不等式组具有弱选择性。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 128128选择定理选择定理n对偶不等式组对偶不等式组n设原始问题的严格不等式约束条件：设原始问题的严格不等式约束条件：n原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 129129n定义（强选择性）：若两个不等式（等式）系统，恰有一个

48、可解，定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。则称这两个系统具有强选择性。选择定理选择定理n对偶不等式组对偶不等式组n设原始问题为凸优化问题，其严格不等式约束条件为：设原始问题为凸优化问题，其严格不等式约束条件为：n若存在若存在 ，满足，满足 ，则上述两不等式约束系统，则上述两不等式约束系统具有强选择性。具有强选择性。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 130130选择定理选择定理n对偶不等式组对偶不等式组n设原始问题为凸优化问题，其不等式约束条件为：设原始问题为凸优化问题，其不等式约束条件为：则原始问题的不等式约束条件与对偶不等式

49、组具有强选择性。则原始问题的不等式约束条件与对偶不等式组具有强选择性。n若存在若存在 ，满足，满足 ，且下述优化问题存在最优，且下述优化问题存在最优解解信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 131131罚函数的例n 范数：范数：n死区线性罚函数：死区线性罚函数：n对数门限罚函数对数门限罚函数信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 132132鲁棒的罚函数n若若 大到一定程度时，罚函数为大到一定程度时，罚函数为 的线性函数，则称的线性函数，则称该罚函数为鲁棒的罚函数。该罚函数为鲁棒的罚函数。nHuber罚函数罚函数信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 13

50、3133最小范数问题最小范数问题n问题描述：问题描述：其中其中 为方程组为方程组 的解。的解。n可以消去等式约束将其转换为范数逼近问题：可以消去等式约束将其转换为范数逼近问题：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 134134最小范数问题最小范数问题n最小平方范数问题：范数最小平方范数问题：范数 ，最优解满足：，最优解满足：n最小罚问题：最小罚问题：n绝对值和最小问题：范数绝对值和最小问题：范数 ，原问题可转换为，原问题可转换为LP问问题：题：信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 135135正则逼近正则逼近n二元矢量优化问题描述：二元矢量优化问题描述：n正则化问题