凸优化理论与应用.ppt

《凸优化理论与应用.ppt》由会员分享，可在线阅读，更多相关《凸优化理论与应用.ppt（217页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、第一章凸集凸集8 8仿射集(Affine sets)n直线的表示：直线的表示：n线段的表示：线段的表示：9 9仿射集(Affine sets)n仿射集的定义：过集合仿射集的定义：过集合C内任意两点的直线均在集合内任意两点的直线均在集合C内，则称集合内，则称集合C为仿射集。为仿射集。n仿射集的例：直线、平面、超平面仿射集的例：直线、平面、超平面1010仿射集n仿射包：包含集合仿射包：包含集合C的最小的仿射集。的最小的仿射集。n仿射维数：仿射包的维数。仿射维数：仿射包的维数。1111仿射集n内点（内点（interior）：）：n相对内点（相对内点（relative interior）：）：1212

4、凸集(Convex Sets)n凸集的定义：集合凸集的定义：集合C内任意两点间的线段均在集合内任意两点间的线段均在集合C内，则称集合内，则称集合C为凸集。为凸集。1313凸集n凸包的定义：包含集合凸包的定义：包含集合C的最小的凸集。的最小的凸集。1414锥(Cones)n锥的定义：锥的定义：n凸锥的定义：集合凸锥的定义：集合C既是凸集又是锥。既是凸集又是锥。n锥包的定义：集合锥包的定义：集合C内点的所有锥组合。内点的所有锥组合。1515超平面和半空间n超平面超平面(hyperplane)：n半空间半空间(Halfspace)：1616欧氏球和椭球n欧氏球欧氏球(euclidean ball):

5、n椭球椭球(ellipsoid):1717范数球和范数锥n范数范数(norm)：n范数球范数球(norm ball)：n范数锥范数锥(norm cone)：1818多面体(Polyhedra)n多面体：多面体：n单纯形单纯形(simplex)：1919半正定锥(Positive semidefinite cone)nn阶对称矩阵集：阶对称矩阵集：nn阶半正定矩阵集：阶半正定矩阵集：nn阶正定矩阵集：阶正定矩阵集：n阶半正定矩阵集为阶半正定矩阵集为凸锥！凸锥！2020保持凸性的运算n集合交运算集合交运算n仿射变换仿射变换n透视透视/投射函数投射函数(perspective function)21

6、21保持凸性的运算n线性分式函数线性分式函数(linear-fractional function)2222真锥(proper cone)n真锥的定义：锥真锥的定义：锥 满足如下条件满足如下条件K具有内点具有内点K内不含直线内不含直线2323广义不等式n真锥真锥 下的下的偏序关系偏序关系：n例：例：n逐项不等式逐项不等式n矩阵不等式矩阵不等式广义不等式广义不等式严格广义不等式严格广义不等式2424广义不等式的性质2525严格广义不等式的性质2626最值和极值n最小元的定义：设最小元的定义：设 ，对，对 ，都有，都有 成立，则称成立，则称 为为 的最小元。的最小元。n极小元的定义：设极小元的定义

7、：设 ，对于，对于 ，若，若 ，则，则 成立，则称成立，则称 为为 的极小元。的极小元。2727分割超平面(separating hyperplane)n定理：设定理：设 和和 为两不相交凸集，则存在超平面将为两不相交凸集，则存在超平面将 和和 分离。即：分离。即：2828支撑超平面(supporting hyperplane)n定义：设集合定义：设集合 ，为为 边界上的点。若存在边界上的点。若存在 ，满足对任意满足对任意 ，都有，都有 成立，则称超平成立，则称超平面面 为集合为集合 在点在点 处的支撑超平面。处的支撑超平面。n定理：凸集边界上任意一点均存在支撑超平面。定理：凸集边界上任意一点

