凸优化理论与应用课件

1 1凸优化理论与应用凸优化理论与应用庄 伯 金Bn 1凸优化理论与应用庄 伯 金2 2优化理论概述n什么是优化问题？什么是优化问题？Objective Objective functionfunctionConstraint Constraint functionsfunctionsn 2优化理论概述什么是优化问题？Objective funct3 3几类经典的优化问题n线性规划问题线性规划问题n最小二乘问题最小二乘问题n凸优化问题凸优化问题凸优化问题理论上有凸优化问题理论上有有效的方法进行求解！有效的方法进行求解！n 3几类经典的优化问题线性规划问题最小二乘问题凸优化问题凸优化4 4本课程的主要内容n理论部分理论部分n凸集和凸函数凸集和凸函数n凸优化问题凸优化问题n对偶问题对偶问题n应用部分应用部分n逼近与拟合逼近与拟合n统计估计统计估计n几何问题几何问题n算法部分算法部分n非约束优化方法非约束优化方法n等式约束优化方法等式约束优化方法n内点法内点法n 4本课程的主要内容理论部分5 5n熟悉了解凸优化理论的基本原理和基本方法；熟悉了解凸优化理论的基本原理和基本方法；n掌握实际问题转化为凸优化问题的基本方法；掌握实际问题转化为凸优化问题的基本方法；n掌握最优化问题的经典算法。掌握最优化问题的经典算法。课程要求n 5熟悉了解凸优化理论的基本原理和基本方法；课程要求6 6参考书目nStephen Boyd and Lieven Vandenberghe,Stephen Boyd and Lieven Vandenberghe,“Convex Optimization”,“Convex Optimization”,Cambridge University Cambridge University PressPress.n袁亚湘、孙文瑜，袁亚湘、孙文瑜，“最优化理论与方法最优化理论与方法”，科学出版，科学出版社，社，19991999。n 6参考书目Stephen Boyd and Lieven V7 7凸优化理论与应用凸优化理论与应用第一章第一章凸集凸集n 7凸优化理论与应用第一章8 8仿射集(Affine sets)n直线的表示：直线的表示：n线段的表示：线段的表示：n 8仿射集(Affine sets)直线的表示：线段的表示：9 9仿射集(Affine sets)n仿射集的定义：过集合仿射集的定义：过集合C C内任意两点的直线均在集合内任意两点的直线均在集合C C内，则称集合内，则称集合C C为仿射集。为仿射集。n仿射集的例：直线、平面、超平面仿射集的例：直线、平面、超平面n 9仿射集(Affine sets)仿射集的定义：过集合C内任1010仿射集n仿射包：包含集合仿射包：包含集合C C的最小的仿射集。的最小的仿射集。n仿射维数：仿射包的维数。仿射维数：仿射包的维数。n 10仿射集仿射包：包含集合C的最小的仿射集。仿射维数：仿射包1111仿射集n内点（内点（interior）：）：n相对内点（相对内点（relative interior）：）：n 11仿射集内点（interior）：相对内点（relativ1212凸集(Convex Sets)n凸集的定义：集合凸集的定义：集合C C内任意两点间的线段均在集合内任意两点间的线段均在集合C C内，内，则称集合则称集合C C为凸集。为凸集。n 12凸集(Convex Sets)凸集的定义：集合C内任意两1313凸集n凸包的定义：包含集合凸包的定义：包含集合C C的最小的凸集。的最小的凸集。n 13凸集凸包的定义：包含集合C的最小的凸集。1414锥(Cones)n锥的定义：锥的定义：n凸锥的定义：集合凸锥的定义：集合C C既是凸集又是锥。既是凸集又是锥。n锥包的定义：集合锥包的定义：集合C C内点的所有锥组合。内点的所有锥组合。n 14锥(Cones)锥的定义：凸锥的定义：集合C既是凸集又是1515超平面和半空间n超平面超平面(hyperplane)hyperplane)：n半空间半空间(Halfspace)Halfspace)：n 15超平面和半空间超平面(hyperplane)：半空间(1616欧氏球和椭球n欧氏球欧氏球(euclidean ball):euclidean ball):n椭球椭球(ellipsoid):ellipsoid):n 16欧氏球和椭球欧氏球(euclidean ball):椭球1717范数球和范数锥n范数范数(norm)(norm)：n范数球范数球(norm ball)(norm ball)：n范数锥范数锥(norm cone)(norm cone)：n 17范数球和范数锥范数(norm)：范数球(norm bal1818多面体(Polyhedra)n多面体：多面体：n单纯形单纯形(simplex)：n 18多面体(Polyhedra)多面体：单纯形(simple1919半正定锥(Positive semidefinite cone)nn n阶对称矩阵集：阶对称矩阵集：nn n阶半正定矩阵集：阶半正定矩阵集：nn n阶正定矩阵集：阶正定矩阵集：n n阶半正定矩阵集为阶半正定矩阵集为凸锥！凸锥！n 19半正定锥(Positive semidefinite c2020保持凸性的运算n集合交运算集合交运算n仿射变换仿射变换n透视透视/投射函数投射函数(perspective function)n 20保持凸性的运算集合交运算2121保持凸性的运算n线性分式函数线性分式函数(linear-fractional function)n 21保持凸性的运算线性分式函数(linear-fractio2222真锥(proper cone)n真锥的定义：锥真锥的定义：锥 满足如下条件满足如下条件K K具有内点具有内点K K内不含直线内不含直线n 22真锥(proper cone)真锥的定义：锥 2323广义不等式n真锥真锥 下的下的偏序关系偏序关系：n例：例：n逐项不等式逐项不等式n矩阵不等式矩阵不等式广义不等式广义不等式严格广义不等式严格广义不等式n 23广义不等式真锥 下的偏序关系：例：广义不等式严格广2424广义不等式的性质n 24广义不等式的性质2525严格广义不等式的性质n 25严格广义不等式的性质2626最值和极值n最小元的定义：设最小元的定义：设 ，对，对 ，都有，都有 成立，则称成立，则称 为为 的最小元。的最小元。n极小元的定义：设极小元的定义：设 ，对于，对于 ，若，若 ，则，则 成立，则称成立，则称 为为 的极小元。的极小元。n 26最值和极值最小元的定义：设 ，对 2727分割超平面(separating hyperplane)n定理：设定理：设 和和 为两不相交凸集，则存在超平面将为两不相交凸集，则存在超平面将 和和 分离。即：分离。即：n 27分割超平面(separating hyperplane)2828支撑超平面(supporting hyperplane)n定义：设集合定义：设集合 ，为为 边界上的点。若存在边界上的点。若存在 ，满足对任意满足对任意 ，都有，都有 成立，则称超平成立，则称超平面面 为集合为集合 在点在点 处的支撑超平面。处的支撑超平面。n定理：凸集边界上任意一点均存在支撑超平面。定理：凸集边界上任意一点均存在支撑超平面。n定理：若一个闭的非中空集合，在边界上的任意一点定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。存在支撑超平面，则该集合为凸集。n 28支撑超平面(supporting hyperplane)2929对偶锥(dual cone)n对偶锥的定义：设对偶锥的定义：设 为锥，则集合为锥，则集合 称为对偶锥。称为对偶锥。n对偶锥的性质：对偶锥的性质：真锥的对偶锥仍真锥的对偶锥仍然是真锥！然是真锥！n 29对偶锥(dual cone)对偶锥的定义：设 为锥，3030对偶广义不等式n广义不等式与对偶等价性质广义不等式与对偶等价性质n最小元的对偶特性：最小元的对偶特性：n 30对偶广义不等式广义不等式与对偶等价性质最小元的对偶特性：3131对偶广义不等式n极小元的对偶特性极小元的对偶特性反过来不一定成反过来不一定成立！立！n 31对偶广义不等式极小元的对偶特性反过来不一定成立！3232作业nP60 2.8P60 2.8nP60 2.10P60 2.10nP60 2.14P60 2.14nP62 P62 2.162.16nP62 2.18P62 2.18nP64 2.30P64 2.30nP64 2.31P64 2.31nP64 2.33P64 2.33n 32作业P60 2.83333凸优化理论与应用凸优化理论与应用第二章第二章 凸函数凸函数n 33凸优化理论与应用第二章 凸函数3434凸函数的定义1.定义域定义域 为凸集；为凸集；2.，有，有n凸函数的定义：函数凸函数的定义：函数 ，满足，满足n凸函数的扩展定义：若凸函数的扩展定义：若 为凸函数，则可定义其扩为凸函数，则可定义其扩展函数展函数 为为凸函数的凸函数的扩展函数扩展函数也是凸函也是凸函数！数！n 34凸函数的定义1.定义域 为凸集；2.3535凸函数的一阶微分条件n若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 一阶可微，一阶可微，则函数则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对n 35凸函数的一阶微分条件若函数 的定义域 3636凸函数的二阶微分条件n若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 二阶可微，二阶可微，则函数则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对 ，其，其Hessian矩阵矩阵n 36凸函数的二阶微分条件若函数 的定义域 3737凸函数的例n幂函数幂函数n负对数函数负对数函数n负熵函数负熵函数n范数函数范数函数n指数函数指数函数n 37凸函数的例幂函数负对数函数负熵函数范数函数指数函数3838凸函数的例n 38凸函数的例3939下水平集(sublevel set)n定理：凸函数的任一下水平集均为凸集。定理：凸函数的任一下水平集均为凸集。n任一下水平集均为凸集的函数任一下水平集均为凸集的函数不一定不一定为凸函数。为凸函数。称为称为 的的 下水平集。下水平集。n定义：集合定义：集合n 39下水平集(sublevel set)定理：凸函数的任一下4040函数上半图(epigraph)n定理：函数定理：函数 为凸函数为凸函数当且仅当当且仅当 的上半图为凸集。的上半图为凸集。称为函数称为函数 的上半图。的上半图。n定义：集合定义：集合n 40函数上半图(epigraph)定理：函数 为凸函数4141Jensen不等式n 为凸函数，则有：为凸函数，则有：nJensen不等式的另外形式：不等式的另外形式：n 41Jensen不等式 为凸函数，则有：Jensen不等4242保持函数凸性的算子n凸函数的逐点最大值凸函数的逐点最大值n凸函数与仿射变换的复合凸函数与仿射变换的复合n凸函数的非负加权和凸函数的非负加权和n 42保持函数凸性的算子凸函数的逐点最大值凸函数与仿射变换的复4343保持函数凸性的算子n复合运算复合运算n最小值算子最小值算子n凸函数的透视算子凸函数的透视算子n 43保持函数凸性的算子复合运算最小值算子凸函数的透视算子4444共轭函数(conjugate function)n定义：设函数定义：设函数 ，其共轭函数，其共轭函数 ，定义为，定义为n共轭函数的例共轭函数的例共轭函数共轭函数具有凸性！具有凸性！n 44共轭函数(conjugate function)定义：设4545共轭函数的性质nFenchels inequalityn性质：若性质：若 为凸函数，且为凸函数，且 的上半图是闭集，则有的上半图是闭集，则有n性质：设性质：设 为凸函数，且可微，对于为凸函数，且可微，对于 ，若，若则则n 45共轭函数的性质Fenchels inequality性4646准凸函数(quasiconvex function)n准凸函数的例准凸函数的例n定义：设函数定义：设函数 ，若函数的定义域和任意下水，若函数的定义域和任意下水平集平集则称函数则称函数 为准凸函数。为准凸函数。n 46准凸函数(quasiconvex function)准凸4747准凸函数的判定定理n定理：函数定理：函数 为准凸函数，当且仅当为准凸函数，当且仅当 为凸集，且为凸集，且对对 ，有，有n定理：若函数定理：若函数 一阶可微，则一阶可微，则 为准凸函数，当且仅为准凸函数，当且仅当当 为凸集，且对为凸集，且对 ，有，有 ，有，有n定理：若函数定理：若函数 二阶可微，且满足对二阶可微，且满足对则函数则函数 准凸函数。准凸函数。n 47准凸函数的判定定理定理：函数 为准凸函数，4848n最小值函数最小值函数n非负权值函数的最大值函数非负权值函数的最大值函数保持准凸性的算子n复合函数复合函数n 48最小值函数非负权值函数的最大值函数保持准凸性的算子复合函4949准凸函数的凸函数族表示n若若 为准凸函数，根据为准凸函数，根据 的任意的任意 下水平集，我们下水平集，我们可以构造一个凸函数族可以构造一个凸函数族 ，使得，使得n性质：若性质：若 为准凸函数为准凸函数 的凸函数族表示，对每一个的凸函数族表示，对每一个 ，若，若 ，则有，则有n 49准凸函数的凸函数族表示若 为准凸函数，根5050对数凸函数 为凸集为凸集为凸函数。为凸函数。n定义：函数定义：函数 称为对数凸函数，若函数称为对数凸函数，若函数 满足：满足：n定理：函数定理：函数 的定义域为凸集，且的定义域为凸集，且 ，则，则 为为对数凸函数，当且仅当对对数凸函数，当且仅当对 有有n对数凸函数的例对数凸函数的例n 50对数凸函数 为凸集为凸函数5151对数凸函数和凹函数的性质n性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。闭。n定理：函数定理：函数 二阶可微，则二阶可微，则 为对数凸函数当且仅为对数凸函数当且仅当当n性质：对数凸性对函数加运算保持封闭。但对数凹性对函数性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。加运算不封闭。n推论：函数推论：函数 对每一个对每一个 在在 上对数凸，则函数上对数凸，则函数 也是对数凸函数。也是对数凸函数。n 51对数凸函数和凹函数的性质性质：对数凸性与凹性对函数乘积和5252对数凸函数和凹函数的性质n定理：函数定理：函数 为对数凹函数，则函为对数凹函数，则函数数 是对数凹函数。是对数凹函数。n 52对数凸函数和凹函数的性质定理：函数 5353广义不等式下的凸性n广义单调性的定义：设广义单调性的定义：设 为真锥，函数为真锥，函数 称为称为 单调增，若函数单调增，若函数 满足：满足：n广义凸函数的定义：设广义凸函数的定义：设 为真锥，函数为真锥，函数 称为称为 凸，若函数凸，若函数 满足对满足对 均有均有n定理定理(对偶等价对偶等价)：函数函数 为为 凸函数，当且仅当对所有凸函数，当且仅当对所有 ，为凸函数。为凸函数。n 53广义不等式下的凸性广义单调性的定义：设 5454作业(1)nP116 3.16P116 3.16nP116 3.21P116 3.21n 54作业(1)P116 3.165555作业(2)nP121 3.41P121 3.41nP122 3.49 (1)(2)P122 3.49 (1)(2)n 55作业(2)P121 3.415656凸优化理论与应用凸优化理论与应用第三章第三章 凸优化凸优化n 56凸优化理论与应用第三章 凸优化5757优化问题的基本形式n优化问题的基本描述：优化问题的基本描述：优化变量优化变量不等式约束不等式约束等式约束等式约束无约束优化无约束优化n 57优化问题的基本形式优化问题的基本描述：优化变量不等式约束5858优化问题的基本形式最优化值最优化值最优化解最优化解 优化问题的域优化问题的域 可行点可行点(解解)(feasible)满足约束条件满足约束条件 可行域可行域(可解集可解集)所有可行点的集合所有可行点的集合n 58优化问题的基本形式最优化值最优化解 优化问题的域5959局部最优问题n局部最优问题局部最优问题n 59局部最优问题局部最优问题6060优化问题的等价形式(1)n定理：若定理：若 则原优化问题与以下优化问题等价则原优化问题与以下优化问题等价n 60优化问题的等价形式(1)定理：若 则原优化问题与以下6161优化问题的等价形式(2)n定理：设定理：设 为一一对应，且为一一对应，且 则原优化问题与以下优化问题等价则原优化问题与以下优化问题等价n 61优化问题的等价形式(2)定理：设 6262优化问题的等价形式(3)n定理：设定理：设 为严格单调增函数；为严格单调增函数；满满足足 当且仅当当且仅当 ；满足满足 当当且仅当且仅当 。则原优化问题与以下优化问题等价。则原优化问题与以下优化问题等价n 62优化问题的等价形式(3)定理：设 6363优化问题的等价形式(4)n定理：原优化问题与以下优化问题等价定理：原优化问题与以下优化问题等价n 称为松弛变量称为松弛变量n 63优化问题的等价形式(4)定理：原优化问题与以下优化问题等6464优化问题的等价形式(5)n定理：设定理：设 满足等式满足等式 成立，当且仅当成立，当且仅当 。则原优化问题与以下优化。则原优化问题与以下优化问题等价问题等价n 64优化问题的等价形式(5)定理：设 6565可分离变量优化问题n性质：性质：其中其中可以分离变量可以分离变量n定理：优化问题定理：优化问题n 65可分离变量优化问题性质：其中可以分离变量定理：优化问6666优化问题的上半图形式n 66优化问题的上半图形式6767凸优化问题的基本形式n凸优化问题的基本描述：凸优化问题的基本描述：为仿射函数为仿射函数 为凸函数为凸函数 若若 为准凸函数，则优化问题称为准凸优化问题。为准凸函数，则优化问题称为准凸优化问题。性质：凸优化问题的可行域是凸集。性质：凸优化问题的可行域是凸集。n 67凸优化问题的基本形式凸优化问题的基本描述：6868凸优化问题的例n例：例：等价于凸优化问题等价于凸优化问题n 68凸优化问题的例例：等价于凸优化问题6969凸优化问题的局部最优解n定理：凸优化问题的局部最优解均是全局最优解。定理：凸优化问题的局部最优解均是全局最优解。n 69凸优化问题的局部最优解定理：凸优化问题的局部最优解均是全7070凸优化问题最优解的微分条件n定理：设定理：设 为凸优化问题的可行域，为凸优化问题的可行域，可微。可微。则则 为最优解当且仅当为最优解当且仅当 成立。成立。n定理：非约束凸优化问题中，若定理：非约束凸优化问题中，若 可微。则可微。则 为最为最优解当且仅当优解当且仅当 成立。成立。n 70凸优化问题最优解的微分条件定理：设 为凸优化问题的7171凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，且存在向量，且存在向量 满足满足 n定理：设凸优化问题仅有等式约束定理：设凸优化问题仅有等式约束n 71凸优化问题的等价形式 则 为最优解当且仅当 7272凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，且，且 n定理：设凸优化问题定理：设凸优化问题n 72凸优化问题的等价形式 则 为最优解当且仅当 7373凸优化问题的等价形式等价于等价于 n定理：设凸优化问题定理：设凸优化问题其中其中 n 73凸优化问题的等价形式 等价于 定理：设凸优化问7474凸优化问题的等价形式等价于等价于 n定理：设凸优化问题定理：设凸优化问题n 74凸优化问题的等价形式 等价于 定理：设凸优化问7575准凸优化问题 为准凸函数，为准凸函数，为凸函数。为凸函数。n准凸优化问题的基本描述准凸优化问题的基本描述n注：准凸优化问题的局部最优解不一定是全局最优解。注：准凸优化问题的局部最优解不一定是全局最优解。n 75准凸优化问题 为准凸函数，7676准凸优化问题的上半图形式n设设 为准凸函数为准凸函数 的凸函数族表示，即的凸函数族表示，即 则准凸优化问题的可行解问题为则准凸优化问题的可行解问题为n设设 为准凸优化问题的最优解，若上述问题可解，则为准凸优化问题的最优解，若上述问题可解，则 。否则。否则 。n 76准凸优化问题的上半图形式设 为准凸函数 7777准凸优化问题二分法求解n给定一个足够小的给定一个足够小的 和足够大的和足够大的 ，使得区间，使得区间 能包含最优解能包含最优解 。给定。给定nLOOP：n令令n求解可行解问题；求解可行解问题；n若可解，则令若可解，则令 ，否则令，否则令n若若 ，则结束，否则，则结束，否则goto LOOP。n 77准凸优化问题二分法求解给定一个足够小的 和足够大的 7878线性规划(linear program,LP)nLP问题的一般描述问题的一般描述n 78线性规划(linear program,LP)LP问题的7979LP问题的几种类型n标准标准LP问题问题n不等式形式不等式形式LP问题问题n 79LP问题的几种类型标准LP问题不等式形式LP问题8080标准LP问题的转换n 80标准LP问题的转换8181LP问题的例nChebyshev center of a polyhedronnPiecewise-linear minimizationnLinear-fractional programmingn 81LP问题的例Chebyshev center of a 8282Chebyshev center of a polyhedronn多面体nChebyshev center：到多面体边界距离最大的内点（最深的点）n问题描述nLP形式n 82Chebyshev center of a polyhe8383Piecewise-linear minimizationn问题描述n上半图形式nLP形式n 83Piecewise-linear minimizatio8484Linear-fractional programmingn问题描述nLP形式n 84Linear-fractional programmin8585二次规划(quadratic program,QP)nQP问题的基本描述问题的基本描述n 85二次规划(quadratic program,QP)QP8686二次约束二次规划nquadratically constrained quadratic program(QCQP)n 86二次约束二次规划quadratically constr8787QP问题的例nLeast-squares and regressionnDistance between polyhedran 87QP问题的例Least-squares and regr8888Least-squares and regressionn问题描述n 88Least-squares and regression8989Distance between polyhedran问题描述nQP形式n 89Distance between polyhedra问题9090Second-order cone program,SOCPnSOCP问题的基本描述n二次锥约束条件n 90Second-order cone program,S9191SOCP问题的例Robust linear programmingn问题描述其中 不是完全确定的常数。n例：为确定的常数，为变量，其范围满足SOCP形式n 91SOCP问题的例Robust linear progr9292几何规划(Geometric programming)n单项式与多项式n几何规划的基本描述n 92几何规划(Geometric programming)单9393几何规划的凸形式转换n令n几何规划的凸形式n 93几何规划的凸形式转换令几何规划的凸形式9494广义不等式约束n广义不等式约束的优化问题nSOCP的描述n 94广义不等式约束广义不等式约束的优化问题SOCP的描述9595凸优化理论与应用凸优化理论与应用第四章第四章 对偶问题对偶问题n 95凸优化理论与应用第四章 对偶问题9696优化问题的拉格朗日函数n设优化问题：设优化问题：n拉格朗日拉格朗日(Lagrangian)函数：函数：n对固定的对固定的 ，拉格朗日函数，拉格朗日函数 为关于为关于 和和 的的仿仿射函数射函数。n 96优化问题的拉格朗日函数设优化问题：拉格朗日(Lagran9797拉格朗日对偶函数n拉格朗日对偶函数拉格朗日对偶函数(lagrange dual function)：若拉格朗日函数没有下界，则令若拉格朗日函数没有下界，则令n拉格朗日对偶函数为拉格朗日对偶函数为凹函数凹函数。n对对 和和 ，若原最优化问题有最优值，若原最优化问题有最优值 ，则，则n 97拉格朗日对偶函数拉格朗日对偶函数(lagrange du9898对偶函数的例nLeast-squares solution of linear equationsLeast-squares solution of linear equationsnStandard form LPStandard form LPnTwo-way partitioning problemTwo-way partitioning problemn 98对偶函数的例Least-squares solution9999Least-squares solution of linear equationsLeast-squares solution of linear equationsn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：n 99Least-squares solution of li100100Standard form LPStandard form LPn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：n 100Standard form LP原问题：拉格朗日函数：101101Two-way partitioning problemTwo-way partitioning problemn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：n 101Two-way partitioning proble102102对偶函数与共轭函数n共轭函数共轭函数n共轭函数与对偶函数存在密切联系共轭函数与对偶函数存在密切联系n具有线性不等式约束和线性等式约束的优化问题：具有线性不等式约束和线性等式约束的优化问题：对偶函数：对偶函数：n 102对偶函数与共轭函数共轭函数共轭函数与对偶函数存在密切联103103Equality constrained norm minimizationEquality constrained norm minimizationn问题描述：问题描述：n共轭函数：共轭函数：n对偶函数：对偶函数：n 103Equality constrained norm m104104Entropy maximizationn原始问题：原始问题：n共轭函数：共轭函数：n对偶函数对偶函数：n 104Entropy maximization原始问题：共轭105105Minimum volume covering ellipsoidMinimum volume covering ellipsoidn原始问题：原始问题：n对偶函数：对偶函数：n共轭函数：共轭函数：n 105Minimum volume covering ell106106拉格朗日对偶问题n拉格朗日对偶问题的描述：拉格朗日对偶问题的描述：n对偶可行域对偶可行域n最优值最优值n最优解最优解n 106拉格朗日对偶问题拉格朗日对偶问题的描述：对偶可行域最优107107LP问题的对偶问题n标准标准LP问题问题n对偶函数对偶函数n对偶问题对偶问题n等价描述等价描述n 107LP问题的对偶问题标准LP问题对偶函数对偶问题等价描述108108弱对偶性n定理（弱对偶性）定理（弱对偶性）：设原始问题的最优值为：设原始问题的最优值为 ，对偶问，对偶问题的最优值为题的最优值为 ，则，则 成立。成立。noptimal duality gapn可以利用对偶问题找到原始问题最优解的下界。可以利用对偶问题找到原始问题最优解的下界。n 108弱对偶性定理（弱对偶性）：设原始问题的最优值为 109109强对偶性n强对偶性并不是总是成立的。强对偶性并不是总是成立的。n定义（强对偶性）定义（强对偶性）：设原始问题的最优值为：设原始问题的最优值为 ，对偶问，对偶问题的最优值为题的最优值为 。若。若 成立，则称原始问题和对成立，则称原始问题和对偶问题之间具有偶问题之间具有强对偶性强对偶性。n凸优化问题凸优化问题通常（但并不总是）通常（但并不总是）具有强对偶性。具有强对偶性。nSlater定理：若凸优化问题存在严格可行解，即存在定理：若凸优化问题存在严格可行解，即存在 ，满足，满足则优化问题具有强对偶性。该条件称为则优化问题具有强对偶性。该条件称为Slater条件条件。n 109强对偶性强对偶性并不是总是成立的。定义（强对偶性）：110110强对偶性存在存在 ，满足，满足n弱化的弱化的Slater条件：若不等式约束条件的前条件：若不等式约束条件的前 个为线性不个为线性不等式约束条件，则等式约束条件，则Slater条件可以弱化为：条件可以弱化为：n 110强对偶性存在 ，满111111Least-squares solution of linear equationsLeast-squares solution of linear equationsn原问题：原问题：n对偶问题：对偶问题：n具有强对偶性具有强对偶性n 111Least-squares solution of l112112Lagrange dual of QCQPnQCQP：n拉格朗日函数：拉格朗日函数：n对偶函数：对偶函数：n 112Lagrange dual of QCQPQCQP：拉113113Lagrange dual of QCQPn对偶问题对偶问题：nSlater条件：存在条件：存在 ，满足，满足n 113Lagrange dual of QCQP对偶问题：S114114Entropy maximizationn原始问题：原始问题：n对偶函数：对偶函数：n对偶问题对偶问题：n 114Entropy maximization原始问题：对偶115115Entropy maximizationn弱化的弱化的Slater条件：存在条件：存在 ，满足，满足n 115Entropy maximization弱化的Slat116116Minimum volume covering ellipsoidMinimum volume covering ellipsoidn原始问题：原始问题：n对偶函数：对偶函数：n对偶问题：对偶问题：n 116Minimum volume covering ell117117Minimum volume covering ellipsoidMinimum volume covering ellipsoidn弱化的弱化的SlaterSlater条件总成立，因此该优化问题具有强对偶性。条件总成立，因此该优化问题具有强对偶性。n弱化的弱化的Slater条件：存在条件：存在 ，满足，满足n 117Minimum volume covering ell118118对偶可行解的不等式对偶可行解的不等式n对于一优化问题，若对于一优化问题，若 为一可行解，为一可行解，为对偶问题可行解，为对偶问题可行解，则有如下不等式：则有如下不等式：为为 次优解，其中次优解，其中n不等式可以用于对次优解的精度估计不等式可以用于对次优解的精度估计n 118对偶可行解的不等式对于一优化问题，若 为一可行解119119互补松弛条件互补松弛条件所以所以n设设 为原始优化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则若两者具有强对偶性，则即即n 119互补松弛条件所以设 为原始优化问题的最优解，120120KKTKKT优化条件优化条件n设优化问题中，函数设优化问题中，函数 可微。设可微。设 为原始优化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，且两者为对偶问题的最优解，且两者具有强对偶性，则具有强对偶性，则 满足如下条件：满足如下条件：KKTKKT条件为条件为必要条件！必要条件！n 120KKT优化条件设优化问题中，函数 121121凸优化问题的凸优化问题的KKTKKT条件条件可微。设可微。设 满足满足KKT条件，则条件，则 为原始问题的最优解，而为原始问题的最优解，而 为对偶问题的最优解，且两者具有强对偶性。为对偶问题的最优解，且两者具有强对偶性。n设原始问题为凸优化问题中，函数设原始问题为凸优化问题中，函数n 121凸优化问题的KKT条件可微。设 122122例例n原始凸优化问题原始凸优化问题KKT条件条件n 122例原始凸优化问题KKT条件123123例例其中其中解得解得n 123例其中解得124124凸优化问题的对偶求解凸优化问题的对偶求解存在唯一解存在唯一解 。若。若 为原始问题的可行解，则为原始问题的可行解，则 即为原始问题即为原始问题的最优解；若的最优解；若 不是原始问题的可行解，则原始问题不存在最不是原始问题的可行解，则原始问题不存在最优解。优解。n设原始优化问题与对偶问题具有强对偶性，且设原始优化问题与对偶问题具有强对偶性，且 为对偶问为对偶问题的最优解。题的最优解。存在唯一的最小解，即存在唯一的最小解，即n 124凸优化问题的对偶求解存在唯一解 。若 125125扰动问题扰动问题n扰动问题：扰动问题：n当当 时即为原始问题。时即为原始问题。n若若 为正，则第为正，则第 个不等式约束被放宽；若个不等式约束被放宽；若 为负，则第为负，则第 个个不等式约束被收紧。不等式约束被收紧。n记记 为扰动问题的最优解。若扰动问题无最优解，则记为扰动问题的最优解。若扰动问题无最优解，则记n 125扰动问题扰动问题：当 126126灵敏度分析灵敏度分析n设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为问题的最优对偶解为 ，则有，则有n若若 在在 处可微，则处可微，则n 126灵敏度分析设对偶问题存在最优解，且与原始问题具有强对偶127127n定义（弱选择性）：若两个不等式（等式）系统，至多有一个可定义（弱选择性）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。解，则称这两个系统具有弱选择性。选择定理选择定理n对偶不等式组对偶不等式组n设原始问题的约束条件：设原始问题的约束条件：n对偶问题对偶问题n原始问题的约束条件与对偶不等式组具有弱选择性。原始问题的约束条件与对偶不等式组具有弱选择性。n 127定义（弱选择性）：若两个不等式（等式）系统，至多有一个128128选择定理选择定理n对偶不等式组对偶不等式组n设原始问题的严格不等式约束条件：设原始问题的严格不等式约束条件：n原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。n 128选择定理对偶不等式组设原始问题的严格不等式约束条件：原129129n定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。则称这两个系统具有强选择性。选择定理选择定理n对偶不等式组对偶不等式组n设原始问题为凸优化问题，其严格不等式约束条件为：设原始问题为凸优化问题，其严格不等式约束条件为：n若存在若存在 ，满足，满足 ，则上述两不等式约束系统，则上述两不等式约束系统具有强选择性。具有强选择性。n 129定义（强选择性）：若两个不等式（等式）系统，恰有一个可130130选择定理选择定理n对偶不等式组对偶不等式组n设原始问题为凸优化问题，其不等式约束条件为：设原始问题为凸优化问题，其不等式约束条件为：则原始问题的不等式约束条件与对偶不等式组具有强选择性。则原始问题的不等式约束条件与对偶不等式组具有强选择性。n若存在若存在 ，满足，满足 ，且下述优化问题存在最优，且下述优化问题存在最优解解n 130选择定理对偶不等式组设原始问题为凸优化问题，其不等式约131131罚函数的例n 范数：范数：n死区线性罚函数：死区线性罚函数：n对数门限罚函数对数门限罚函数n 131罚函数的例 范数：死区线性132132鲁棒的罚函数n若若 大到一定程度时，罚函数为大到一定程度时，罚函数为 的线性函数，的线性函数，则称该罚函数为鲁棒的罚函数。则称该罚函数为鲁棒的罚函数。nHuberHuber罚函数罚函数n 132鲁棒的罚函数若 大到一定程度时，罚函数为 133133最小范数问题最小范数问题n问题描述：问题描述：其中其中 为方程组为方程组 的解。的解。n可以消去等式约束将其转换为范数逼近问题：可以消去等式约束将其转换为范数逼近问题：n 133最小范数问题问题描述：其中 为方程134134最小范数问题最小范数问题n最小平方范数问题：范数最小平方范数问题：范数 ，最优解满足：，最优解满足：n最小罚问题：最小罚问题：n绝对值和最小问题：范数绝对值和最小问题：范数 ，原问题可转换为，原问题可转换为LPLP问题：问题：n 134最小范数问题最小平方范数问题：范数 ，最135135正则逼近正则逼近n二元矢量优化问题描述：二元矢量优化问题描述：n正则化问题：正则化问题：最优解描述了两分量的一条折中曲线。最优解描述了两分量的一条折中曲线。n 135正则逼近二元矢量优化问题描述：正则化问题：最优解描述136136正则逼近正则逼近nTikhonovTikhonov正则化问题：正则化问题：为二次优化问题：为二次优化问题：最优解的形式最优解的形式：n 136正则逼近Tikhonov正则化问题：为二次优化问题：137137正则逼近正则逼近nTikhonovTikhonov光滑正则化问题：光滑正则化问题：为二阶差分算子：为二阶差分算子：n 137正则逼近Tikhonov光滑正则化问题：为138138信号复原信号复原n已知加噪信号：已知加噪信号：信号复原问题的描述：信号复原问题的描述：函数函数 为正则函数或光滑函数。为正则函数或光滑函数。n 138信号复原已知加噪信号：信号复原问题的描述：函数 139139信号复原信号复原n 139信号复原140140信号复原信号复原n 140信号复原141141信号复原信号复原n 141信号复原142142鲁棒逼近鲁棒逼近n问题描述：问题描述：n随机鲁棒逼近：随机鲁棒逼近：为随机变量，逼近问题转换为最小为随机变量，逼近问题转换为最小化期望化期望n例：例：随机鲁棒逼近为：随机鲁棒逼近为：转换为转换为：n 142鲁棒逼近问题描述：随机鲁棒逼近：为随机变量，逼近143143随机鲁棒逼近随机鲁棒逼近n 为随机变量：为随机变量：最小平方随机鲁棒逼近为：最小平方随机鲁棒逼近为：转换为转换为：其中其中n 143随机鲁棒逼近 为随机变量：最小平方随机鲁棒逼144144最坏情况鲁棒逼近最坏情况鲁棒逼近n考虑考虑 ，最坏情况鲁棒逼近为：，最坏情况鲁棒逼近为：n例：例：随机鲁棒逼近为：随机鲁棒逼近为：转换为转换为：n 144最坏情况鲁棒逼近考虑 ，最坏情况145145凸优化理论与应用凸优化理论与应用第第6 6章章 统计估计统计估计n 145凸优化理论与应用第6章 统计估计146146概率分布的参数估计n随机变量的概率密度为随机变量的概率密度为 ，其中，其中 为概率分布的为概率分布的参数，且参数未知。参数估计的目标就是通过一些已知参数，且参数未知。参数估计的目标就是通过一些已知样本估计获得参数的最优近似值。样本估计获得参数的最优近似值。n问题描述问题描述n 为样本观测值；为样本观测值；n 为对数似然函数；为对数似然函数；n若似然函数为凹函数，则优化问题为凸优化问题。若似然函数为凹函数，则优化问题为凸优化问题。n 146概率分布的参数估计随机变量的概率密度为 147147具有独立同分布噪声的线性测量n线性测量模型：线性测量模型：n 为观测值或测量值；为观测值或测量值；n 为未知参数向量；为未知参数向量；n 独立同分布噪声，其概率密度为独立同分布噪声，其概率密度为 。n似然函数为似然函数为n最大似然估计问题为：最大似然估计问题为：n 147具有独立同分布噪声的线性测量线性测量模型：为观148148例例n高斯白噪声高斯白噪声对数似然函数：对数似然函数：n区间区间 上均匀分布的噪声：上均匀分布的噪声：对数似然函数：对数似然函数：n 148例高斯白噪声对数似然函数：区间 149149逻辑回归n随机变量随机变量 的概率分布为：的概率分布为：n 为参数；为参数；n 为可观测的解释变量；为可观测的解释变量；为观察值。为观察值。对数似然函数对数似然函数：n 149逻辑回归随机变量 的概率分布150150假定测验n随机变量随机变量 ，有，有 种可能（假定）种可能（假定）的分布；的分布；n假定假定 ：的概率分布为的概率分布为n假定测验的目标：由观察值猜测随机变量最有可能服从假定测验的目标：由观察值猜测随机变量最有可能服从哪种假定的分布。哪种假定的分布。n当当 时，称为二元假定测验。时，称为二元假定测验。n随机检测子：非负元素矩阵随机检测子：非负元素矩阵 n 150假定测验随机变量 151151假定测验n 为当为当 实际服从第实际服从第1 1种假定分布而猜测为第种假定分布而猜测为第2 2种种假定分布的概率；假定分布的概率；n 为当为当 实际服从第实际服从第2 2种假定分布而猜测为第种假定分布而猜测为第1 1种种假定分布的概率；假定分布的概率；n多目标优化形式多目标优化形式：n检测概率矩阵检测概率矩阵n 151假定测验 为当 实际服从第1种假定分布而152152假定测验n最小最大值形式最小最大值形式n尺度优化形式：尺度优化形式：n 152假定测验最小最大值形式尺度优化形式：153153例例n 在两种假设下的概率分布为：在两种假设下的概率分布为：n 153例 在两种假设下的概率分布为：154154例例n 154例155155实验设计实验设计n线性测量问题线性测量问题n最大似然估计值：最大似然估计值：n 独立同分布高斯白噪声，服从分布独立同分布高斯白噪声，服从分布 。n估计误差估计误差 均值为均值为0 0，方差为，方差为信赖椭圆为信赖椭圆为n 155实验设计线性测量问题最大似然估计值：独立同分布156156实验设计实验设计n实验设计的目标：寻找实验设计的目标：寻找 ，使得误，使得误差的方差矩阵最小。差的方差矩阵最小。n向量优化形式：向量优化形式：n为整数问题，求解较困难。为整数问题，求解较困难。n 156实验设计实验设计的目标：寻找 157157实验设计实验设计n当当 时，令时，令 近似为一连续实近似为一连续实数，原问题可松弛转换为连续实数优化：数，原问题可松弛转换为连续实数优化：n 157实验设计当 时，令 158158凸优化理论与应用凸优化理论与应用第第7 7章章 无约束优化无约束优化n 158凸优化理论与应用第7章 无约束优化159159无约束优化问题n问题描述：问题描述：n无约束问题求解的两种方法：无约束问题求解的两种方法：n迭代逼近：迭代逼近：n求解梯度方程：求解梯度方程：n 为凸函数，且二次可微。为凸函数，且二次可微。n 159无约束优化问题问题描述：无约束问题求解的两种方法：迭代160160例梯度方程梯度方程n二次优化：二次优化：n 160例梯度方程二次优化：161161迭代起始点迭代起始点n满足条件满足条件2 2的几种函数：的几种函数：n起始点起始点 满足：满足：n函数函数 任意下水平集都是闭集；任意下水平集都是闭集；n函数的定义域为函数的定义域为n当当 时，时，n 161迭代起始点满足条件2的几种函数：起始点 162162强凸性n定义：函数定义：函数 在在 上具有强凸性，若上具有强凸性，若 满足满足n若函数若函数 具有强凸性，则有具有强凸性，则有n 为最优值，则为最优值，则n 162强凸性定义：函数 在 上具有强163163强凸性则有则有n 为最优值，则为最优值，则n若函数若函数 在在 上具有强凸性，则可以证明存在上具有强凸性，则可以证明存在 ，满足，满足 n 163强凸性则有 为最优值，则若函数 164164强凸性n对于对于 ，矩阵，矩阵 的特征值从大到小依次的特征值从大到小依次为为 。则有：。则有：n定义：矩阵定义：矩阵 的条件数为最大特征值与最小的条件数为最大特征值与最小特征值之比，即特征值之比，即 。n条件数的上界：条件数的上界：n 164强凸性对于 ，矩阵 165165下降法n下降法的基本原理：下降法的基本原理：迭代迭代 ，满足，满足 为下降方向，为下降方向，为步长因子为步长因子。n对于凸函数对于凸函数 ，当，当 满足满足 时，存在某时，存在某个个 ，使得，使得 。n 165下降法下降法的基本原理：迭代 166166下降法n下降法的一般步骤：下降法的一般步骤：n给出初始点给出初始点 ；n循环迭代循环迭代n计算下降方向计算下降方向 ；n搜索步长因子搜索步长因子 ；n迭代：迭代：n 166下降法下降法的一般步骤：给出初始点 167167步长因子搜索n精确一维搜索：精确一维搜索：n回溯一维搜索：给定参数回溯一维搜索：给定参数n循环迭代循环迭代n初始化：令初始化：令 ；n若若 ，则终止退出；，则终止退出；n否则令否则令 n 167步长因子搜索精确一维搜索：回溯一维搜索：给定参数循环迭168168步长因子搜索n 168步长因子搜索169169梯度下降法n算法简单，但收敛速度较慢。算法简单，但收敛速度较慢。n下降方向：下降方向：n终止条件：终止条件：n收敛性：收敛性：其中其中 。n 169梯度下降法算法简单，但收敛速度较慢。下降方向：终止条件170170收敛性分析则有：则有：n设函数设函数 具有强凸性，则存在具有强凸性，则存在 和和 ，满足：，满足：n若若 采用精确一维搜索，则采用精确一维搜索，则 ，收敛速度因子：，收敛速度因子：n若若 采用回溯一维搜索，收敛速度因子：采用回溯一维搜索，收敛速度因子：n条件数越大，收敛速度越小。条件数越大，收敛速度越小。n 170收敛性分析则有：设函数 具有强凸性，则171171例n当当 时，时，算法收敛速度很慢。算法收敛速度很慢。n初始解为初始解为 ，采用精确一维搜索；，采用精确一维搜索；n迭代：迭代：n 171例当 时，算172172例n步长因子采用回溯一维搜索。步长因子采用回溯一维搜索。n 172例步长因子采用回溯一维搜索。173173最速下降法n归一化最速下降方向：归一化最速下降方向：n非归一化最速下降方向非归一化最速下降方向n欧式范数：欧式范数：n二次范数二次范数 ：n 范数：范数：n 173最速下降法归一化最速下降方向：非归一化最速下降方向欧式174174最速下降法n 174最速下降法175175收敛性分析n范数界：范数界：n收敛速度因子：收敛速度因子：n 175收敛性分析范数界：收敛速度因子：176176牛顿法n设函数设函数 二阶可微，则在二阶可微，则在 附近，附近，的泰勒的泰勒展式为：展式为：n泰勒展开可作为泰勒展开可作为 在在 附近的近似；附近的近似；n下降方向：下降方向：n为二次范数为二次范数 上的最上的最速下降方向。速下降方向。n 176牛顿法设函数 二阶可微，则在 附近，177177牛顿法n 177牛顿