凸优化理论与应用归纳课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 bjzhuang,*,精选,凸优化理论与应用,庄 伯 金,Bjzhuang,精选凸优化理论与应用庄 伯 金,精选,优化理论概述,什么是优化问题？,Objective function,Constraint functions,精选优化理论概述什么是优化问题？Objective func,精选,几类经典的优化问题,线性规划问题,最小二乘问题,凸优化问题,凸优化问题理论上有有效的方法进行求解！,精选几类经典的优化问题线性规划问题最小二乘问题凸优化问题凸优,精选,本课程的主要内容,理论部分,凸集和凸函数,凸优化问题,对偶问题,应用部分,逼近与拟合,统计估计,几何问题,算法部分,非约束优化方法,等式约束优化方法,内点法,精选本课程的主要内容理论部分,精选,熟悉了解凸优化理论的基本原理和基本方法；,掌握实际问题转化为凸优化问题的基本方法；,掌握最优化问题的经典算法。,课程要求,精选熟悉了解凸优化理论的基本原理和基本方法；课程要求,精选,参考书目,Stephen Boyd and Lieven Vandenberghe,“,Convex Optimization,”,Cambridge University Press,.,袁亚湘、孙文瑜，“最优化理论与方法”，科学出版社，,1999,。,精选参考书目Stephen Boyd and Lieven,精选,凸优化理论与应用,第一章,凸集,精选凸优化理论与应用第一章,精选,仿射集(,Affine sets),直线的表示：,线段的表示：,精选仿射集(Affine sets)直线的表示：线段的表示：,精选,仿射集(,Affine sets),仿射集的定义：过集合,C,内任意两点的直线均在集合,C,内，则称集合,C,为仿射集。,仿射集的例：直线、平面、超平面,精选仿射集(Affine sets)仿射集的定义：过集合C内,精选,仿射集,仿射包：包含集合,C,的最小的仿射集。,仿射维数：仿射包的维数。,精选仿射集仿射包：包含集合C的最小的仿射集。仿射维数：仿射包,精选,仿射集,内点（,interior,）：,相对内点（,relative interior,）：,精选仿射集内点（interior）：相对内点（relativ,精选,凸集(,Convex Sets),凸集的定义：集合,C,内任意两点间的线段均在集合,C,内，则称集合,C,为凸集。,精选凸集(Convex Sets)凸集的定义：集合C内任意两,精选,凸集,凸包的定义：包含集合,C,的最小的凸集。,精选凸集凸包的定义：包含集合C的最小的凸集。,精选,锥(,Cones),锥的定义：,凸锥的定义：集合,C,既是凸集又是锥。,锥包的定义：集合,C,内点的所有锥组合。,精选锥(Cones)锥的定义：凸锥的定义：集合C既是凸集又是,精选,超平面和半空间,超平面(,hyperplane),：,半空间(,Halfspace)：,精选超平面和半空间超平面(hyperplane)：半空间(,精选,欧氏球和椭球,欧氏球(,euclidean ball):,椭球(,ellipsoid):,精选欧氏球和椭球欧氏球(euclidean ball):椭球,精选,范数球和范数锥,范数,(norm),：,范数球,(norm ball),：,范数锥,(norm cone),：,精选范数球和范数锥范数(norm)：范数球(norm bal,精选,多面体,(Polyhedra),多面体：,单纯形,(simplex),：,精选多面体(Polyhedra)多面体：单纯形(simple,精选,半正定锥,(Positive semidefinite cone),n,阶对称矩阵集：,n,阶半正定矩阵集：,n,阶正定矩阵集：,n,阶半正定矩阵集为凸锥！,精选半正定锥(Positive semidefinite c,精选,保持凸性的运算,集合交运算,仿射变换,透视,/,投射函数,(,perspective function,),精选保持凸性的运算集合交运算,精选,保持凸性的运算,线性分式函数,(,linear-fractional function,),精选保持凸性的运算线性分式函数(linear-fractio,精选,真锥(,proper cone),真锥的定义：锥 满足如下条件,K,具有内点,K,内不含直线,精选真锥(proper cone)真锥的定义：锥,精选,广义不等式,真锥 下的,偏序关系,：,例：,逐项不等式,矩阵不等式,广义不等式,严格广义不等式,精选广义不等式真锥 下的偏序关系：例：广义不等式严格广,精选,广义不等式的性质,精选广义不等式的性质,精选,严格广义不等式的性质,精选严格广义不等式的性质,精选,最值和极值,最小元的定义：设 ，对 ，都有,成立，则称 为 的最小元。,极小元的定义：设 ，对于 ，若,，则 成立，则称 为 的极小元。,精选最值和极值最小元的定义：设 ，对,精选,分割超平面(,separating hyperplane),定理：设 和 为两不相交凸集，则存在超平面将 和 分离。即：,精选分割超平面(separating hyperplane),精选,支撑超平面(,supporting hyperplane),定义：设集合 ，为 边界上的点。若存在 ，满足对任意 ，都有 成立，则称超平面 为集合 在点 处的支撑超平面。,定理：凸集边界上任意一点均存在支撑超平面。,定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。,精选支撑超平面(supporting hyperplane),精选,对偶锥(,dual cone),对偶锥的定义：设 为锥，则集合,称为对偶锥。,对偶锥的性质：,真锥的对偶锥仍然是真锥！,精选对偶锥(dual cone)对偶锥的定义：设 为锥，,精选,对偶广义不等式,广义不等式与对偶等价性质,最小元的对偶特性：,精选对偶广义不等式广义不等式与对偶等价性质最小元的对偶特性：,精选,对偶广义不等式,极小元的对偶特性,反过来不一定成立！,精选对偶广义不等式极小元的对偶特性反过来不一定成立！,精选,作业,P60 2.8,P60 2.10,P60 2.14,P62,2.16,P62 2.18,P64 2.30,P64 2.31,P64 2.33,精选作业P60 2.8,精选,凸优化理论与应用,第二章,凸函数,精选凸优化理论与应用第二章 凸函数,精选,凸函数的定义,1.定义域 为凸集；,2.，有,凸函数的定义：函数 ，满足,凸函数的扩展定义：若 为凸函数，则可定义其扩展函数 为,凸函数的扩展函数也是凸函数！,精选凸函数的定义1.定义域 为凸集；2.,精选,凸函数的一阶微分条件,若函数 的定义域 为开集，且函数 一阶可微，则函数 为凸函数当且仅当 为凸集，且对,精选凸函数的一阶微分条件若函数 的定义域,精选,凸函数的二阶微分条件,若函数 的定义域 为开集，且函数 二阶可微，则函数 为凸函数当且仅当 为凸集，且对 ，其,Hessian,矩阵,精选凸函数的二阶微分条件若函数 的定义域,精选,凸函数的例,幂函数,负对数函数,负熵函数,范数函数,指数函数,精选凸函数的例幂函数负对数函数负熵函数范数函数指数函数,精选,凸函数的例,精选凸函数的例,精选,下水平集(sublevel set),定理：凸函数的任一下水平集均为凸集。,任一下水平集均为凸集的函数,不一定,为凸函数。,称为 的 下水平集。,定义：集合,精选下水平集(sublevel set)定理：凸函数的任一下,精选,函数上半图(epigraph),定理：函数 为凸函数,当且仅当,的上半图为凸集。,称为函数 的上半图。,定义：集合,精选函数上半图(epigraph)定理：函数 为凸函数,精选,Jensen不等式,为凸函数，则有：,Jensen,不等式的另外形式：,精选Jensen不等式 为凸函数，则有：Jensen不等,精选,保持函数凸性的算子,凸函数的逐点最大值,凸函数与仿射变换的复合,凸函数的非负加权和,精选保持函数凸性的算子凸函数的逐点最大值凸函数与仿射变换的复,精选,保持函数凸性的算子,复合运算,最小值算子,凸函数的透视算子,精选保持函数凸性的算子复合运算最小值算子凸函数的透视算子,精选,共轭函数(conjugate function),定义：设函数 ，其共轭函数 ，定义为,共轭函数的例,共轭函数具有凸性！,精选共轭函数(conjugate function)定义：设,精选,共轭函数的性质,Fenchel,s inequality,性质：若 为凸函数，且 的上半图是闭集，则有,性质：设 为凸函数，且可微，对于 ，若,则,精选共轭函数的性质Fenchels inequality性,精选,准凸函数(,quasiconvex function),准凸函数的例,定义：设函数 ，若函数的定义域和任意下水平集,则称函数 为准凸函数。,精选准凸函数(quasiconvex function)准凸,精选,准凸函数的判定定理,定理：函数 为准凸函数，当且仅当 为凸集，且对 ，有,定理：若函数 一阶可微，则 为准凸函数，当且仅当 为凸集，且对 ，有,，有,定理：若函数 二阶可微，且满足对,则函数 准凸函数。,精选准凸函数的判定定理定理：函数 为准凸函数，,精选,最小值函数,非负权值函数的最大值函数,保持准凸性的算子,复合函数,精选最小值函数非负权值函数的最大值函数保持准凸性的算子复合函,精选,准凸函数的凸函数族表示,若 为准凸函数，根据 的任意 下水平集，我们可以构造一个凸函数族 ，使得,性质：若 为准凸函数 的凸函数族表示，对每一个 ，若 ，则有,精选准凸函数的凸函数族表示若 为准凸函数，根,精选,对数凸函数,为凸集,为凸函数。,定义：函数 称为对数凸函数，若函数 满足：,定理：函数 的定义域为凸集，且 ，则 为对数凸函数，当且仅当对,有,对数凸函数的例,精选对数凸函数 为凸集为凸函数,精选,对数凸函数和凹函数的性质,性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。,定理：函数 二阶可微，则 为对数凸函数当且仅当,性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。,推论：函数 对每一个 在 上对数凸，则函数 也是对数凸函数。,精选对数凸函数和凹函数的性质性质：对数凸性与凹性对函数乘积和,精选,对数凸函数和凹函数的性质,定理：函数 为对数凹函数，则函数 是对数凹函数。,精选对数凸函数和凹函数的性质定理：函数,精选,广义不等式下的凸性,广义单调性的定义：设 为真锥，函数 称为 单调增，若函数 满足：,广义凸函数的定义：设 为真锥，函数 称为 凸，若函数 满足对,均有,定理(对偶等价,)：,函数 为 凸函数，当且仅当对所有 ，为凸函数。,精选广义不等式下的凸性广义单调性的定义：设,精选,作业(1),P116 3.16,P116 3.21,精选作业(1)P116 3.16,精选,作业(2),P121 3.41,P122 3.49 (1)(2),精选作业(2)P121 3.41,精选,凸优化理论与应用,第三章,凸优化,精选凸优化理论与应用第三章 凸优化,精选,优化问题的基本形式,优化问题的基本描述：,优化变量,不等式约束,等式约束,无约束优化,精选优化问题的基本形式优化问题的基本描述：优化变量不等式约束,精选,优化问题的基本形式,最优化值,最优化解,优化问题的域,可行点(解)(,feasible),满足约束条件,可行域(可解集,),所有可行点的集合,精选优化问题的基本形式最优化值最优化解 优化问题的域,精选,局部最优问题,局部最优问题,精选局部最优问题局部最优问题,精选,优化问题的等价形式(1),定理：若,则原优化问题与以下优化问题等价,精选优化问题的等价形式(1)定理：若 则原优化问题与以下,精选,优化问题的等价形式(2),定理：设 为一一对应，且,则原优化问题与以下优化问题等价,精选优化问题的等价形式(2)定理：设,精选,优化问题的等价形式(3),定理：设 为严格单调增函数；满足 当且仅当 ；满足 当且仅当 。则原优化问题与以下优化问题等价,精选优化问题的等价形式(3)定理：设,精选,优化问题的等价形式(4),定理：原优化问题与以下优化问题等价,称为松弛变量,精选优化问题的等价形式(4)定理：原优化问题与以下优化问题等,精选,优化问题的等价形式(5),定理：设 满足等式 成立，当且仅当 。则原优化问题与以下优化问题等价,精选优化问题的等价形式(5)定理：设,精选,可分离变量优化问题,性质：,其中,可以分离变量,定理：优化问题,精选可分离变量优化问题性质：其中可以分离变量定理：优化问,精选,优化问题的上半图形式,精选优化问题的上半图形式,精选,凸优化问题的基本形式,凸优化问题的基本描述：,为仿射函数,为凸函数,若 为准凸函数，则优化问题称为准凸优化问题。,性质：凸优化问题的可行域是凸集。,精选凸优化问题的基本形式凸优化问题的基本描述：,精选,凸优化问题的例,例：,等价于凸优化问题,精选凸优化问题的例例：等价于凸优化问题,精选,凸优化问题的局部最优解,定理：凸优化问题的局部最优解均是全局最优解。,精选凸优化问题的局部最优解定理：凸优化问题的局部最优解均是全,精选,凸优化问题最优解的微分条件,定理：设 为凸优化问题的可行域，可微。则 为最优解当且仅当 成立。,定理：非约束凸优化问题中，若 可微。则 为最优解当且仅当 成立。,精选凸优化问题最优解的微分条件定理：设 为凸优化问题的,精选,凸优化问题的等价形式,则 为最优解当且仅当 ，且存在向量 满足,定理：设凸优化问题仅有等式约束,精选凸优化问题的等价形式则 为最优解当且仅当,精选,凸优化问题的等价形式,则 为最优解当且仅当 ，且,定理：设凸优化问题,精选凸优化问题的等价形式则 为最优解当且仅当,精选,凸优化问题的等价形式,等价于,定理：设凸优化问题,其中,精选凸优化问题的等价形式等价于 定理：设凸优化问,精选,凸优化问题的等价形式,等价于,定理：设凸优化问题,精选凸优化问题的等价形式等价于 定理：设凸优化问,精选,准凸优化问题,为准凸函数，为凸函数。,准凸优化问题的基本描述,注：准凸优化问题的局部最优解不一定是全局最优解。,精选准凸优化问题 为准凸函数，,精选,准凸优化问题的上半图形式,设 为准凸函数 的凸函数族表示，即,则准凸优化问题的可行解问题为,设 为准凸优化问题的最优解，若上述问题可解，则 。否则 。,精选准凸优化问题的上半图形式设 为准凸函数,精选,准凸优化问题二分法求解,给定一个足够小的 和足够大的 ，使得区间 能包含最优解 。给定,LOOP：,令,求解可行解问题；,若可解，则令 ，否则令,若 ，则结束，否则,goto LOOP。,精选准凸优化问题二分法求解给定一个足够小的 和足够大的,精选,线性规划(linear program,LP),LP,问题的一般描述,精选线性规划(linear program,LP)LP问题的,精选,LP问题的几种类型,标准,LP,问题,不等式形式,LP,问题,精选LP问题的几种类型标准LP问题不等式形式LP问题,精选,标准LP问题的转换,精选标准LP问题的转换,精选,LP问题的例,Chebyshev center of a polyhedron,Piecewise-linear minimization,Linear-fractional programming,精选LP问题的例Chebyshev center of a,精选,Chebyshev center of a polyhedron,多面体,Chebyshev center,：到多面体边界距离最大的内点（最深的点）,问题描述,LP,形式,精选Chebyshev center of a polyhe,精选,Piecewise-linear minimization,问题描述,上半图形式,LP,形式,精选Piecewise-linear minimizatio,精选,Linear-fractional programming,问题描述,LP,形式,精选Linear-fractional programmin,精选,二次规划(,quadratic program,QP,),QP,问题的基本描述,精选二次规划(quadratic program,QP)QP,精选,二次约束二次规划,quadratically constrained quadratic program(QCQP),精选二次约束二次规划quadratically constr,精选,QP,问题的例,Least-squares and regression,Distance between polyhedra,精选QP问题的例Least-squares and regr,精选,Least-squares and regression,问题描述,精选Least-squares and regression,精选,Distance between polyhedra,问题描述,QP,形式,精选Distance between polyhedra问题,精选,Second-order cone program,SOCP,SOCP,问题的基本描述,二次锥约束条件,精选Second-order cone program,S,精选,SOCP,问题的例,Robust linear programming,问题描述,其中 不是完全确定的常数。,例：为确定的常数，为变量，其范围满足,SOCP,形式,精选SOCP问题的例Robust linear progr,精选,几何规划(,Geometric programming,),单项式与多项式,几何规划的基本描述,精选几何规划(Geometric programming)单,精选,几何规划的凸形式转换,令,几何规划的凸形式,精选几何规划的凸形式转换令几何规划的凸形式,精选,广义不等式约束,广义不等式约束的优化问题,SOCP,的描述,精选广义不等式约束广义不等式约束的优化问题SOCP的描述,精选,凸优化理论与应用,第四章,对偶问题,精选凸优化理论与应用第四章 对偶问题,精选,优化问题的拉格朗日函数,设优化问题：,拉格朗日(,Lagrangian),函数：,对固定的 ，拉格朗日函数 为关于 和 的,仿射函数,。,精选优化问题的拉格朗日函数设优化问题：拉格朗日(Lagran,精选,拉格朗日对偶函数,拉格朗日对偶函数,(lagrange dual function),：,若拉格朗日函数没有下界，则令,拉格朗日对偶函数为,凹函数,。,对 和 ，若原最优化问题有最优值 ，则,精选拉格朗日对偶函数拉格朗日对偶函数(lagrange du,精选,对偶函数的例,Least-squares solution of linear equations,Standard form LP,Two-way partitioning problem,精选对偶函数的例Least-squares solution,精选,Least-squares solution of linear equations,原问题：,拉格朗日函数：,拉格朗日对偶函数：,精选Least-squares solution of li,精选,Standard form LP,原问题：,拉格朗日函数：,拉格朗日对偶函数：,精选Standard form LP原问题：拉格朗日函数：拉,精选,Two-way partitioning problem,原问题：,拉格朗日函数：,拉格朗日对偶函数：,精选Two-way partitioning problem,精选,对偶函数与共轭函数,共轭函数,共轭函数与对偶函数存在密切联系,具有线性不等式约束和线性等式约束的优化问题：,对偶函数：,精选对偶函数与共轭函数共轭函数共轭函数与对偶函数存在密切联系,精选,Equality constrained norm minimization,问题描述：,共轭函数：,对偶函数：,精选Equality constrained norm mi,精选,Entropy maximization,原始问题：,共轭函数：,对偶函数,：,精选Entropy maximization原始问题：共轭函,精选,Minimum volume covering ellipsoid,原始问题：,对偶函数：,共轭函数：,精选Minimum volume covering elli,精选,拉格朗日对偶问题,拉格朗日对偶问题的描述：,对偶可行域,最优值,最优解,精选拉格朗日对偶问题拉格朗日对偶问题的描述：对偶可行域最优值,精选,LP问题的对偶问题,标准,LP,问题,对偶函数,对偶问题,等价描述,精选LP问题的对偶问题标准LP问题对偶函数对偶问题等价描述,精选,弱对偶性,定理（弱对偶性）：设原始问题的最优值为 ，对偶问题的最优值为 ，则 成立。,optimal duality gap,可以利用对偶问题找到原始问题最优解的下界。,精选弱对偶性定理（弱对偶性）：设原始问题的最优值为,精选,强对偶性,强对偶性并不是总是成立的。,定义（强对偶性）：设原始问题的最优值为 ，对偶问题的最优值为 。若 成立，则称原始问题和对偶问题之间具有,强对偶性,。,凸优化问题,通常（但并不总是）,具有强对偶性。,Slater,定理：若凸优化问题存在严格可行解，即存在 ，满足,则优化问题具有强对偶性。该条件称为,Slater,条件,。,精选强对偶性强对偶性并不是总是成立的。定义（强对偶性）：设,精选,强对偶性,存在 ，满足,弱化的,Slater,条件：若不等式约束条件的前 个为线性不等式约束条件，则,Slater,条件可以弱化为：,精选强对偶性存在 ，满足,精选,Least-squares solution of linear equations,原问题：,对偶问题：,具有强对偶性,精选Least-squares solution of li,精选,Lagrange dual of QCQP,QCQP,：,拉格朗日函数：,对偶函数：,精选Lagrange dual of QCQPQCQP：拉格,精选,Lagrange dual of QCQP,对偶问题,：,Slater,条件：存在 ，满足,精选Lagrange dual of QCQP对偶问题：Sl,精选,Entropy maximization,原始问题：,对偶函数：,对偶问题,：,精选Entropy maximization原始问题：对偶函,精选,Entropy maximization,弱化的,Slater,条件：存在 ，满足,精选Entropy maximization弱化的Slate,精选,Minimum volume covering ellipsoid,原始问题：,对偶函数：,对偶问题：,精选Minimum volume covering elli,精选,Minimum volume covering ellipsoid,弱化的,Slater,条件总成立，因此该优化问题具有强对偶性。,弱化的,Slater,条件：存在 ，满足,精选Minimum volume covering elli,精选,对偶可行解的不等式,对于一优化问题，若 为一可行解，为对偶问题可行解，则有如下不等式：,为 次优解，其中,不等式可以用于对次优解的精度估计,精选对偶可行解的不等式对于一优化问题，若 为一可行解，,精选,互补松弛条件,所以,设 为原始优化问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则,即,精选互补松弛条件所以设 为原始优化问题的最优解，,精选,KKT,优化条件,设优化问题中，函数 可微。设 为原始优化问题的最优解，为对偶问题的最优解，且两者具有强对偶性，则 满足如下条件：,KKT,条件为必要条件！,精选KKT优化条件设优化问题中，函数,精选,凸优化问题的,KKT,条件,可微。设 满足,KKT,条件，则 为原始问题的最优解，而 为对偶问题的最优解，且两者具有强对偶性。,设原始问题为凸优化问题中，函数,精选凸优化问题的KKT条件可微。设,精选,例,原始凸优化问题,KKT,条件,精选例原始凸优化问题KKT条件,精选,例,其中,解得,精选例其中解得,精选,凸优化问题的对偶求解,存在唯一解 。若 为原始问题的可行解，则 即为原始问题的最优解；若 不是原始问题的可行解，则原始问题不存在最优解。,设原始优化问题与对偶问题具有强对偶性，且 为对偶问题的最优解。存在唯一的最小解，即,精选凸优化问题的对偶求解存在唯一解 。若,精选,扰动问题,扰动问题：,当 时即为原始问题。,若 为正，则第 个不等式约束被放宽；若 为负，则第 个不等式约束被收紧。,记 为扰动问题的最优解。若扰动问题无最优解，则记,精选扰动问题扰动问题：当,精选,灵敏度分析,设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为 ，则有,若 在 处可微，则,精选灵敏度分析设对偶问题存在最优解，且与原始问题具有强对偶性,精选,定义（弱选择性）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。,选择定理,对偶不等式组,设原始问题的约束条件：,对偶问题,原始问题的约束条件与对偶不等式组具有弱选择性。,精选定义（弱选择性）：若两个不等式（等式）系统，至多有一个可,精选,选择定理,对偶不等式组,设原始问题的严格不等式约束条件：,原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。,精选选择定理对偶不等式组设原始问题的严格不等式约束条件：原始,精选,定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。,选择定理,对偶不等式组,设原始问题为凸优化问题，其严格不等式约束条件为：,若存在 ，满足 ，则上述两不等式约束系统具有强选择性。,精选定义（强选择性）：若两个不等式（等式）系统，恰有一个可解,精选,选择定理,对偶不等式组,设原始问题为凸优化问题，其不等式约束条件为：,则原始问题的不等式约束条件与对偶不等式组具有强选择性。,若存在 ，满足 ，且下述优化问题存在最优解,精选选择定理对偶不等式组设原始问题为凸优化问题，其不等式约束,精选,罚函数的例,范数：,死区线性罚函数：,对数门限罚函数,精选罚函数的例 范数：死区线性罚,精选,鲁棒的罚函数,若 大到一定程度时，罚函数为 的线性函数，则称该罚函数为鲁棒的罚函数。,Huber,罚函数,精选鲁棒的罚函数若 大到一定程度时，罚函数为,精选,最小范数问题,问题描述：,其中 为方程组 的解。,可以消去等式约束将其转换为范数逼近问题：,精选最小范数问题问题描述：其中 为方程组,精选,最小范数问题,最小平方范数问题：范数 ，最优解满足：,最小罚问题：,绝对值和最小问题：范数 ，原问题可转换为,LP,问题：,精选最小范数问题最小平方范数问题：范数 ，最优,精选,正则逼近,二元矢量优化问题描述：,正则化问题：,最优解描述了两分量的一条折中曲线。,精选正则逼近二元矢量优化问题描述：正则化问题：最优解描述了,精选,正则逼近,Tikhonov,正则化问题：,为二次优化问题：,最优解的形式,：,精选正则逼近Tikhonov正则化问题：为二次优化问题：,精选,正则逼近,Tikhonov,光滑正则化问题：,为二阶差分算子：,精选正则逼近Tikhonov光滑正则化问题：为二,精选,信号复原,已知加噪信号：,信号复原问题的描述：,函数 为正则函数或光滑函数。,精选信号复原已知加噪信号：信号复原问题的描述：函数,精选,信号复原,精选信号复原,精选,信号复原,精选信号复原,精选,信号复原,精选信号复原,精选,鲁棒逼近,问题描述：,随机鲁棒逼近：为随机变量，逼近问题转换为最小化期望,例：,随机鲁棒逼近为：,转换为,：,精选鲁棒逼近问题描述：随机鲁棒逼近：为随机变量，逼近问,精选,随机鲁棒逼近,为随机变量：,最小平方随机鲁棒逼近为：,转换为,：,其中,精选随机鲁棒逼近 为随机变量：最小平方随机鲁棒逼近,精选,最坏情况鲁棒逼近,考虑 ，最坏情况鲁棒逼近为：,例：,随机鲁棒逼近为：,转换为,：,精选最坏情况鲁棒逼近考虑 ，最坏情况鲁,精选,凸优化理论与应用,第6章,统计估计,精选凸优化理论与应用第6章 统计估计,精选,概率分布的参数估计,随机变量的概率密度为 ，其中 为概率分布的参数，且参数未知。参数估计的目标就是通过一些已知样本估计获得参数的最优近似值。,问题描述,为样本观测值；,为对数似然函数；,若似然函数为凹函数，则优化问题为凸优化问题。,精选概率分布的参数估计随机变量的概率密度为 ，,精选,具有独立同分布噪声的线性测量,线性测量模型：,为观测值或测量值；,为未知参数向量；,独立同分布噪声，其概率密度为 。,似然函数为,最大似然估计问题为：,精选具有独立同分布噪声的线性测量线性测量模型：为观测,精选,例,高斯白噪声,对数似然函数：,区间 上均匀分布的噪声：,对数似然函数：,精选例高斯白噪声对数似然函数：区间,精选,逻辑回归,随机变量 的概率分布为：,为参数；,为可观测的解释变量；为观察值。,对数似然函数,：,精选逻辑回归随机变量 的概率分布为,精选,假定测验,随机变量 ，有 种可能（假定）的分布；,假定 ：的概率分布为,假定测验的目标：由观察值猜测随机变量最有可能服从哪种假定的分布。,当 时，称为二元假定测验。,随机检测子：非负元素矩阵,精选假定测验随机变量,精选,假定测验,为当 实际服从第1种假定分布而猜测为第2种假定分布的概率；,为当 实际服从第2种假定分布而猜测为第1种假定分布的概率；,多目标优化形式,：,检测概率矩阵,精选假定测验 为当 实际服从第1种假定分布而猜,精选,假定测验,最小最大值形式,尺度优化形式：,精选假定测验最小最大值形式尺度优化形式：,精选,例,在两种假设下的概率分布为：,精选例 在两种假设下的概率分布为：,精选,例,精选例,精选,实验设计,线性测量问题,最大似然估计值：,独立同分布高斯白噪声，服从分布 。,估计误差 均值为0，方差为,信赖椭圆为,精选实验设计线性测量问题最大似然估计值：独立同分布高,精选,实验设计,实验设计的目标：寻找 ，使得误差的方差矩阵最小。,向量优化形式：,为整数问题，求解较困难。,精选实验设计实验设计的目标：寻找,精选,实验设计,当 时，令 近似为一连续实数，原问题可松弛转换为连续实数优化：,精选实验设计当 时，令,精选,凸优化理论与应用,第7章,无约束优化,精选凸优化理论与应用第7章 无约束优化,精选,无约束优化问题,问题描述：,无约束问题求解的两种方法：,迭代逼近：,求解梯度方程：,为凸函数，且二次可微。,精选无约束优化问题问题描述：无约束问题求解的两种方法：迭代逼,精选,例,梯度方程,二次优化：,精选例梯度方程二次优化：,精选,迭代起始点,满足条件2的几种函数：,起始点 满足：,函数 任意下水平集都是闭集；,函数的定义域为,当 时，,精选迭代起始点满足条件2的几种函数：起始点 满,精选,强凸性,定义：函数 在 上具有强凸性，若 满足,若函数 具有强凸性，则有,为最优值，则,精选强凸性定义：函数 在 上具有强凸,精选,强凸性,则有,为最优值，则,若函数 在 上具有强凸性，则可以证明存在 ，满足,精选强凸性则有 为最优值，则若函数,精选,强凸性,对于 ，矩阵 的特征值从大到小依次为 。则有：,定义：矩阵 的条件数为最大特征值与最小特征值之比，即 。,条件数的上界：,精选强凸性对于 ，矩阵,精选,下降法,下降法的基本原理：,迭代 ，满足,为下降方向，为步长因子,。,对于凸函数 ，当 满足 时，存在某个 ，使得 。,精选下降法下降法的基本原理：迭代,精选,下降法,下降法的一般步骤：,给出初始点 ；,循环迭代,计算下降方向 ；,搜索步长因子 ；,迭代：,精选下降法下降法的一般步骤：给出初始点,精选,步长因子搜索,精确一维搜索：,回溯一维搜索：给定参数,循环迭代,初始化：令 ；,若 ，则终止退出；,否则令,精选步长因子搜索精确一维搜索：回溯一维搜索：给定参数循环迭代,精选,步长因子搜索,精选步长因子搜索,精选,梯度下降法,算法简单，但收敛速度较慢。,下降方向：,终止条件：,收敛性：,其中 。,精选梯度下降法算法简单，但收敛速度较慢。下降方向：终止条件：,精选,收敛性分析,则有：,设函数 具有强凸性，则存在 和 ，满足：,若 采用精确一维搜索，则 ，收敛速度因子：,若 采用回溯一维搜索，收敛速度因子：,条件数越大，收敛速度越小。,精选收敛性分析则有：设函数 具有强凸性，则存,精选,例,当 时，算法收敛速度很慢。,初始解为 ，采用精确一维搜索；,迭代：,精选例当 时，算法,精选,例,步长因子采用回溯一维搜索。,精选例步长因子采用回溯一维搜索。,精选,最速下降法,归一化最速下降方向：,非归一化最速下降方向,欧式范数：,二次范数 ：,范数：,精选最速下降法归一化最速下降方向：非归一化最速下降方向欧式范,精选,最速下降法,精选最速下降法,精选,收敛性分析,范数界：,收敛速度因子：,精选收敛性分析范数界：收敛速度因子：,精选,牛顿法,设函数 二阶可微，则在 附近，的泰勒展式为：,泰勒展开可作为 在 附近的近似；,下降方向：,为二次范数 上的最速下降方向。,精选牛顿法设函数 二阶可微，则在 附近，,精选,牛顿法,精选牛顿法,精选,牛顿减量,令,为 在 处的牛顿减量。,牛顿减量的性质1：,性质2：,牛顿减量可作为迭代求解的误差估计。,性质3：牛顿减量具有仿射不变性。,精选牛顿减量令 为 在 处的牛,精选,牛顿方法,初始化：给定初始解 以及,LOOP：,计算：,若 则终止退出；,一维线性搜索：计算步长因子 ；,迭代：,精选牛顿方法初始化：给定初始解,精选,收敛性分析,定理：假设 二阶连续可微，具有强凸性，即存在 ，满足：,则存在 ，,且海森矩阵满足,Lipschitz,条件，即存在 ，满足：,若 ，则 ；,若 ，则 ，且,精选收敛性分析定理：假设 二阶连续可微，具有,精选,收敛性分析,定理：假设 二阶连续可微，具有强凸性，即存在 ，满足：,则存在 ，对于 ，有,且海森矩阵满足,Lipschitz,条件，即存在 ，满足：,精选收敛性分析定理：假设 二阶连续可微，具有,精选,例,精选例,精选,凸优化理论与应用,第8章,等式约束优化,精选凸优化理论与应用第8章 等式约束优化,精选,等式约束优化问题,问题描述：,为凸函数，且二次连续可微，且,假设最优值 存在，则 为最优解当且仅当存在 ，满足（,KKT,条件）：,精选等式约束优化问题问题描述：为凸函数，且二,精选,例,KKT,系统：,二次优化：,KKT,系统可解，则二次优化问题存在最优解。,系数矩阵称为,KKT,矩阵。,KKT,矩阵非奇异当且仅当：,精选例KKT系统：二次优化：KKT系统可解，则二次优化问题,精选,消去等式约束,方程组 的解集：,为方程组的一个特解，为 的零空间范围。,无约束优化形式：,若 为最优解，则有,精选消去等式约束方程组 的解集：,精选,对偶问题,对偶形式：,精选对偶问题对偶形式：,精选,牛顿法,牛顿减量,为等式约束优化的可行解，则在 附近原问题的二次近似为：,设 和 分别为该问题和对偶问题的最优解，则满足：,精选牛顿法牛顿减量 为等式约束优化的可行解，则在,精选,性质2：牛顿减量具有仿射不变性。,牛顿减量,牛顿减量,牛顿减量的性质：,精选性质2：牛顿减量具有仿射不变性。牛顿减量牛顿减量牛顿减量,精选,可行下降方向,可行下降方向：设 满足方程组 。若 满足方程组 ，则 。称为可行方向。若对于较小的 ，有 ，则 为可行下降方向。,精选可行下降方向可行下降方向：设 满足方程组,精选,等式约束的牛顿方法,LOOP：,计算 及 ；,若 则终止退出；,一维线性搜索：计算步长因子 ；,迭代：,初始化：给定初始解 满足 ，以及,精选等式约束的牛顿方法LOOP：计算 及,精选,消去等式约束的牛顿方法,转换为等式约束下的牛顿方法：,初始值 ，第 次迭代值 ；,初始值：,迭代值：,精选消去等式约束的牛顿方法转换为等式约束下的牛顿方法：初始值,精选,非可行解为初始点的牛顿法,函数 二阶连续可微，因此有,为等式约束优化的非可行解，则增量 应尽可能使 满足,KKT,条件，即：,设 和 为,KKT,条件的解，即有：,精选非可行解为初始点的牛顿法函数 二阶连续可,精选,非可行解为初始点的牛顿法,则,KKT,条件可表示为：,令,设 为不满足,KKT,条件，则其迭代量需满足：,即,精选非可行解为初始点的牛顿法则KKT条件可表示为：令设,精选,当 且 时，终止迭代。,非可行解为初始点的牛顿法,LOOP：,计算 和 ；,回溯一维线性搜索：,迭代：,初始化：给定初始解 及 ，以及,令 ；,While,精选当 且,精选,其中 ，且满足 。,KKT系统的求解,1.,分解；,2.若 非奇异，则可消元：,3.若 奇异，则,KKT,系统可改写为：,KKT,系统：,精选其中 ，且满足,精选,凸优化理论与应用,第9章,内点法,精选凸优化理论与应用第9章 内点法,精选,则优化问题具有强对偶性，其对偶问题亦可解。,假设存在 ，满足严格不等式条件,不等式约束优化问题,问题描述：,为凸函数，且二次连续可微，且,假设最优值 存在；,精选则优化问题具有强对偶性，其对偶问题亦可解。假设存在,精选,不具备良好的连续可微性，考虑用对数阀函数来近似替代。,不等式约束的消去,示性函数消去不等式约束：,精选 不具备良好的连续可微性，考虑用对数阀,精选,令,对数阀函数,对于 ，是 的光滑逼近。且当 时，有,带示性函数的优化问题可近似为：,精选令对数阀函数对于 ，,精选,对数阀函数二阶连续可微，导数为：,对数阀函数,对数阀函数 是凸函数,精选对数阀函数二阶连续可微，导数为：对数阀函数对数阀函数,精选,中心线,对数阀近似问题的等价问题：,最优解为 ，则最优解集 称为优化问题的中心线。,精选中心线对数阀近似问题的等价问题：最优解为,精选,中心线的对偶点,设 ，则存在 满足,KKT,条件：,为对偶问题的可行解。,令,则 是拉格朗日函数 的最小值解。,精选中心线的对偶点设 ，则存在,精选,中心线的对偶点,设 为原始问题的最优值，则有：,因此，当 时，有 。为原始问题的 次优解。,精选中心线的对偶点设 为原始问题的最优值，则有：因此,精选,更新 ：,阀方法,初始化：给定严格可行解 ，及,LOOP：,中心步骤：以 为初始点求解优化问题 ，,迭代：,终止条件：若 ，则终止退出。,精选更新 ：阀方法初始化：给定严格可行解 ，,精选,收敛性分析,外层循环迭代次数：,中心步骤实质为一个无约束或等式约束优化问题，其收敛性分析与相应优化问题的收敛性分析结果一致。,精选收敛性分析外层循环迭代次数：中心步骤实质为一个无约束或等,精选,例：,LP,问题：,初始值：,精选例：LP问题：初始值：,精选,当 时，原始问题不可解；,当 时，无法准确确定。,第一阶段方法,对于不等式约束的优化问题，如何寻找严格可行解或验证不可解？,求解优化问题：,该问题最优解存在，假设最优值为,当 时，存在严格可行解；,精选当 时，原始问题不可解；当,精选,第一阶段方法,优化目标为逐项之和：,对于固定的 ，,精选第一阶段方法优化目标为逐项之和：对于固定的 ，,精选,寻找严格可行解的方法,牛顿法求解优化问题：,迭代终止条件：当前解 ，即终止迭代，严格可行解为 。,精选寻找严格可行解的方法牛顿法求解优化问题：迭代终止条件：当,精选,凸优化理论与应用,复习,精选凸优化理论与应用复习,精选,凸集,凸集与凸包的概念；,几种常见的凸集,多面体、单纯形、范数球、凸锥、真锥、范数锥、半正定锥等；,保持凸集的运算,集合交运算、仿射变换、透视函数、线性分式函数,广义不等式的概念,支撑超平面、分割超平面的概念,精选凸集凸集与凸包的概念；,精选,凸函数,凸函数的概念及判定；,常见凸函数；,Jessen,不等式；,保持函数凸性的算子；,共轭函数的概念、常见函数的共轭函数；,向量凸函数（广义不等式下的凸性）,精选凸函数凸函数的概念及判定；,精选,优化问题,优化问题的基本描述、等价形式；,凸优化问题的基本描述、等价形式；,常见凸优化问题。,精选优化问题优化问题的基本描述、等价形式；,精选,对偶问题,优化问题的拉格朗日函数及对偶函数的概念和性质；,一些常见问题的对偶函数；,对偶函数与共轭函数的关系；,对偶问题的描述；,强对偶性的概念及,Slater,条件；,KKT,条件。,精选对偶问题优化问题的拉格朗日函数及对偶函数的概念和性质；,精选,常见应用问题,逼近问题的几种基本描述；,统计估计问题的基本描述。,精选常见应用问题逼近问题的几种基本描述；,精选,常用算法,无约束问题常用算法：,下降法,最速下降,牛顿法,等式约束问题的常用算法,等式约束条件的消去,牛顿法,内点法,精选常用算法无约束问题常用算法：,