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

《凸优化理论与应用课件.ppt》由会员分享，可在线阅读，更多相关《凸优化理论与应用课件.ppt（217页珍藏版）》请在三一办公上搜索。

1、可编辑,1,凸优化理论与应用,庄 伯 金B,可编辑,2,优化理论概述,什么是优化问题？,Objective function,Constraint functions,可编辑,3,几类经典的优化问题,线性规划问题,最小二乘问题,凸优化问题,凸优化问题理论上有有效的方法进行求解！,可编辑,4,本课程的主要内容,理论部分凸集和凸函数凸优化问题对偶问题应用部分逼近与拟合统计估计几何问题算法部分非约束优化方法等式约束优化方法内点法,可编辑,5,熟悉了解凸优化理论的基本原理和基本方法；掌握实际问题转化为凸优化问题的基本方法；掌握最优化问题的经典算法。,课程要求,可编辑,6,参考书目,Stephen Bo

2、yd and Lieven Vandenberghe, “Convex Optimization”, Cambridge University Press.袁亚湘、孙文瑜，“最优化理论与方法”，科学出版社，1999。,可编辑,7,凸优化理论与应用,第一章凸集,可编辑,8,仿射集(Affine sets),直线的表示：,线段的表示：,可编辑,9,仿射集(Affine sets),仿射集的定义：过集合C内任意两点的直线均在集合C内，则称集合C为仿射集。仿射集的例：直线、平面、超平面,可编辑,10,仿射集,仿射包：包含集合C的最小的仿射集。,仿射维数：仿射包的维数。,可编辑,11,仿射集,内点（in

3、terior）：,相对内点（relative interior）：,可编辑,12,凸集(Convex Sets),凸集的定义：集合C内任意两点间的线段均在集合C内，则称集合C为凸集。,可编辑,13,凸集,凸包的定义：包含集合C的最小的凸集。,可编辑,14,锥(Cones),锥的定义：,凸锥的定义：集合C既是凸集又是锥。,锥包的定义：集合C内点的所有锥组合。,可编辑,15,超平面和半空间,超平面(hyperplane) ：,半空间(Halfspace)：,可编辑,16,欧氏球和椭球,欧氏球(euclidean ball):,椭球(ellipsoid):,可编辑,17,范数球和范数锥,范数(nor

4、m)：,范数球(norm ball)：,范数锥(norm cone)：,可编辑,18,多面体(Polyhedra),多面体：,单纯形(simplex)：,可编辑,19,半正定锥(Positive semidefinite cone),n阶对称矩阵集：,n阶半正定矩阵集：,n阶正定矩阵集：,n阶半正定矩阵集为凸锥！,可编辑,20,保持凸性的运算,集合交运算仿射变换透视/投射函数(perspective function),可编辑,21,保持凸性的运算,线性分式函数(linear-fractional function),可编辑,22,真锥(proper cone),真锥的定义：锥 满足如下条件,

5、K具有内点,K内不含直线,可编辑,23,广义不等式,真锥 下的偏序关系：,例：逐项不等式矩阵不等式,广义不等式,严格广义不等式,可编辑,24,广义不等式的性质,可编辑,25,严格广义不等式的性质,可编辑,26,最值和极值,最小元的定义：设 ，对 ，都有 成立，则称 为 的最小元。,极小元的定义：设 ，对于 ，若 ，则 成立，则称 为 的极小元。,可编辑,27,分割超平面(separating hyperplane),定理：设 和 为两不相交凸集，则存在超平面将 和 分离。即：,可编辑,28,支撑超平面(supporting hyperplane),定义：设集合 ， 为 边界上的点。若存在 ，满

6、足对任意 ，都有 成立，则称超平面 为集合 在点 处的支撑超平面。,定理：凸集边界上任意一点均存在支撑超平面。定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。,可编辑,29,对偶锥(dual cone),对偶锥的定义：设 为锥，则集合 称为对偶锥。,对偶锥的性质：,真锥的对偶锥仍然是真锥！,可编辑,30,对偶广义不等式,广义不等式与对偶等价性质,最小元的对偶特性：,可编辑,31,对偶广义不等式,极小元的对偶特性,反过来不一定成立！,可编辑,32,作业,P60 2.8P60 2.10P60 2.14P62 2.16P62 2.18P64 2.30P64 2.31P6