8、均存在支撑超平面。n定理：若一个闭的非中空集合，在边界上的任意一点定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。存在支撑超平面，则该集合为凸集。2929对偶锥(dual cone)n对偶锥的定义：设对偶锥的定义：设 为锥，则集合为锥，则集合 称为对偶锥。称为对偶锥。n对偶锥的性质：对偶锥的性质：真锥的对偶锥仍真锥的对偶锥仍然是真锥！然是真锥！3030对偶广义不等式n广义不等式与对偶等价性质广义不等式与对偶等价性质n最小元的对偶特性：最小元的对偶特性：3131对偶广义不等式n极小元的对偶特性极小元的对偶特性反过来不一定成反过来不一定成立！立！3232作业nP60

9、2.8nP60 2.10nP60 2.14nP62 2.16nP62 2.18nP64 2.30nP64 2.31nP64 2.333333凸优化理论与应用凸优化理论与应用第二章第二章 凸函数凸函数3434凸函数的定义1.定义域定义域 为凸集；为凸集；2.，有，有n凸函数的定义：函数凸函数的定义：函数 ，满足，满足n凸函数的扩展定义：若凸函数的扩展定义：若 为凸函数，则可定义其扩为凸函数，则可定义其扩展函数展函数 为为凸函数的凸函数的扩展函数扩展函数也是凸函也是凸函数！数！3535凸函数的一阶微分条件n若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 一阶可微，一阶可微，则函数则函

10、数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对3636凸函数的二阶微分条件n若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 二阶可微，二阶可微，则函数则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对 ，其，其Hessian矩阵矩阵3737凸函数的例n幂函数幂函数n负对数函数负对数函数n负熵函数负熵函数n范数函数范数函数n指数函数指数函数3838凸函数的例3939下水平集(sublevel set)n定理：凸函数的任一下水平集均为凸集。定理：凸函数的任一下水平集均为凸集。n任一下水平集均为凸集的函数任一下水平集均为凸集的函数不一定不一定为凸函数。为

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

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

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

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

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

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

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

18、调增函数；为严格单调增函数；满满足足 当且仅当当且仅当 ；满足满足 当当且仅当且仅当 。则原优化问题与以下优化问题等价。则原优化问题与以下优化问题等价6363优化问题的等价形式(4)n定理：原优化问题与以下优化问题等价定理：原优化问题与以下优化问题等价n 称为松弛变量称为松弛变量6464优化问题的等价形式(5)n定理：设定理：设 满足等式满足等式 成立，当且仅当成立，当且仅当 。则原优化问题与以下优化。则原优化问题与以下优化问题等价问题等价6565可分离变量优化问题n性质：性质：其中其中可以分离变量可以分离变量n定理：优化问题定理：优化问题6666优化问题的上半图形式6767凸优化问题的基本形

19、式n凸优化问题的基本描述：凸优化问题的基本描述：为仿射函数为仿射函数 为凸函数为凸函数 若若 为准凸函数，则优化问题称为准凸优化问题。为准凸函数，则优化问题称为准凸优化问题。性质：凸优化问题的可行域是凸集。性质：凸优化问题的可行域是凸集。6868凸优化问题的例n例：例：等价于凸优化问题等价于凸优化问题6969凸优化问题的局部最优解n定理：凸优化问题的局部最优解均是全局最优解。定理：凸优化问题的局部最优解均是全局最优解。7070凸优化问题最优解的微分条件n定理：设定理：设 为凸优化问题的可行域，为凸优化问题的可行域，可微。则可微。则 为最优解当且仅当为最优解当且仅当 成立。成立。n定理：非约束凸

20、优化问题中，若定理：非约束凸优化问题中，若 可微。则可微。则 为最为最优解当且仅当优解当且仅当 成立。成立。7171凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，且存在向量，且存在向量 满足满足 n定理：设凸优化问题仅有等式约束定理：设凸优化问题仅有等式约束7272凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，且，且 n定理：设凸优化问题定理：设凸优化问题7373凸优化问题的等价形式等价于等价于 n定理：设凸优化问题定理：设凸优化问题其中其中 7474凸优化问题的等价形式等价于等价于 n定理：设凸优化问题定理：设凸优化问题7575准凸优化问题 为准凸函数，为准凸

