凸优化理论与应用课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,可编辑,1,凸优化理论与应用,庄 伯 金,Bjzhuang,可编辑,2,优化理论概述,什么是优化问题？,Objective function,Constraint functions,可编辑,3,几类经典的优化问题,线性规划问题,最小二乘问题,凸优化问题,凸优化问题理论上有有效的方法进行求解！,可编辑,4,本课程的主要内容,理论部分,凸集和凸函数,凸优化问题,对偶问题,应用部分,逼近与拟合,统计估计,几何问题,算法部分,非约束优化方法,等式约束优化方法,内点法,可编辑,5,熟悉了解凸优化理论的基本原理和基本方法；,掌握实际问题转化为凸优化问题的基本方法；,掌握最优化问题的经典算法。,课程要求,可编辑,6,参考书目,Stephen Boyd and Lieven Vandenberghe,“,Convex Optimization,”,Cambridge University Press,.,袁亚湘、孙文瑜，“最优化理论与方法”，科学出版社，,1999,。,可编辑,7,凸优化理论与应用,第一章,凸集,可编辑,8,仿射集(,Affine sets),直线的表示：,线段的表示：,可编辑,9,仿射集(,Affine sets),仿射集的定义：过集合,C,内任意两点的直线均在集合,C,内，则称集合,C,为仿射集。,仿射集的例：直线、平面、超平面,可编辑,10,仿射集,仿射包：包含集合,C,的最小的仿射集。,仿射维数：仿射包的维数。,可编辑,11,仿射集,内点（,interior,）：,相对内点（,relative interior,）：,可编辑,12,凸集(,Convex Sets),凸集的定义：集合,C,内任意两点间的线段均在集合,C,内，则称集合,C,为凸集。,可编辑,13,凸集,凸包的定义：包含集合,C,的最小的凸集。,可编辑,14,锥(,Cones),锥的定义：,凸锥的定义：集合,C,既是凸集又是锥。,锥包的定义：集合,C,内点的所有锥组合。,可编辑,15,超平面和半空间,超平面(,hyperplane),：,半空间(,Halfspace)：,可编辑,16,欧氏球和椭球,欧氏球(,euclidean ball):,椭球(,ellipsoid):,可编辑,17,范数球和范数锥,范数,(norm),：,范数球,(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),真锥的定义：锥 满足如下条件,K,具有内点,K,内不含直线,可编辑,23,广义不等式,真锥 下的,偏序关系,：,例：,逐项不等式,矩阵不等式,广义不等式,严格广义不等式,可编辑,24,广义不等式的性质,可编辑,25,严格广义不等式的性质,可编辑,26,最值和极值,最小元的定义：设 ，对 ，都有,成立，则称 为 的最小元。,极小元的定义：设 ，对于 ，若,，则 成立，则称 为 的极小元。,可编辑,27,分割超平面(,separating hyperplane),定理：设 和 为两不相交凸集，则存在超平面将 和 分离。即：,可编辑,28,支撑超平面(,supporting hyperplane),定义：设集合 ， 为 边界上的点。若存在 ，满足对任意 ，都有 成立，则称超平面 为集合 在点 处的支撑超平面。,定理：凸集边界上任意一点均存在支撑超平面。,定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。,可编辑,29,对偶锥(,dual cone),对偶锥的定义：设 为锥，则集合,称为对偶锥。,对偶锥的性质：,真锥的对偶锥仍然是真锥！,可编辑,30,对偶广义不等式,广义不等式与对偶等价性质,最小元的对偶特性：,可编辑,31,对偶广义不等式,极小元的对偶特性,反过来不一定成立！,可编辑,32,作业,P60 2.8,P60 2.10,P60 2.14,P62,2.16,P62 2.18,P64 2.30,P64 2.31,P64 2.33,可编辑,33,凸优化理论与应用,第二章,凸函数,可编辑,34,凸函数的定义,1.定义域 为凸集；,2. ，有,凸函数的定义：函数 ，满足,凸函数的扩展定义：若 为凸函数，则可定义其扩展函数 为,凸函数的扩展函数也是凸函数！,可编辑,35,凸函数的一阶微分条件,若函数 的定义域 为开集，且函数 一阶可微，则函数 为凸函数当且仅当 为凸集，且对,可编辑,36,凸函数的二阶微分条件,若函数 的定义域 为开集，且函数 二阶可微，则函数 为凸函数当且仅当 为凸集，且对 ，其,Hessian,矩阵,可编辑,37,凸函数的例,幂函数,负对数函数,负熵函数,范数函数,指数函数,可编辑,38,凸函数的例,可编辑,39,下水平集(,sublevel set),定理：凸函数的任一下水平集均为凸集。,任一下水平集均为凸集的函数,不一定,为凸函数。,称为 的 下水平集。,定义：集合,可编辑,40,函数上半图(,epigraph),定理：函数 为凸函数,当且仅当,的上半图为凸集。,称为函数 的上半图。,定义：集合,可编辑,41,Jensen,不等式,为凸函数，则有：,Jensen,不等式的另外形式：,可编辑,42,保持函数凸性的算子,凸函数的逐点最大值,凸函数与仿射变换的复合,凸函数的非负加权和,可编辑,43,保持函数凸性的算子,复合运算,最小值算子,凸函数的透视算子,可编辑,44,共轭函数,(conjugate function),定义：设函数 ，其共轭函数 ，定义为,共轭函数的例,共轭函数具有凸性！,可编辑,45,共轭函数的性质,Fenchel,s inequality,性质：若 为凸函数，且 的上半图是闭集，则有,性质：设 为凸函数，且可微，对于 ，若,则,可编辑,46,准凸函数(,quasiconvex function),准凸函数的例,定义：设函数 ，若函数的定义域和任意下水平集,则称函数 为准凸函数。,可编辑,47,准凸函数的判定定理,定理：函数 为准凸函数，当且仅当 为凸集，且对 ，有,定理：若函数 一阶可微，则 为准凸函数，当且仅当 为凸集，且对 ，有,，有,定理：若函数 二阶可微，且满足对,则函数 准凸函数。,可编辑,48,最小值函数,非负权值函数的最大值函数,保持准凸性的算子,复合函数,可编辑,49,准凸函数的凸函数族表示,若 为准凸函数，根据 的任意 下水平集，我们可以构造一个凸函数族 ，使得,性质：若 为准凸函数 的凸函数族表示，对每一个 ，若 ，则有,可编辑,50,对数凸函数,为凸集,为凸函数。,定义：函数 称为对数凸函数，若函数 满足：,定理：函数 的定义域为凸集，且 ，则 为对数凸函数，当且仅当对,有,对数凸函数的例,可编辑,51,对数凸函数和凹函数的性质,性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。,定理：函数 二阶可微，则 为对数凸函数当且仅当,性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。,推论：函数 对每一个 在 上对数凸，则函数 也是对数凸函数。,可编辑,52,对数凸函数和凹函数的性质,定理：函数 为对数凹函数，则函数 是对数凹函数。,可编辑,53,广义不等式下的凸性,广义单调性的定义：设 为真锥，函数 称为 单调增，若函数 满足：,广义凸函数的定义：设 为真锥，函数 称为 凸，若函数 满足对,均有,定理(对偶等价,)：,函数 为 凸函数，当且仅当对所有 ， 为凸函数。,可编辑,54,作业(1),P116 3.16,P116 3.21,可编辑,55,作业(2),P121 3.41,P122 3.49 (1)(2),可编辑,56,凸优化理论与应用,第三章,凸优化,可编辑,57,优化问题的基本形式,优化问题的基本描述：,优化变量,不等式约束,等式约束,无约束优化,可编辑,58,优化问题的基本形式,最优化值,最优化解,优化问题的域,可行点(解) (,feasible),满足约束条件,可行域(可解集,),所有可行点的集合,可编辑,59,局部最优问题,局部最优问题,可编辑,60,优化问题的等价形式(1),定理：若,则原优化问题与以下优化问题等价,可编辑,61,优化问题的等价形式(2),定理：设 为一一对应，且,则原优化问题与以下优化问题等价,可编辑,62,优化问题的等价形式(3),定理：设 为严格单调增函数； 满足 当且仅当 ； 满足 当且仅当 。则原优化问题与以下优化问题等价,可编辑,63,优化问题的等价形式(4),定理：原优化问题与以下优化问题等价,称为松弛变量,可编辑,64,优化问题的等价形式(5),定理：设 满足等式 成立，当且仅当 。则原优化问题与以下优化问题等价,可编辑,65,可分离变量优化问题,性质：,其中,可以分离变量,定理：优化问题,可编辑,66,优化问题的上半图形式,可编辑,67,凸优化问题的基本形式,凸优化问题的基本描述：,为仿射函数,为凸函数,若 为准凸函数，则优化问题称为准凸优化问题。,性质：凸优化问题的可行域是凸集。,可编辑,68,凸优化问题的例,例：,等价于凸优化问题,可编辑,69,凸优化问题的局部最优解,定理：凸优化问题的局部最优解均是全局最优解。,可编辑,70,凸优化问题最优解的微分条件,定理：设 为凸优化问题的可行域， 可微。则 为最优解当且仅当 成立。,定理：非约束凸优化问题中，若 可微。则 为最优解当且仅当 成立。,可编辑,71,凸优化问题的等价形式,则 为最优解当且仅当 ，且存在向量 满足,定理：设凸优化问题仅有等式约束,可编辑,72,凸优化问题的等价形式,则 为最优解当且仅当 ，且,定理：设凸优化问题,可编辑,73,凸优化问题的等价形式,等价于,定理：设凸优化问题,其中,可编辑,74,凸优化问题的等价形式,等价于,定理：设凸优化问题,可编辑,75,准凸优化问题,为准凸函数， 为凸函数。,准凸优化问题的基本描述,注：准凸优化问题的局部最优解不一定是全局最优解。,可编辑,76,准凸优化问题的上半图形式,设 为准凸函数 的凸函数族表示，即,则准凸优化问题的可行解问题为,设 为准凸优化问题的最优解，若上述问题可解，则 。否则 。,可编辑,77,准凸优化问题二分法求解,给定一个足够小的 和足够大的 ，使得区间 能包含最优解 。给定,LOOP：,令,求解可行解问题；,若可解，则令 ，否则令,若 ，则结束，否则,goto LOOP。,可编辑,78,线性规划,(linear program,LP),LP,问题的一般描述,可编辑,79,LP,问题的几种类型,标准,LP,问题,不等式形式,LP,问题,可编辑,80,标准,LP,问题的转换,可编辑,81,LP,问题的例,Chebyshev center of a polyhedron,Piecewise-linear minimization,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 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,问题描述,其中 不是完全确定的常数。,例： 为确定的常数， 为变量，其范围满足,SOCP,形式,可编辑,92,几何规划(,Geometric programming,),单项式与多项式,几何规划的基本描述,可编辑,93,几何规划的凸形式转换,令,几何规划的凸形式,可编辑,94,广义不等式约束,广义不等式约束的优化问题,SOCP,的描述,可编辑,95,凸优化理论与应用,第四章,对偶问题,可编辑,96,优化问题的拉格朗日函数,设优化问题：,拉格朗日(,Lagrangian),函数：,对固定的 ，拉格朗日函数 为关于 和 的,仿射函数,。,可编辑,97,拉格朗日对偶函数,拉格朗日对偶函数,(lagrange dual function),：,若拉格朗日函数没有下界，则令,拉格朗日对偶函数为,凹函数,。,对 和 ，若原最优化问题有最优值 ，则,可编辑,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,原问题：,拉格朗日函数：,拉格朗日对偶函数：,可编辑,102,对偶函数与共轭函数,共轭函数,共轭函数与对偶函数存在密切联系,具有线性不等式约束和线性等式约束的优化问题：,对偶函数：,可编辑,103,Equality constrained norm minimization,问题描述：,共轭函数：,对偶函数：,可编辑,104,Entropy maximization,原始问题：,共轭函数：,对偶函数,：,可编辑,105,Minimum volume covering ellipsoid,原始问题：,对偶函数：,共轭函数：,可编辑,106,拉格朗日对偶问题,拉格朗日对偶问题的描述：,对偶可行域,最优值,最优解,可编辑,107,LP,问题的对偶问题,标准,LP,问题,对偶函数,对偶问题,等价描述,可编辑,108,弱对偶性,定理（弱对偶性） ：设原始问题的最优值为 ，对偶问题的最优值为 ，则 成立。,optimal duality gap,可以利用对偶问题找到原始问题最优解的下界。,可编辑,109,强对偶性,强对偶性并不是总是成立的。,定义（强对偶性） ：设原始问题的最优值为 ，对偶问题的最优值为 。若 成立，则称原始问题和对偶问题之间具有,强对偶性,。,凸优化问题,通常（但并不总是）,具有强对偶性。,Slater,定理：若凸优化问题存在严格可行解，即存在 ，满足,则优化问题具有强对偶性。该条件称为,Slater,条件,。,可编辑,110,强对偶性,存在 ，满足,弱化的,Slater,条件：若不等式约束条件的前 个为线性不等式约束条件，则,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 volume covering ellipsoid,原始问题：,对偶函数：,对偶问题：,可编辑,117,Minimum volume covering ellipsoid,弱化的,Slater,条件总成立，因此该优化问题具有强对偶性。,弱化的,Slater,条件：存在 ，满足,可编辑,118,对偶可行解的不等式,对于一优化问题，若 为一可行解， 为对偶问题可行解，则有如下不等式：,为 次优解，其中,不等式可以用于对次优解的精度估计,可编辑,119,互补松弛条件,所以,设 为原始优化问题的最优解， 为对偶问题的最优解，若两者具有强对偶性，则,即,可编辑,120,KKT,优化条件,设优化问题中，函数 可微。设 为原始优化问题的最优解， 为对偶问题的最优解，且两者具有强对偶性，则 满足如下条件：,KKT,条件为必要条件！,可编辑,121,凸优化问题的,KKT,条件,可微。设 满足,KKT,条件，则 为原始问题的最优解，而 为对偶问题的最优解，且两者具有强对偶性。,设原始问题为凸优化问题中，函数,可编辑,122,例,原始凸优化问题,KKT,条件,可编辑,123,例,其中,解得,可编辑,124,凸优化问题的对偶求解,存在唯一解 。若 为原始问题的可行解，则 即为原始问题的最优解；若 不是原始问题的可行解，则原始问题不存在最优解。,设原始优化问题与对偶问题具有强对偶性，且 为对偶问题的最优解。 存在唯一的最小解，即,可编辑,125,扰动问题,扰动问题：,当 时即为原始问题。,若 为正，则第 个不等式约束被放宽；若 为负，则第 个不等式约束被收紧。,记 为扰动问题的最优解。若扰动问题无最优解，则记,可编辑,126,灵敏度分析,设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为 ，则有,若 在 处可微，则,可编辑,127,定义（弱选择性）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。,选择定理,对偶不等式组,设原始问题的约束条件：,对偶问题,原始问题的约束条件与对偶不等式组具有弱选择性。,可编辑,128,选择定理,对偶不等式组,设原始问题的严格不等式约束条件：,原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。,可编辑,129,定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。,选择定理,对偶不等式组,设原始问题为凸优化问题，其严格不等式约束条件为：,若存在 ，满足 ，则上述两不等式约束系统具有强选择性。,可编辑,130,选择定理,对偶不等式组,设原始问题为凸优化问题，其不等式约束条件为：,则原始问题的不等式约束条件与对偶不等式组具有强选择性。,若存在 ，满足 ，且下述优化问题存在最优解,可编辑,131,罚函数的例,范数：,死区线性罚函数：,对数门限罚函数,可编辑,132,鲁棒的罚函数,若 大到一定程度时，罚函数为 的线性函数，则称该罚函数为鲁棒的罚函数。,Huber,罚函数,可编辑,133,最小范数问题,问题描述：,其中 为方程组 的解。,可以消去等式约束将其转换为范数逼近问题：,可编辑,134,最小范数问题,最小平方范数问题：范数 ，最优解满足：,最小罚问题：,绝对值和最小问题：范数 ，原问题可转换为,LP,问题：,可编辑,135,正则逼近,二元矢量优化问题描述：,正则化问题：,最优解描述了两分量的一条折中曲线。,可编辑,136,正则逼近,Tikhonov,正则化问题：,为二次优化问题：,最优解的形式,：,可编辑,137,正则逼近,Tikhonov,光滑正则化问题：,为二阶差分算子：,可编辑,138,信号复原,已知加噪信号：,信号复原问题的描述：,函数 为正则函数或光滑函数。,可编辑,139,信号复原,可编辑,140,信号复原,可编辑,141,信号复原,可编辑,142,鲁棒逼近,问题描述：,随机鲁棒逼近： 为随机变量，逼近问题转换为最小化期望,例：,随机鲁棒逼近为：,转换为,：,可编辑,143,随机鲁棒逼近,为随机变量：,最小平方随机鲁棒逼近为：,转换为,：,其中,可编辑,144,最坏情况鲁棒逼近,考虑 ，最坏情况鲁棒逼近为：,例：,随机鲁棒逼近为：,转换为,：,可编辑,145,凸优化理论与应用,第6章,统计估计,可编辑,146,概率分布的参数估计,随机变量的概率密度为 ，其中 为概率分布的参数，且参数未知。参数估计的目标就是通过一些已知样本估计获得参数的最优近似值。,问题描述,为样本观测值；,为对数似然函数；,若似然函数为凹函数，则优化问题为凸优化问题。,可编辑,147,具有独立同分布噪声的线性测量,线性测量模型：,为观测值或测量值；,为未知参数向量；,独立同分布噪声，其概率密度为 。,似然函数为,最大似然估计问题为：,可编辑,148,例,高斯白噪声,对数似然函数：,区间 上均匀分布的噪声：,对数似然函数：,可编辑,149,逻辑回归,随机变量 的概率分布为：,为参数；,为可观测的解释变量； 为观察值。,对数似然函数,：,可编辑,150,假定测验,随机变量 ，有 种可能（假定）的分布；,假定 ： 的概率分布为,假定测验的目标：由观察值猜测随机变量最有可能服从哪种假定的分布。,当 时，称为二元假定测验。,随机检测子：非负元素矩阵,可编辑,151,假定测验,为当 实际服从第1种假定分布而猜测为第2种假定分布的概率；,为当 实际服从第2种假定分布而猜测为第1种假定分布的概率；,多目标优化形式,：,检测概率矩阵,可编辑,152,假定测验,最小最大值形式,尺度优化形式：,可编辑,153,例,在两种假设下的概率分布为：,可编辑,154,例,可编辑,155,实验设计,线性测量问题,最大似然估计值：,独立同分布高斯白噪声，服从分布 。,估计误差 均值为0，方差为,信赖椭圆为,可编辑,156,实验设计,实验设计的目标：寻找 ，使得误差的方差矩阵最小。,向量优化形式：,为整数问题，求解较困难。,可编辑,157,实验设计,当 时，令 近似为一连续实数，原问题可松弛转换为连续实数优化：,可编辑,158,凸优化理论与应用,第7章,无约束优化,可编辑,159,无约束优化问题,问题描述：,无约束问题求解的两种方法：,迭代逼近：,求解梯度方程：,为凸函数，且二次可微。,可编辑,160,例,梯度方程,二次优化：,可编辑,161,迭代起始点,满足条件2的几种函数：,起始点 满足：,函数 任意下水平集都是闭集；,函数的定义域为,当 时，,可编辑,162,强凸性,定义：函数 在 上具有强凸性，若 满足,若函数 具有强凸性，则有,为最优值，则,可编辑,163,强凸性,则有,为最优值，则,若函数 在 上具有强凸性，则可以证明存在 ，满足,可编辑,164,强凸性,对于 ，矩阵 的特征值从大到小依次为 。则有：,定义：矩阵 的条件数为最大特征值与最小特征值之比，即 。,条件数的上界：,可编辑,165,下降法,下降法的基本原理：,迭代 ，满足,为下降方向， 为步长因子,。,对于凸函数 ，当 满足 时，存在某个 ，使得 。,可编辑,166,下降法,下降法的一般步骤：,给出初始点 ；,循环迭代,计算下降方向 ；,搜索步长因子 ；,迭代：,可编辑,167,步长因子搜索,精确一维搜索：,回溯一维搜索：给定参数,循环迭代,初始化：令 ；,若 ，则终止退出；,否则令,可编辑,168,步长因子搜索,可编辑,169,梯度下降法,算法简单，但收敛速度较慢。,下降方向：,终止条件：,收敛性：,其中 。,可编辑,170,收敛性分析,则有：,设函数 具有强凸性，则存在 和 ，满足：,若 采用精确一维搜索，则 ，收敛速度因子：,若 采用回溯一维搜索，收敛速度因子：,条件数越大，收敛速度越小。,可编辑,171,例,当 时，算法收敛速度很慢。,初始解为 ，采用精确一维搜索；,迭代：,可编辑,172,例,步长因子采用回溯一维搜索。,可编辑,173,最速下降法,归一化最速下降方向：,非归一化最速下降方向,欧式范数：,二次范数 ：,范数：,可编辑,174,最速下降法,可编辑,175,收敛性分析,范数界：,收敛速度因子：,可编辑,176,牛顿法,设函数 二阶可微，则在 附近， 的泰勒展式为：,泰勒展开可作为 在 附近的近似；,下降方向：,为二次范数 上的最速下降方向。,可编辑,177,牛顿法,可编辑,178,牛顿减量,令,为 在 处的牛顿减量。,牛顿减量的性质1：,性质2：,牛顿减量可作为迭代求解的误差估计。,性质3：牛顿减量具有仿射不变性。,可编辑,179,牛顿方法,初始化：给定初始解 以及,LOOP：,计算：,若 则终止退出；,一维线性搜索：计算步长因子 ；,迭代：,可编辑,180,收敛性分析,定理：假设 二阶连续可微，具有强凸性，即存在 ，满足：,则存在 ，,且海森矩阵满足,Lipschitz,条件，即存在 ，满足：,若 ，则 ；,若 ，则 ，且,可编辑,181,收敛性分析,定理：假设 二阶连续可微，具有强凸性，即存在 ，满足：,则存在 ，对于 ，有,且海森矩阵满足,Lipschitz,条件，即存在 ，满足：,可编辑,182,例,可编辑,183,凸优化理论与应用,第8章,等式约束优化,可编辑,184,等式约束优化问题,问题描述：,为凸函数，且二次连续可微，且,假设最优值 存在，则 为最优解当且仅当存在 ，满足（,KKT,条件）：,可编辑,185,例,KKT,系统：,二次优化：,KKT,系统可解，则二次优化问题存在最优解。,系数矩阵称为,KKT,矩阵。,KKT,矩阵非奇异当且仅当：,可编辑,186,消去等式约束,方程组 的解集：,为方程组的一个特解， 为 的零空间范围。,无约束优化形式：,若 为最优解，则有,可编辑,187,对偶问题,对偶形式：,可编辑,188,牛顿法,牛顿减量,为等式约束优化的可行解，则在 附近原问题的二次近似为：,设 和 分别为该问题和对偶问题的最优解，则满足：,可编辑,189,性质2：牛顿减量具有仿射不变性。,牛顿减量,牛顿减量,牛顿减量的性质：,可编辑,190,可行下降方向,可行下降方向：设 满足方程组 。若 满足方程组 ，则 。 称为可行方向。若对于较小的 ，有 ，则 为可行下降方向。,可编辑,191,等式约束的牛顿方法,LOOP：,计算 及 ；,若 则终止退出；,一维线性搜索：计算步长因子 ；,迭代：,初始化：给定初始解 满足 ，以及,可编辑,192,消去等式约束的牛顿方法,转换为等式约束下的牛顿方法：,初始值 ，第 次迭代值 ；,初始值：,迭代值：,可编辑,193,非可行解为初始点的牛顿法,函数 二阶连续可微，因此有,为等式约束优化的非可行解，则增量 应尽可能使 满足,KKT,条件，即：,设 和 为,KKT,条件的解，即有：,可编辑,194,非可行解为初始点的牛顿法,则,KKT,条件可表示为：,令,设 为不满足,KKT,条件，则其迭代量需满足：,即,可编辑,195,当 且 时，终止迭代。,非可行解为初始点的牛顿法,LOOP：,计算 和 ；,回溯一维线性搜索：,迭代：,初始化：给定初始解 及 ，以及,令 ；,While,可编辑,196,其中 ，且满足 。,KKT,系统的求解,1.,分解；,2.若 非奇异，则可消元：,3.若 奇异，则,KKT,系统可改写为：,KKT,系统：,可编辑,197,凸优化理论与应用,第9章,内点法,可编辑,198,则优化问题具有强对偶性，其对偶问题亦可解。,假设存在 ，满足严格不等式条件,不等式约束优化问题,问题描述：,为凸函数，且二次连续可微，且,假设最优值 存在；,可编辑,199,不具备良好的连续可微性，考虑用对数阀函数来近似替代。,不等式约束的消去,示性函数消去不等式约束：,可编辑,200,令,对数阀函数,对于 ， 是 的光滑逼近。且当 时，有,带示性函数的优化问题可近似为：,可编辑,201,对数阀函数二阶连续可微，导数为：,对数阀函数,对数阀函数 是凸函数,可编辑,202,中心线,对数阀近似问题的等价问题：,最优解为 ，则最优解集 称为优化问题的中心线。,可编辑,203,中心线的对偶点,设 ，则存在 满足,KKT,条件：,为对偶问题的可行解。,令,则 是拉格朗日函数 的最小值解。,可编辑,204,中心线的对偶点,设 为原始问题的最优值，则有：,因此，当 时，有 。 为原始问题的 次优解。,可编辑,205,更新 ：,阀方法,初始化：给定严格可行解 ， ， ，及,LOOP：,中心步骤：以 为初始点求解优化问题 ，,迭代：,终止条件：若 ，则终止退出。,可编辑,206,收敛性分析,外层循环迭代次数：,中心步骤实质为一个无约束或等式约束优化问题，其收敛性分析与相应优化问题的收敛性分析结果一致。,可编辑,207,例：,LP,问题：,初始值：,可编辑,208,当 时，原始问题不可解；,当 时，无法准确确定。,第一阶段方法,对于不等式约束的优化问题，如何寻找严格可行解或验证不可解？,求解优化问题：,该问题最优解存在，假设最优值为,当 时，存在严格可行解；,可编辑,209,第一阶段方法,优化目标为逐项之和：,对于固定的 ，,可编辑,210,寻找严格可行解的方法,牛顿法求解优化问题：,迭代终止条件：当前解 ，即终止迭代，严格可行解为 。,可编辑,211,凸优化理论与应用,复习,可编辑,212,凸集,凸集与凸包的概念；,几种常见的凸集,多面体、单纯形、范数球、凸锥、真锥、范数锥、半正定锥等；,保持凸集的运算,集合交运算、仿射变换、透视函数、线性分式函数,广义不等式的概念,支撑超平面、分割超平面的概念,可编辑,213,凸函数,凸函数的概念及判定；,常见凸函数；,Jessen,不等式；,保持函数凸性的算子；,共轭函数的概念、常见函数的共轭函数；,向量凸函数（广义不等式下的凸性）,可编辑,214,优化问题,优化问题的基本描述、等价形式；,凸优化问题的基本描述、等价形式；,常见凸优化问题。,可编辑,215,对偶问题,优化问题的拉格朗日函数及对偶函数的概念和性质；,一些常见问题的对偶函数；,对偶函数与共轭函数的关系；,对偶问题的描述；,强对偶性的概念及,Slater,条件；,KKT,条件。,可编辑,216,常见应用问题,逼近问题的几种基本描述；,统计估计问题的基本描述。,可编辑,217,常用算法,无约束问题常用算法：,下降法,最速下降,牛顿法,等式约束问题的常用算法,等式约束条件的消去,牛顿法,内点法,