7、4 2.33,可编辑,33,凸优化理论与应用,第二章 凸函数,可编辑,34,凸函数的定义,1.定义域 为凸集；,2. ，有,凸函数的定义：函数 ，满足,凸函数的扩展定义：若 为凸函数，则可定义其扩展函数 为,凸函数的扩展函数也是凸函数！,可编辑,35,凸函数的一阶微分条件,若函数 的定义域 为开集，且函数 一阶可微，则函数 为凸函数当且仅当 为凸集，且对,可编辑,36,凸函数的二阶微分条件,若函数 的定义域 为开集，且函数 二阶可微，则函数 为凸函数当且仅当 为凸集，且对 ，其Hessian矩阵,可编辑,37,凸函数的例,幂函数,负对数函数,负熵函数,范数函数,指数函数,可编辑,38,凸函数的

8、例,可编辑,39,下水平集(sublevel set),定理：凸函数的任一下水平集均为凸集。,任一下水平集均为凸集的函数不一定为凸函数。,可编辑,40,函数上半图(epigraph),定理：函数 为凸函数当且仅当 的上半图为凸集。,可编辑,41,Jensen不等式,为凸函数，则有：,Jensen不等式的另外形式：,可编辑,42,保持函数凸性的算子,凸函数的逐点最大值,凸函数与仿射变换的复合,凸函数的非负加权和,可编辑,43,保持函数凸性的算子,复合运算,最小值算子,凸函数的透视算子,可编辑,44,共轭函数(conjugate function),定义：设函数 ，其共轭函数 ，定义为,共轭函数的

9、例,共轭函数具有凸性！,可编辑,45,共轭函数的性质,Fenchels inequality,性质：若 为凸函数，且 的上半图是闭集，则有,可编辑,46,准凸函数(quasiconvex function),准凸函数的例,可编辑,47,准凸函数的判定定理,定理：函数 为准凸函数，当且仅当 为凸集，且对 ，有,定理：若函数 一阶可微，则 为准凸函数，当且仅当 为凸集，且对 ，有,可编辑,48,最小值函数,非负权值函数的最大值函数,保持准凸性的算子,复合函数,可编辑,49,准凸函数的凸函数族表示,若 为准凸函数，根据 的任意 下水平集，我们可以构造一个凸函数族 ，使得,性质：若 为准凸函数 的凸函

10、数族表示，对每一个 ，若 ，则有,可编辑,50,对数凸函数,对数凸函数的例,可编辑,51,对数凸函数和凹函数的性质,性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。,定理：函数 二阶可微，则 为对数凸函数当且仅当,性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。,推论：函数 对每一个 在 上对数凸，则函数 也是对数凸函数。,可编辑,52,对数凸函数和凹函数的性质,定理：函数 为对数凹函数，则函数 是对数凹函数。,可编辑,53,广义不等式下的凸性,广义单调性的定义：设 为真锥，函数 称为 单调增，若函数 满足：,定理(对偶等价)：函数 为 凸函数，当且仅当对所有 ， 为

11、凸函数。,可编辑,54,作业(1),P116 3.16P116 3.21,可编辑,55,作业(2),P121 3.41P122 3.49 (1)(2),可编辑,56,凸优化理论与应用,第三章 凸优化,可编辑,57,优化问题的基本形式,优化问题的基本描述：,优化变量,不等式约束,等式约束,无约束优化,可编辑,58,优化问题的基本形式,最优化值,最优化解,优化问题的域,可行点(解) (feasible) 满足约束条件,可行域(可解集) 所有可行点的集合,可编辑,59,局部最优问题,局部最优问题,可编辑,60,优化问题的等价形式(1),可编辑,61,优化问题的等价形式(2),可编辑,62,优化问题的