21、函数，为凸函数。为凸函数。n准凸优化问题的基本描述准凸优化问题的基本描述n注：准凸优化问题的局部最优解不一定是全局最优解。注：准凸优化问题的局部最优解不一定是全局最优解。7676准凸优化问题的上半图形式n设设 为准凸函数为准凸函数 的凸函数族表示，即的凸函数族表示，即 则准凸优化问题的可行解问题为则准凸优化问题的可行解问题为n设设 为准凸优化问题的最优解，若上述问题可解，则为准凸优化问题的最优解，若上述问题可解，则 。否则。否则 。7777准凸优化问题二分法求解n给定一个足够小的给定一个足够小的 和足够大的和足够大的 ，使得区间，使得区间 能包含最优解能包含最优解 。给定。给定nLOOP：n令

22、令n求解可行解问题；求解可行解问题；n若可解，则令若可解，则令 ，否则令，否则令n若若 ，则结束，否则，则结束，否则goto LOOP。7878线性规划(linear program,LP)nLP问题的一般描述问题的一般描述7979LP问题的几种类型n标准标准LP问题问题n不等式形式不等式形式LP问题问题8080标准LP问题的转换8181LP问题的例nChebyshev center of a polyhedronnPiecewise-linear minimizationnLinear-fractional programming8282Chebyshev center of a polyh

23、edronn多面体nChebyshev center：到多面体边界距离最大的内点（最深的点）n问题描述nLP形式8383Piecewise-linear minimizationn问题描述n上半图形式nLP形式8484Linear-fractional programmingn问题描述nLP形式8585二次规划(quadratic program,QP)nQP问题的基本描述问题的基本描述8686二次约束二次规划nquadratically constrained quadratic program(QCQP)8787QP问题的例nLeast-squares and regressionnDis

24、tance between polyhedra8888Least-squares and regressionn问题描述8989Distance between polyhedran问题描述nQP形式9090Second-order cone program,SOCPnSOCP问题的基本描述n二次锥约束条件9191SOCP问题的例Robust linear programmingn问题描述其中 不是完全确定的常数。n例：为确定的常数，为变量，其范围满足SOCP形式9292几何规划(Geometric programming)n单项式与多项式n几何规划的基本描述9393几何规划的凸形式转换n令n

25、几何规划的凸形式9494广义不等式约束n广义不等式约束的优化问题nSOCP的描述9595凸优化理论与应用凸优化理论与应用第四章第四章 对偶问题对偶问题9696优化问题的拉格朗日函数n设优化问题：设优化问题：n拉格朗日拉格朗日(Lagrangian)函数：函数：n对固定的对固定的 ，拉格朗日函数，拉格朗日函数 为关于为关于 和和 的的仿仿射函数射函数。9797拉格朗日对偶函数n拉格朗日对偶函数拉格朗日对偶函数(lagrange dual function)：若拉格朗日函数没有下界，则令若拉格朗日函数没有下界，则令n拉格朗日对偶函数为拉格朗日对偶函数为凹函数凹函数。n对对 和和 ，若原最优化问题有

26、最优值，若原最优化问题有最优值 ，则，则9898对偶函数的例nLeast-squares solution of linear equationsnStandard form LPnTwo-way partitioning problem9999Least-squares solution of linear equationsn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：100100Standard form LPn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：101101Two-way partitioning

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

28、5Minimum volume covering ellipsoidn原始问题：原始问题：n对偶函数：对偶函数：n共轭函数：共轭函数：106106拉格朗日对偶问题n拉格朗日对偶问题的描述：拉格朗日对偶问题的描述：n对偶可行域对偶可行域n最优值最优值n最优解最优解107107LP问题的对偶问题n标准标准LP问题问题n对偶函数对偶函数n对偶问题对偶问题n等价描述等价描述108108弱对偶性n定理（弱对偶性）定理（弱对偶性）：设原始问题的最优值为：设原始问题的最优值为 ，对偶问，对偶问题的最优值为题的最优值为 ，则，则 成立。成立。noptimal duality gapn可以利用对偶问题找到原始问

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