12、等价形式(3),定理：设 为严格单调增函数； 满足 当且仅当 ； 满足 当且仅当 。则原优化问题与以下优化问题等价,可编辑,63,优化问题的等价形式(4),定理：原优化问题与以下优化问题等价,称为松弛变量,可编辑,64,优化问题的等价形式(5),定理：设 满足等式 成立，当且仅当 。则原优化问题与以下优化问题等价,可编辑,65,可分离变量优化问题,可编辑,66,优化问题的上半图形式,可编辑,67,凸优化问题的基本形式,凸优化问题的基本描述：,为仿射函数,为凸函数,若 为准凸函数，则优化问题称为准凸优化问题。,性质：凸优化问题的可行域是凸集。,可编辑,68,凸优化问题的例,例：,等价于凸优化问题

13、,可编辑,69,凸优化问题的局部最优解,定理：凸优化问题的局部最优解均是全局最优解。,可编辑,70,凸优化问题最优解的微分条件,定理：设 为凸优化问题的可行域， 可微。则 为最优解当且仅当 成立。,定理：非约束凸优化问题中，若 可微。则 为最优解当且仅当 成立。,可编辑,71,凸优化问题的等价形式,可编辑,72,凸优化问题的等价形式,可编辑,73,凸优化问题的等价形式,可编辑,74,凸优化问题的等价形式,等价于,定理：设凸优化问题,可编辑,75,准凸优化问题,注：准凸优化问题的局部最优解不一定是全局最优解。,可编辑,76,准凸优化问题的上半图形式,设 为准凸函数 的凸函数族表示，即,则准凸优化

14、问题的可行解问题为,设 为准凸优化问题的最优解，若上述问题可解，则 。否则 。,可编辑,77,准凸优化问题二分法求解,给定一个足够小的 和足够大的 ，使得区间 能包含最优解 。给定,LOOP：令求解可行解问题；若可解，则令 ，否则令若 ，则结束，否则goto LOOP。,可编辑,78,线性规划(linear program,LP),LP问题的一般描述,可编辑,79,LP问题的几种类型,标准LP问题,不等式形式LP问题,可编辑,80,标准LP问题的转换,可编辑,81,LP问题的例,Chebyshev center of a polyhedron,Piecewise-linear minimiza

15、tion,Linear-fractional programming,可编辑,82,Chebyshev center of a polyhedron,多面体,Chebyshev center：到多面体边界距离最大的内点（最深的点）,问题描述,LP形式,可编辑,83,Piecewise-linear minimization,问题描述,上半图形式,LP形式,可编辑,84,Linear-fractional programming,问题描述,LP形式,可编辑,85,二次规划(quadratic program,QP),QP问题的基本描述,可编辑,86,二次约束二次规划,quadratically

16、constrained quadratic program (QCQP),可编辑,87,QP问题的例,Least-squares and regression,Distance between polyhedra,可编辑,88,Least-squares and regression,问题描述,可编辑,89,Distance between polyhedra,问题描述,QP形式,可编辑,90,Second-order cone program, SOCP,SOCP问题的基本描述,二次锥约束条件,可编辑,91,SOCP问题的例Robust linear programming,例： 为确定的常

17、数， 为变量，其范围满足,SOCP形式,可编辑,92,几何规划(Geometric programming),单项式与多项式,几何规划的基本描述,可编辑,93,几何规划的凸形式转换,令,几何规划的凸形式,可编辑,94,广义不等式约束,广义不等式约束的优化问题,SOCP的描述,可编辑,95,凸优化理论与应用,第四章 对偶问题,可编辑,96,优化问题的拉格朗日函数,设优化问题：,拉格朗日(Lagrangian)函数：,对固定的 ，拉格朗日函数 为关于 和 的仿射函数。,可编辑,97,拉格朗日对偶函数,拉格朗日对偶函数(lagrange dual function) ：,若拉格朗日函数没有下界，则令

18、,拉格朗日对偶函数为凹函数。,对 和 ，若原最优化问题有最优值 ，则,可编辑,98,对偶函数的例,Least-squares solution of linear equations,Standard form LP,Two-way partitioning problem,可编辑,99,Least-squares solution of linear equations,原问题：,拉格朗日函数：,拉格朗日对偶函数：,可编辑,100,Standard form LP,原问题：,拉格朗日函数：,拉格朗日对偶函数：,可编辑,101,Two-way partitioning problem,原问题：

19、,拉格朗日函数：,拉格朗日对偶函数：,可编辑,102,对偶函数与共轭函数,共轭函数,共轭函数与对偶函数存在密切联系,具有线性不等式约束和线性等式约束的优化问题：,对偶函数：,可编辑,103,Equality constrained norm minimization,问题描述：,共轭函数：,对偶函数：,可编辑,104,Entropy maximization,原始问题：,共轭函数：,对偶函数：,可编辑,105,Minimum volume covering ellipsoid,原始问题：,对偶函数：,共轭函数：,可编辑,106,拉格朗日对偶问题,拉格朗日对偶问题的描述：,对偶可行域,最优值,最

20、优解,可编辑,107,LP问题的对偶问题,标准LP问题,对偶函数,对偶问题,等价描述,可编辑,108,弱对偶性,定理（弱对偶性） ：设原始问题的最优值为 ，对偶问题的最优值为 ，则 成立。,optimal duality gap,可以利用对偶问题找到原始问题最优解的下界。,可编辑,109,强对偶性,强对偶性并不是总是成立的。,定义（强对偶性） ：设原始问题的最优值为 ，对偶问题的最优值为 。若 成立，则称原始问题和对偶问题之间具有强对偶性。,凸优化问题通常（但并不总是）具有强对偶性。,可编辑,110,强对偶性,存在 ，满足,弱化的Slater条件：若不等式约束条件的前 个为线性不等式约束条件，

21、则Slater条件可以弱化为：,可编辑,111,Least-squares solution of linear equations,原问题：,对偶问题：,具有强对偶性,可编辑,112,Lagrange dual of QCQP,QCQP：,拉格朗日函数：,对偶函数：,可编辑,113,Lagrange dual of QCQP,对偶问题：,Slater条件：存在 ，满足,可编辑,114,Entropy maximization,原始问题：,对偶函数：,对偶问题：,可编辑,115,Entropy maximization,弱化的Slater条件：存在 ，满足,可编辑,116,Minimum vo

22、lume covering ellipsoid,原始问题：,对偶函数：,对偶问题：,可编辑,117,Minimum volume covering ellipsoid,弱化的Slater条件总成立，因此该优化问题具有强对偶性。,弱化的Slater条件：存在 ，满足,可编辑,118,对偶可行解的不等式,对于一优化问题，若 为一可行解， 为对偶问题可行解，则有如下不等式：,为 次优解，其中,不等式可以用于对次优解的精度估计,可编辑,119,互补松弛条件,所以,设 为原始优化问题的最优解， 为对偶问题的最优解，若两者具有强对偶性，则,即,可编辑,120,KKT优化条件,设优化问题中，函数 可微。设

23、为原始优化问题的最优解， 为对偶问题的最优解，且两者具有强对偶性，则 满足如下条件：,KKT条件为必要条件！,可编辑,121,凸优化问题的KKT条件,可编辑,122,例,原始凸优化问题,KKT条件,可编辑,123,例,其中,解得,可编辑,124,凸优化问题的对偶求解,可编辑,125,扰动问题,扰动问题：,当 时即为原始问题。,若 为正，则第 个不等式约束被放宽；若 为负，则第 个不等式约束被收紧。,记 为扰动问题的最优解。若扰动问题无最优解，则记,可编辑,126,灵敏度分析,设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为 ，则有,若 在 处可微，则,可编辑,127,

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