30、偶性。该条件称为Slater条件条件。110110强对偶性存在存在 ，满足，满足n弱化的弱化的Slater条件：若不等式约束条件的前条件：若不等式约束条件的前 个为线性不个为线性不等式约束条件，则等式约束条件，则Slater条件可以弱化为：条件可以弱化为：111111Least-squares solution of linear equationsn原问题：原问题：n对偶问题：对偶问题：n具有强对偶性具有强对偶性112112Lagrange dual of QCQPnQCQP：n拉格朗日函数：拉格朗日函数：n对偶函数：对偶函数：113113Lagrange dual of QCQPn对偶问题

31、对偶问题：nSlater条件：存在条件：存在 ，满足，满足114114Entropy maximizationn原始问题：原始问题：n对偶函数：对偶函数：n对偶问题对偶问题：115115Entropy maximizationn弱化的弱化的Slater条件：存在条件：存在 ，满足，满足116116Minimum volume covering ellipsoidn原始问题：原始问题：n对偶函数：对偶函数：n对偶问题：对偶问题：117117Minimum volume covering ellipsoidn弱化的弱化的Slater条件总成立，因此该优化问题具有强对偶性。条件总成立，因此该优化问题

32、具有强对偶性。n弱化的弱化的Slater条件：存在条件：存在 ，满足，满足118118对偶可行解的不等式对偶可行解的不等式n对于一优化问题，若对于一优化问题，若 为一可行解，为一可行解，为对偶问题可行解，为对偶问题可行解，则有如下不等式：则有如下不等式：为为 次优解，其中次优解，其中n不等式可以用于对次优解的精度估计不等式可以用于对次优解的精度估计119119互补松弛条件互补松弛条件所以所以n设设 为原始优化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则若两者具有强对偶性，则即即120120KKT优化条件优化条件n设优化问题中，函数设优化问

33、题中，函数 可微。设可微。设 为原始优化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，且两者为对偶问题的最优解，且两者具有强对偶性，则具有强对偶性，则 满足如下条件：满足如下条件：KKT条件为条件为必要条件！必要条件！121121凸优化问题的凸优化问题的KKT条件条件可微。设可微。设 满足满足KKT条件，则条件，则 为原始问题的最优解，而为原始问题的最优解，而 为对偶问题的最优解，且两者具有强对偶性。为对偶问题的最优解，且两者具有强对偶性。n设原始问题为凸优化问题中，函数设原始问题为凸优化问题中，函数122122例例n原始凸优化问题原始凸优化问题KKT条件条件123123例例其中其

34、中解得解得124124凸优化问题的对偶求解凸优化问题的对偶求解存在唯一解存在唯一解 。若。若 为原始问题的可行解，则为原始问题的可行解，则 即为原始问题即为原始问题的最优解；若的最优解；若 不是原始问题的可行解，则原始问题不存在最不是原始问题的可行解，则原始问题不存在最优解。优解。n设原始优化问题与对偶问题具有强对偶性，且设原始优化问题与对偶问题具有强对偶性，且 为对偶问为对偶问题的最优解。题的最优解。存在唯一的最小解，即存在唯一的最小解，即125125扰动问题扰动问题n扰动问题：扰动问题：n当当 时即为原始问题。时即为原始问题。n若若 为正，则第为正，则第 个不等式约束被放宽；若个不等式约束

35、被放宽；若 为负，则第为负，则第 个个不等式约束被收紧。不等式约束被收紧。n记记 为扰动问题的最优解。若扰动问题无最优解，则记为扰动问题的最优解。若扰动问题无最优解，则记126126灵敏度分析灵敏度分析n设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为问题的最优对偶解为 ，则有，则有n若若 在在 处可微，则处可微，则127127n定义（弱选择性）：若两个不等式（等式）系统，至多有一个可定义（弱选择性）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。解，则称这两个系统具有弱选择性。选择定理选

36、择定理n对偶不等式组对偶不等式组n设原始问题的约束条件：设原始问题的约束条件：n对偶问题对偶问题n原始问题的约束条件与对偶不等式组具有弱选择性。原始问题的约束条件与对偶不等式组具有弱选择性。128128选择定理选择定理n对偶不等式组对偶不等式组n设原始问题的严格不等式约束条件：设原始问题的严格不等式约束条件：n原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。129129n定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。则称这两个系统具有