25、,设原始问题为凸优化问题，其不等式约束条件为：,可编辑,131,罚函数的例,范数：,死区线性罚函数：,对数门限罚函数,可编辑,132,鲁棒的罚函数,若 大到一定程度时，罚函数为 的线性函数，则称该罚函数为鲁棒的罚函数。,Huber罚函数,可编辑,133,最小范数问题,问题描述：,其中 为方程组 的解。,可以消去等式约束将其转换为范数逼近问题：,可编辑,134,最小范数问题,最小平方范数问题：范数 ，最优解满足：,最小罚问题：,绝对值和最小问题：范数 ，原问题可转换为LP问题：,可编辑,135,正则逼近,二元矢量优化问题描述：,正则化问题：,最优解描述了两分量的一条折中曲线。,可编辑,136,正

26、则逼近,Tikhonov正则化问题：,为二次优化问题：,最优解的形式：,可编辑,137,正则逼近,Tikhonov光滑正则化问题：,为二阶差分算子：,可编辑,138,信号复原,已知加噪信号：,信号复原问题的描述：,函数 为正则函数或光滑函数。,可编辑,139,信号复原,可编辑,140,信号复原,可编辑,141,信号复原,可编辑,142,鲁棒逼近,问题描述：,随机鲁棒逼近： 为随机变量，逼近问题转换为最小化期望,例：,随机鲁棒逼近为：,转换为：,可编辑,143,随机鲁棒逼近,为随机变量：,最小平方随机鲁棒逼近为：,转换为：,其中,可编辑,144,最坏情况鲁棒逼近,考虑 ，最坏情况鲁棒逼近为：,例

27、：,随机鲁棒逼近为：,转换为：,可编辑,145,凸优化理论与应用,第6章 统计估计,可编辑,146,概率分布的参数估计,随机变量的概率密度为 ，其中 为概率分布的参数，且参数未知。参数估计的目标就是通过一些已知样本估计获得参数的最优近似值。,问题描述,为样本观测值；,为对数似然函数；,若似然函数为凹函数，则优化问题为凸优化问题。,可编辑,147,具有独立同分布噪声的线性测量,线性测量模型：,为观测值或测量值；,为未知参数向量；,独立同分布噪声，其概率密度为 。,似然函数为,最大似然估计问题为：,可编辑,148,例,高斯白噪声,对数似然函数：,区间 上均匀分布的噪声：,对数似然函数：,可编辑,1

28、49,逻辑回归,随机变量 的概率分布为：,为参数；,为可观测的解释变量； 为观察值。,对数似然函数：,可编辑,150,假定测验,随机变量 ，有 种可能（假定）的分布；,假定 ： 的概率分布为,假定测验的目标：由观察值猜测随机变量最有可能服从哪种假定的分布。,当 时，称为二元假定测验。,随机检测子：非负元素矩阵,可编辑,151,假定测验,为当 实际服从第1种假定分布而猜测为第2种假定分布的概率；,为当 实际服从第2种假定分布而猜测为第1种假定分布的概率；,多目标优化形式：,检测概率矩阵,可编辑,152,假定测验,最小最大值形式,尺度优化形式：,可编辑,153,例,在两种假设下的概率分布为：,可编

29、辑,154,例,可编辑,155,实验设计,线性测量问题,最大似然估计值：,独立同分布高斯白噪声，服从分布 。,估计误差 均值为0，方差为,信赖椭圆为,可编辑,156,实验设计,实验设计的目标：寻找 ，使得误差的方差矩阵最小。,向量优化形式：,为整数问题，求解较困难。,可编辑,157,实验设计,当 时，令 近似为一连续实数，原问题可松弛转换为连续实数优化：,可编辑,158,凸优化理论与应用,第7章 无约束优化,可编辑,159,无约束优化问题,问题描述：,无约束问题求解的两种方法：,迭代逼近：,求解梯度方程：,为凸函数，且二次可微。,可编辑,160,例,梯度方程,二次优化：,可编辑,161,迭代起