37、强选择性。选择定理选择定理n对偶不等式组对偶不等式组n设原始问题为凸优化问题，其严格不等式约束条件为：设原始问题为凸优化问题，其严格不等式约束条件为：n若存在若存在 ，满足，满足 ，则上述两不等式约束系统，则上述两不等式约束系统具有强选择性。具有强选择性。130130选择定理选择定理n对偶不等式组对偶不等式组n设原始问题为凸优化问题，其不等式约束条件为：设原始问题为凸优化问题，其不等式约束条件为：则原始问题的不等式约束条件与对偶不等式组具有强选择性。则原始问题的不等式约束条件与对偶不等式组具有强选择性。n若存在若存在 ，满足，满足 ，且下述优化问题存在最优，且下述优化问题存在最优解解13113

38、1罚函数的例n 范数：范数：n死区线性罚函数：死区线性罚函数：n对数门限罚函数对数门限罚函数132132鲁棒的罚函数n若若 大到一定程度时，罚函数为大到一定程度时，罚函数为 的线性函数，则称的线性函数，则称该罚函数为鲁棒的罚函数。该罚函数为鲁棒的罚函数。nHuber罚函数罚函数133133最小范数问题最小范数问题n问题描述：问题描述：其中其中 为方程组为方程组 的解。的解。n可以消去等式约束将其转换为范数逼近问题：可以消去等式约束将其转换为范数逼近问题：134134最小范数问题最小范数问题n最小平方范数问题：范数最小平方范数问题：范数 ，最优解满足：，最优解满足：n最小罚问题：最小罚问题：n绝

39、对值和最小问题：范数绝对值和最小问题：范数 ，原问题可转换为，原问题可转换为LP问问题：题：135135正则逼近正则逼近n二元矢量优化问题描述：二元矢量优化问题描述：n正则化问题：正则化问题：最优解描述了两分量的一条折中曲线。最优解描述了两分量的一条折中曲线。136136正则逼近正则逼近nTikhonov正则化问题：正则化问题：为二次优化问题：为二次优化问题：最优解的形式最优解的形式：137137正则逼近正则逼近nTikhonov光滑正则化问题：光滑正则化问题：为二阶差分算子：为二阶差分算子：138138信号复原信号复原n已知加噪信号：已知加噪信号：信号复原问题的描述：信号复原问题的描述：函数

40、函数 为正则函数或光滑函数。为正则函数或光滑函数。139139信号复原信号复原140140信号复原信号复原141141信号复原信号复原142142鲁棒逼近鲁棒逼近n问题描述：问题描述：n随机鲁棒逼近：随机鲁棒逼近：为随机变量，逼近问题转换为最小化为随机变量，逼近问题转换为最小化期望期望n例：例：随机鲁棒逼近为：随机鲁棒逼近为：转换为转换为：143143随机鲁棒逼近随机鲁棒逼近n 为随机变量：为随机变量：最小平方随机鲁棒逼近为：最小平方随机鲁棒逼近为：转换为转换为：其中其中144144最坏情况鲁棒逼近最坏情况鲁棒逼近n考虑考虑 ，最坏情况鲁棒逼近为：，最坏情况鲁棒逼近为：n例：例：随机鲁棒逼近为

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

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

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

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

45、题，求解较困难。157157实验设计实验设计n当当 时，令时，令 近似为一连续实数，原问题近似为一连续实数，原问题可松弛转换为连续实数优化：可松弛转换为连续实数优化：158158凸优化理论与应用凸优化理论与应用第第7 7章章 无约束优化无约束优化159159无约束优化问题n问题描述：问题描述：n无约束问题求解的两种方法：无约束问题求解的两种方法：n迭代逼近：迭代逼近：n求解梯度方程：求解梯度方程：n 为凸函数，且二次可微。为凸函数，且二次可微。160160例梯度方程梯度方程n二次优化：二次优化：161161迭代起始点迭代起始点n满足条件满足条件2的几种函数：的几种函数：n起始点起始点 满足：满

46、足：n函数函数 任意下水平集都是闭集；任意下水平集都是闭集；n函数的定义域为函数的定义域为n当当 时，时，162162强凸性n定义：函数定义：函数 在在 上具有强凸性，若上具有强凸性，若 满足满足n若函数若函数 具有强凸性，则有具有强凸性，则有n 为最优值，则为最优值，则163163强凸性则有则有n 为最优值，则为最优值，则n若函数若函数 在在 上具有强凸性，则可以证明存在上具有强凸性，则可以证明存在 ，满足，满足 164164强凸性n对于对于 ，矩阵，矩阵 的特征值从大到小依次的特征值从大到小依次为为 。则有：。则有：n定义：矩阵定义：矩阵 的条件数为最大特征值与最小的条件数为最大特征值与最

47、小特征值之比，即特征值之比，即 。n条件数的上界：条件数的上界：165165下降法n下降法的基本原理：下降法的基本原理：迭代迭代 ，满足，满足 为下降方向，为下降方向，为步长因子为步长因子。n对于凸函数对于凸函数 ，当，当 满足满足 时，存在某时，存在某个个 ，使得，使得 。166166下降法n下降法的一般步骤：下降法的一般步骤：n给出初始点给出初始点 ；n循环迭代循环迭代n计算下降方向计算下降方向 ；n搜索步长因子搜索步长因子 ；n迭代：迭代：167167步长因子搜索n精确一维搜索：精确一维搜索：n回溯一维搜索：给定参数回溯一维搜索：给定参数n循环迭代循环迭代n初始化：令初始化：令 ；n若若

48、 ，则终止退出；，则终止退出；n否则令否则令 168168步长因子搜索169169梯度下降法n算法简单，但收敛速度较慢。算法简单，但收敛速度较慢。n下降方向：下降方向：n终止条件：终止条件：n收敛性：收敛性：其中其中 。170170收敛性分析则有：则有：n设函数设函数 具有强凸性，则存在具有强凸性，则存在 和和 ，满足：，满足：n若若 采用精确一维搜索，则采用精确一维搜索，则 ，收敛速度因子：，收敛速度因子：n若若 采用回溯一维搜索，收敛速度因子：采用回溯一维搜索，收敛速度因子：n条件数越大，收敛速度越小。条件数越大，收敛速度越小。171171例n当当 时，时，算法收敛速度很慢。算法收敛速度很

49、慢。n初始解为初始解为 ，采用精确一维搜索；，采用精确一维搜索；n迭代：迭代：172172例n步长因子采用回溯一维搜索。步长因子采用回溯一维搜索。173173最速下降法n归一化最速下降方向：归一化最速下降方向：n非归一化最速下降方向非归一化最速下降方向n欧式范数：欧式范数：n二次范数二次范数 ：n 范数：范数：174174最速下降法175175收敛性分析n范数界：范数界：n收敛速度因子：收敛速度因子：176176牛顿法n设函数设函数 二阶可微，则在二阶可微，则在 附近，附近，的泰勒展式为：的泰勒展式为：n泰勒展开可作为泰勒展开可作为 在在 附近的近似；附近的近似；n下降方向：下降方向：n为二次

50、范数为二次范数 上的最速下降方向。上的最速下降方向。177177牛顿法178178牛顿减量n令令n 为为 在在 处的牛顿减量。处的牛顿减量。n牛顿减量的性质牛顿减量的性质1：n性质性质2：牛顿减量可作为迭代求解的误差估计。牛顿减量可作为迭代求解的误差估计。n性质性质3：牛顿减量具有仿射不变性。：牛顿减量具有仿射不变性。179179牛顿方法n初始化：给定初始解初始化：给定初始解 以及以及nLOOP：n计算：计算：n若若 则终止退出；则终止退出；n一维线性搜索：计算步长因子一维线性搜索：计算步长因子 ；n迭代：迭代：180180收敛性分析n定理：假设定理：假设 二阶连续可微，具有强凸性，即存在二阶