30、始点,满足条件2的几种函数：,起始点 满足：,函数 任意下水平集都是闭集；,函数的定义域为,当 时，,可编辑,162,强凸性,定义：函数 在 上具有强凸性，若 满足,若函数 具有强凸性，则有,为最优值，则,可编辑,163,强凸性,则有,为最优值，则,若函数 在 上具有强凸性，则可以证明存在 ，满足,可编辑,164,强凸性,对于 ，矩阵 的特征值从大到小依次为 。则有：,定义：矩阵 的条件数为最大特征值与最小特征值之比，即 。,条件数的上界：,可编辑,165,下降法,对于凸函数 ，当 满足 时，存在某个 ，使得 。,可编辑,166,下降法,下降法的一般步骤：,给出初始点 ；,可编辑,167,步长

31、因子搜索,精确一维搜索：,可编辑,168,步长因子搜索,可编辑,169,梯度下降法,算法简单，但收敛速度较慢。,下降方向：,终止条件：,可编辑,170,收敛性分析,若 采用精确一维搜索，则 ，收敛速度因子：,若 采用回溯一维搜索，收敛速度因子：,条件数越大，收敛速度越小。,可编辑,171,例,当 时，算法收敛速度很慢。,初始解为 ，采用精确一维搜索；,迭代：,可编辑,172,例,步长因子采用回溯一维搜索。,可编辑,173,最速下降法,归一化最速下降方向：,非归一化最速下降方向,欧式范数：,二次范数 ：,范数：,可编辑,174,最速下降法,可编辑,175,收敛性分析,范数界：,收敛速度因子：,可

32、编辑,176,牛顿法,设函数 二阶可微，则在 附近， 的泰勒展式为：,泰勒展开可作为 在 附近的近似；,下降方向：,为二次范数 上的最速下降方向。,可编辑,177,牛顿法,可编辑,178,牛顿减量,令,为 在 处的牛顿减量。,牛顿减量的性质1：,性质2：,牛顿减量可作为迭代求解的误差估计。,性质3：牛顿减量具有仿射不变性。,可编辑,179,牛顿方法,初始化：给定初始解 以及,LOOP：,计算：,若 则终止退出；,一维线性搜索：计算步长因子 ；,迭代：,可编辑,180,收敛性分析,定理：假设 二阶连续可微，具有强凸性，即存在 ，满足：,则存在 ，,且海森矩阵满足Lipschitz条件，即存在 ，

33、满足：,若 ，则 ；,若 ，则 ，且,可编辑,181,收敛性分析,定理：假设 二阶连续可微，具有强凸性，即存在 ，满足：,则存在 ，对于 ，有,且海森矩阵满足Lipschitz条件，即存在 ，满足：,可编辑,182,例,可编辑,183,凸优化理论与应用,第8章 等式约束优化,可编辑,184,等式约束优化问题,问题描述：,为凸函数，且二次连续可微，且,假设最优值 存在，则 为最优解当且仅当存在 ，满足（KKT条件）：,可编辑,185,例,KKT系统：,二次优化：,KKT系统可解，则二次优化问题存在最优解。,系数矩阵称为KKT矩阵。KKT矩阵非奇异当且仅当：,可编辑,186,消去等式约束,方程组

34、的解集：,为方程组的一个特解， 为 的零空间范围。,无约束优化形式：,若 为最优解，则有,可编辑,187,对偶问题,对偶形式：,可编辑,188,牛顿法,牛顿减量,为等式约束优化的可行解，则在 附近原问题的二次近似为：,设 和 分别为该问题和对偶问题的最优解，则满足：,可编辑,189,性质2：牛顿减量具有仿射不变性。,牛顿减量,牛顿减量,牛顿减量的性质：,可编辑,190,可行下降方向,可行下降方向：设 满足方程组 。若 满足方程组 ，则 。 称为可行方向。若对于较小的 ，有 ，则 为可行下降方向。,可编辑,191,等式约束的牛顿方法,LOOP：,计算 及 ；,若 则终止退出；,一维线性搜索：计算

35、步长因子 ；,迭代：,初始化：给定初始解 满足 ，以及,可编辑,192,消去等式约束的牛顿方法,转换为等式约束下的牛顿方法：,初始值 ，第 次迭代值 ；,初始值：,迭代值：,可编辑,193,非可行解为初始点的牛顿法,函数 二阶连续可微，因此有,为等式约束优化的非可行解，则增量 应尽可能使 满足KKT条件，即：,设 和 为KKT条件的解，即有：,可编辑,194,非可行解为初始点的牛顿法,则KKT条件可表示为：,令,设 为不满足KKT条件，则其迭代量需满足：,即,可编辑,195,当 且 时，终止迭代。,非可行解为初始点的牛顿法,LOOP：,计算 和 ；,回溯一维线性搜索：,迭代：,初始化：给定初始

36、解 及 ，以及,令 ；,While,可编辑,196,其中 ，且满足 。,KKT系统的求解,1. 分解；,2.若 非奇异，则可消元：,3.若 奇异，则KKT系统可改写为：,KKT系统：,可编辑,197,凸优化理论与应用,第9章 内点法,可编辑,198,则优化问题具有强对偶性，其对偶问题亦可解。,假设存在 ，满足严格不等式条件,不等式约束优化问题,问题描述：,为凸函数，且二次连续可微，且,假设最优值 存在；,可编辑,199,不具备良好的连续可微性，考虑用对数阀函数来近似替代。,不等式约束的消去,示性函数消去不等式约束：,可编辑,200,令,对数阀函数,对于 ， 是 的光滑逼近。且当 时，有,带示性

37、函数的优化问题可近似为：,可编辑,201,对数阀函数二阶连续可微，导数为：,对数阀函数,对数阀函数 是凸函数,可编辑,202,中心线,对数阀近似问题的等价问题：,最优解为 ，则最优解集 称为优化问题的中心线。,可编辑,203,中心线的对偶点,设 ，则存在 满足KKT条件：,为对偶问题的可行解。,令,则 是拉格朗日函数 的最小值解。,可编辑,204,中心线的对偶点,设 为原始问题的最优值，则有：,因此，当 时，有 。 为原始问题的 次优解。,可编辑,205,更新 ：,阀方法,初始化：给定严格可行解 ， ， ，及,LOOP：,中心步骤：以 为初始点求解优化问题 ，,迭代：,终止条件：若 ，则终止退

38、出。,可编辑,206,收敛性分析,外层循环迭代次数：,中心步骤实质为一个无约束或等式约束优化问题，其收敛性分析与相应优化问题的收敛性分析结果一致。,可编辑,207,例：,LP问题：,初始值：,可编辑,208,当 时，原始问题不可解；,当 时，无法准确确定。,第一阶段方法,对于不等式约束的优化问题，如何寻找严格可行解或验证不可解？,求解优化问题：,该问题最优解存在，假设最优值为,当 时，存在严格可行解；,可编辑,209,第一阶段方法,优化目标为逐项之和：,对于固定的 ，,可编辑,210,寻找严格可行解的方法,牛顿法求解优化问题：,迭代终止条件：当前解 ，即终止迭代，严格可行解为 。,可编辑,21

39、1,凸优化理论与应用,复习,可编辑,212,凸集,凸集与凸包的概念；几种常见的凸集多面体、单纯形、范数球、凸锥、真锥、范数锥、半正定锥等；保持凸集的运算集合交运算、仿射变换、透视函数、线性分式函数广义不等式的概念支撑超平面、分割超平面的概念,可编辑,213,凸函数,凸函数的概念及判定；常见凸函数；Jessen不等式；保持函数凸性的算子；共轭函数的概念、常见函数的共轭函数；向量凸函数（广义不等式下的凸性）,可编辑,214,优化问题,优化问题的基本描述、等价形式；凸优化问题的基本描述、等价形式；常见凸优化问题。,可编辑,215,对偶问题,优化问题的拉格朗日函数及对偶函数的概念和性质；一些常见问题的对偶函数；对偶函数与共轭函数的关系；对偶问题的描述；强对偶性的概念及Slater条件；KKT条件。,可编辑,216,常见应用问题,逼近问题的几种基本描述；统计估计问题的基本描述。,可编辑,217,常用算法,无约束问题常用算法：下降法最速下降牛顿法等式约束问题的常用算法等式约束条件的消去牛顿法内点法,