凸优化理论与应用课件

信息与通信工程学院庄伯金bjzhuang@1凸优化理论与应用庄伯金Bjzhuang@信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@2优化理论概述什么是优化问题？ObjectivefunctionConstraintfunctions信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@3几类经典的优化问题线性规划问题最小二乘问题凸优化问题凸优化问题理论上有有效的方法进行求解！信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@4本课程的主要内容理论部分凸集和凸函数凸优化问题对偶问题应用部分逼近与拟合统计估计几何问题算法部分非约束优化方法等式约束优化方法内点法信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@5熟悉了解凸优化理论的基本原理和基本方法；掌握实际问题转化为凸优化问题的基本方法；掌握最优化问题的经典算法。课程要求信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@6参考书目StephenBoydandLievenVandenberghe,“ConvexOptimization”,CambridgeUniversityPress.袁亚湘、孙文瑜，“最优化理论与方法”，科学出版社，1999。

信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@7凸优化理论与应用第一章凸集信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@8仿射集(Affinesets)直线的表示：线段的表示：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@9仿射集(Affinesets)仿射集的定义：过集合C内任意两点的直线均在集合C内，则称集合C为仿射集。仿射集的例：直线、平面、超平面信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@10仿射集仿射包：包含集合C的最小的仿射集。仿射维数：仿射包的维数。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@11仿射集内点（interior）：相对内点（relativeinterior）：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@12凸集(ConvexSets)凸集的定义：集合C内任意两点间的线段均在集合C内，则称集合C为凸集。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@13凸集凸包的定义：包含集合C的最小的凸集。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@14锥(Cones)锥的定义：凸锥的定义：集合C既是凸集又是锥。锥包的定义：集合C内点的所有锥组合。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@15超平面和半空间超平面(hyperplane)：半空间(Halfspace)：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@16欧氏球和椭球欧氏球(euclideanball):椭球(ellipsoid):信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@17范数球和范数锥范数(norm)：范数球(normball)：范数锥(normcone)：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@18多面体(Polyhedra)多面体：单纯形(simplex)：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@19半正定锥(Positivesemidefinitecone)n阶对称矩阵集：n阶半正定矩阵集：n阶正定矩阵集：n阶半正定矩阵集为凸锥！信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@20保持凸性的运算集合交运算仿射变换透视/投射函数(perspectivefunction)信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@21保持凸性的运算线性分式函数(linear-fractionalfunction)信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@22真锥(propercone)真锥的定义：锥满足如下条件K具有内点K内不含直线信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@23广义不等式真锥下的偏序关系：例：逐项不等式矩阵不等式广义不等式严格广义不等式信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@24广义不等式的性质信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@25严格广义不等式的性质信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@26最值和极值最小元的定义：设，对，都有成立，则称为的最小元。极小元的定义：设，对于，若，则成立，则称为的极小元。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@27分割超平面(separatinghyperplane)定理：设和为两不相交凸集，则存在超平面将和分离。即：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@28支撑超平面(supportinghyperplane)定义：设集合，为边界上的点。若存在，满足对任意，都有成立，则称超平面为集合在点处的支撑超平面。定理：凸集边界上任意一点均存在支撑超平面。定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@29对偶锥(dualcone)对偶锥的定义：设为锥，则集合称为对偶锥。对偶锥的性质：真锥的对偶锥仍然是真锥！信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@30对偶广义不等式广义不等式与对偶等价性质最小元的对偶特性：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@31对偶广义不等式极小元的对偶特性反过来不一定成立！信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@32作业P602.8P602.10P602.14P622.16P622.18P642.30P642.31P642.33信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@33凸优化理论与应用第二章凸函数信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@34凸函数的定义1.定义域为凸集；2.，有凸函数的定义：函数，满足凸函数的扩展定义：若为凸函数，则可定义其扩展函数为凸函数的扩展函数也是凸函数！信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@35凸函数的一阶微分条件若函数的定义域为开集，且函数一阶可微，则函数为凸函数当且仅当为凸集，且对信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@36凸函数的二阶微分条件若函数的定义域为开集，且函数二阶可微，则函数为凸函数当且仅当为凸集，且对，其Hessian矩阵信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@37凸函数的例幂函数负对数函数负熵函数范数函数指数函数信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@38凸函数的例信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@39下水平集(sublevelset)定理：凸函数的任一下水平集均为凸集。任一下水平集均为凸集的函数不一定为凸函数。 称为的下水平集。定义：集合信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@40函数上半图(epigraph)定理：函数为凸函数当且仅当的上半图为凸集。 称为函数的上半图。定义：集合信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@41Jensen不等式为凸函数，则有：Jensen不等式的另外形式：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@42保持函数凸性的算子凸函数的逐点最大值凸函数与仿射变换的复合凸函数的非负加权和信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@43保持函数凸性的算子复合运算最小值算子凸函数的透视算子信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@44共轭函数(conjugatefunction)定义：设函数，其共轭函数，定义为共轭函数的例共轭函数具有凸性！信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@45共轭函数的性质Fenchel’sinequality性质：若为凸函数，且的上半图是闭集，则有性质：设为凸函数，且可微，对于，若 则信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@46准凸函数(quasiconvexfunction)准凸函数的例定义：设函数，若函数的定义域和任意下水平集

则称函数为准凸函数。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@47准凸函数的判定定理定理：函数为准凸函数，当且仅当为凸集，且对，有定理：若函数一阶可微，则为准凸函数，当且仅当为凸集，且对，有 ，有定理：若函数二阶可微，且满足对 则函数准凸函数。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@48最小值函数非负权值函数的最大值函数保持准凸性的算子复合函数信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@49准凸函数的凸函数族表示若为准凸函数，根据的任意下水平集，我们可以构造一个凸函数族，使得性质：若为准凸函数的凸函数族表示，对每一个，若，则有信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@50对数凸函数 为凸集 为凸函数。定义：函数称为对数凸函数，若函数满足：定理：函数的定义域为凸集，且，则为对数凸函数，当且仅当对有对数凸函数的例信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@51对数凸函数和凹函数的性质性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。定理：函数二阶可微，则为对数凸函数当且仅当性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。推论：函数对每一个在上对数凸，则函数也是对数凸函数。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@52对数凸函数和凹函数的性质定理：函数为对数凹函数，则函数是对数凹函数。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@53广义不等式下的凸性广义单调性的定义：设为真锥，函数称为单调增，若函数满足：广义凸函数的定义：设为真锥，函数称为凸，若函数满足对 均有定理(对偶等价)：函数为凸函数，当且仅当对所有，为凸函数。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@54作业(1)P1163.16P1163.21信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@55作业(2)P1213.41P1223.49(1)(2)信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@56凸优化理论与应用第三章凸优化信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@57优化问题的基本形式优化问题的基本描述：优化变量不等式约束等式约束无约束优化信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@58优化问题的基本形式最优化值最优化解优化问题的域可行点(解)(feasible)满足约束条件可行域(可解集)所有可行点的集合信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@59局部最优问题局部最优问题信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@60优化问题的等价形式(1)定理：若则原优化问题与以下优化问题等价信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@61优化问题的等价形式(2)定理：设为一一对应，且则原优化问题与以下优化问题等价信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@62优化问题的等价形式(3)定理：设为严格单调增函数；满足当且仅当；满足当且仅当。则原优化问题与以下优化问题等价信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@63优化问题的等价形式(4)定理：原优化问题与以下优化问题等价称为松弛变量信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@64优化问题的等价形式(5)定理：设满足等式成立，当且仅当。则原优化问题与以下优化问题等价信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@65可分离变量优化问题性质： 其中 可以分离变量定理：优化问题信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@66优化问题的上半图形式信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@67凸优化问题的基本形式凸优化问题的基本描述：为仿射函数为凸函数若为准凸函数，则优化问题称为准凸优化问题。性质：凸优化问题的可行域是凸集。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@68凸优化问题的例例： 等价于凸优化问题信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@69凸优化问题的局部最优解定理：凸优化问题的局部最优解均是全局最优解。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@70凸优化问题最优解的微分条件定理：设为凸优化问题的可行域，可微。则为最优解当且仅当成立。定理：非约束凸优化问题中，若可微。则为最优解当且仅当成立。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@71凸优化问题的等价形式 则为最优解当且仅当，且存在向量满足定理：设凸优化问题仅有等式约束信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@72凸优化问题的等价形式 则为最优解当且仅当，且定理：设凸优化问题信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@73凸优化问题的等价形式 等价于

定理：设凸优化问题 其中

信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@74凸优化问题的等价形式 等价于

定理：设凸优化问题信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@75准凸优化问题 为准凸函数，为凸函数。准凸优化问题的基本描述注：准凸优化问题的局部最优解不一定是全局最优解。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@76准凸优化问题的上半图形式设为准凸函数的凸函数族表示，即则准凸优化问题的可行解问题为设为准凸优化问题的最优解，若上述问题可解，则。否则。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@77准凸优化问题二分法求解给定一个足够小的和足够大的，使得区间能包含最优解。给定LOOP：令求解可行解问题；若可解，则令，否则令若，则结束，否则gotoLOOP。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@78线性规划(linearprogram,LP)LP问题的一般描述信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@79LP问题的几种类型标准LP问题不等式形式LP问题信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@80标准LP问题的转换信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@81LP问题的例ChebyshevcenterofapolyhedronPiecewise-linearminimizationLinear-fractionalprogramming信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@82Chebyshevcenterofapolyhedron多面体Chebyshevcenter：到多面体边界距离最大的内点（最深的点）问题描述LP形式信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@83Piecewise-linearminimization问题描述上半图形式LP形式信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@84Linear-fractionalprogramming问题描述LP形式信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@85二次规划(quadraticprogram,QP)QP问题的基本描述信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@86二次约束二次规划quadraticallyconstrainedquadraticprogram(QCQP)信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@87QP问题的例Least-squaresandregressionDistancebetweenpolyhedra信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@88Least-squaresandregression问题描述信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@89Distancebetweenpolyhedra问题描述QP形式信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@90Second-orderconeprogram,SOCPSOCP问题的基本描述二次锥约束条件信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@91SOCP问题的例－Robustlinearprogramming问题描述 其中不是完全确定的常数。例：为确定的常数，为变量，其范围满足 SOCP形式信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@92几何规划(Geometricprogramming)单项式与多项式几何规划的基本描述信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@93几何规划的凸形式转换令几何规划的凸形式信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@94广义不等式约束广义不等式约束的优化问题SOCP的描述信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@95凸优化理论与应用第四章对偶问题信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@96优化问题的拉格朗日函数设优化问题：拉格朗日(Lagrangian)函数：对固定的，拉格朗日函数为关于和的仿射函数。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@97拉格朗日对偶函数拉格朗日对偶函数(lagrangedualfunction)：若拉格朗日函数没有下界，则令拉格朗日对偶函数为凹函数。对和，若原最优化问题有最优值，则信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@98对偶函数的例Least-squaressolutionoflinearequationsStandardformLPTwo-waypartitioningproblem信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@99Least-squaressolutionoflinearequations原问题：拉格朗日函数：拉格朗日对偶函数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@100StandardformLP原问题：拉格朗日函数：拉格朗日对偶函数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@101Two-waypartitioningproblem原问题：拉格朗日函数：拉格朗日对偶函数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@102对偶函数与共轭函数共轭函数共轭函数与对偶函数存在密切联系具有线性不等式约束和线性等式约束的优化问题：对偶函数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@103Equalityconstrainednormminimization问题描述：共轭函数：对偶函数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@104Entropymaximization原始问题：共轭函数：对偶函数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@105Minimumvolumecoveringellipsoid原始问题：对偶函数：共轭函数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@106拉格朗日对偶问题拉格朗日对偶问题的描述：对偶可行域最优值最优解信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@107LP问题的对偶问题标准LP问题对偶函数对偶问题等价描述信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@108弱对偶性定理（弱对偶性）：设原始问题的最优值为，对偶问题的最优值为，则成立。optimaldualitygap可以利用对偶问题找到原始问题最优解的下界。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@109强对偶性强对偶性并不是总是成立的。定义（强对偶性）：设原始问题的最优值为，对偶问题的最优值为。若成立，则称原始问题和对偶问题之间具有强对偶性。凸优化问题通常（但并不总是）具有强对偶性。Slater定理：若凸优化问题存在严格可行解，即存在，满足 则优化问题具有强对偶性。该条件称为Slater条件。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@110强对偶性 存在，满足弱化的Slater条件：若不等式约束条件的前个为线性不等式约束条件，则Slater条件可以弱化为：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@111Least-squaressolutionoflinearequations原问题：对偶问题：具有强对偶性信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@112LagrangedualofQCQPQCQP：拉格朗日函数：对偶函数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@113LagrangedualofQCQP对偶问题：Slater条件：存在，满足信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@114Entropymaximization原始问题：对偶函数：对偶问题：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@115Entropymaximization弱化的Slater条件：存在，满足信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@116Minimumvolumecoveringellipsoid原始问题：对偶函数：对偶问题：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@117Minimumvolumecoveringellipsoid弱化的Slater条件总成立，因此该优化问题具有强对偶性。弱化的Slater条件：存在，满足信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@118对偶可行解的不等式对于一优化问题，若为一可行解，为对偶问题可行解，则有如下不等式： 为次优解，其中不等式可以用于对次优解的精度估计信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@119互补松弛条件 所以设为原始优化问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则 即信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@120KKT优化条件设优化问题中，函数可微。设为原始优化问题的最优解，为对偶问题的最优解，且两者具有强对偶性，则满足如下条件：KKT条件为必要条件！信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@121凸优化问题的KKT条件 可微。设满足KKT条件，则为原始问题的最优解，而为对偶问题的最优解，且两者具有强对偶性。设原始问题为凸优化问题中，函数信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@122例原始凸优化问题

KKT条件信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@123例 其中

解得信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@124凸优化问题的对偶求解 存在唯一解。若为原始问题的可行解，则即为原始问题的最优解；若不是原始问题的可行解，则原始问题不存在最优解。设原始优化问题与对偶问题具有强对偶性，且为对偶问题的最优解。存在唯一的最小解，即信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@125扰动问题扰动问题：当时即为原始问题。若为正，则第个不等式约束被放宽；若为负，则第个不等式约束被收紧。记为扰动问题的最优解。若扰动问题无最优解，则记信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@126灵敏度分析设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为，则有若在处可微，则信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@127定义（弱选择性）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。选择定理对偶不等式组设原始问题的约束条件：对偶问题原始问题的约束条件与对偶不等式组具有弱选择性。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@128选择定理对偶不等式组设原始问题的严格不等式约束条件：原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@129定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。选择定理对偶不等式组设原始问题为凸优化问题，其严格不等式约束条件为：若存在，满足，则上述两不等式约束系统具有强选择性。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@130选择定理对偶不等式组设原始问题为凸优化问题，其不等式约束条件为： 则原始问题的不等式约束条件与对偶不等式组具有强选择性。若存在，满足，且下述优化问题存在最优解信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@131罚函数的例范数：死区线性罚函数：对数门限罚函数信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@132鲁棒的罚函数若大到一定程度时，罚函数为的线性函数，则称该罚函数为鲁棒的罚函数。Huber罚函数信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@133最小范数问题问题描述： 其中为方程组的解。可以消去等式约束将其转换为范数逼近问题：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@134最小范数问题最小平方范数问题：范数，最优解满足：最小罚问题：绝对值和最小问题：范数，原问题可转换为LP问题：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@135正则逼近二元矢量优化问题描述：正则化问题： 最优解描述了两分量的一条折中曲线。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@136正则逼近Tikhonov正则化问题： 为二次优化问题： 最优解的形式：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@137正则逼近Tikhonov光滑正则化问题： 为二阶差分算子：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@138信号复原已知加噪信号： 信号复原问题的描述： 函数为正则函数或光滑函数。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@139信号复原信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@140信号复原信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@141信号复原信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@142鲁棒逼近问题描述：随机鲁棒逼近：为随机变量，逼近问题转换为最小化期望例： 随机鲁棒逼近为： 转换为：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@143随机鲁棒逼近为随机变量： 最小平方随机鲁棒逼近为： 转换为： 其中信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@144最坏情况鲁棒逼近考虑，最坏情况鲁棒逼近为：例： 随机鲁棒逼近为： 转换为：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@145凸优化理论与应用第6章统计估计信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@146概率分布的参数估计随机变量的概率密度为，其中为概率分布的参数，且参数未知。参数估计的目标就是通过一些已知样本估计获得参数的最优近似值。问题描述为样本观测值；为对数似然函数；若似然函数为凹函数，则优化问题为凸优化问题。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@147具有独立同分布噪声的线性测量线性测量模型：为观测值或测量值；为未知参数向量；独立同分布噪声，其概率密度为。似然函数为最大似然估计问题为：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@148例高斯白噪声 对数似然函数：区间上均匀分布的噪声： 对数似然函数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@149逻辑回归随机变量的概率分布为：为参数；为可观测的解释变量；为观察值。 对数似然函数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@150假定测验随机变量，有种可能（假定）的分布；假定：的概率分布为假定测验的目标：由观察值猜测随机变量最有可能服从哪种假定的分布。当时，称为二元假定测验。随机检测子：非负元素矩阵信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@151假定测验为当实际服从第1种假定分布而猜测为第2种假定分布的概率；为当实际服从第2种假定分布而猜测为第1种假定分布的概率；多目标优化形式：检测概率矩阵信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@152假定测验最小最大值形式尺度优化形式：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@153例

在两种假设下的概率分布为：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@154例信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@155实验设计线性测量问题最大似然估计值：独立同分布高斯白噪声，服从分布。估计误差均值为0，方差为 信赖椭圆为信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@156实验设计实验设计的目标：寻找，使得误差的方差矩阵最小。向量优化形式：为整数问题，求解较困难。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@157实验设计当时，令近似为一连续实数，原问题可松弛转换为连续实数优化：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@158凸优化理论与应用第7章无约束优化信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@159无约束优化问题问题描述：无约束问题求解的两种方法：迭代逼近：求解梯度方程：为凸函数，且二次可微。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@160例 梯度方程二次优化：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@161迭代起始点满足条件2的几种函数：起始点满足：函数任意下水平集都是闭集；函数的定义域为当时，信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@162强凸性定义：函数在上具有强凸性，若满足若函数具有强凸性，则有为最优值，则信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@163强凸性 则有为最优值，则若函数在上具有强凸性，则可以证明存在，满足信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@164强凸性对于，矩阵的特征值从大到小依次为。则有：

定义：矩阵的条件数为最大特征值与最小特征值之比，即。条件数的上界：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@165下降法下降法的基本原理： 迭代，满足 为下降方向，为步长因子。对于凸函数，当满足时，存在某个，使得。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@166下降法下降法的一般步骤：给出初始点；循环迭代计算下降方向；搜索步长因子；迭代：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@167步长因子搜索精确一维搜索：回溯一维搜索：给定参数循环迭代初始化：令；若，则终止退出；否则令信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@168步长因子搜索信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@169梯度下降法算法简单，但收敛速度较慢。下降方向：终止条件：收敛性： 其中。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@170收敛性分析 则有：设函数具有强凸性，则存在和，满足：若采用精确一维搜索，则，收敛速度因子：若采用回溯一维搜索，收敛速度因子：条件数越大，收敛速度越小。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@171例当时，算法收敛速度很慢。初始解为，采用精确一维搜索；迭代：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@172例步长因子采用回溯一维搜索。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@173最速下降法归一化最速下降方向：非归一化最速下降方向欧式范数：二次范数：范数：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@174最速下降法信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@175收敛性分析范数界：收敛速度因子：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@176牛顿法设函数二阶可微，则在附近，的泰勒展式为：泰勒展开可作为在附近的近似；下降方向：为二次范数上的最速下降方向。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@177牛顿法信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@178牛顿减量令为在处的牛顿减量。牛顿减量的性质1：性质2： 牛顿减量可作为迭代求解的误差估计。性质3：牛顿减量具有仿射不变性。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@179牛顿方法初始化：给定初始解以及LOOP：计算：若则终止退出；一维线性搜索：计算步长因子；迭代：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@180收敛性分析定理：假设二阶连续可微，具有强凸性，即存在，满足： 则存在， 且海森矩阵满足Lipschitz条件，即存在，满足： 若，则； 若，则，且信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@181收敛性分析定理：假设二阶连续可微，具有强凸性，即存在，满足： 则存在，对于，有 且海森矩阵满足Lipschitz条件，即存在，满足：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@182例信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@183凸优化理论与应用第8章等式约束优化信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@184等式约束优化问题问题描述：为凸函数，且二次连续可微，且假设最优值存在，则为最优解当且仅当存在，满足（KKT条件）：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@185例

KKT系统：二次优化：KKT系统可解，则二次优化问题存在最优解。系数矩阵称为KKT矩阵。KKT矩阵非奇异当且仅当：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@186消去等式约束方程组的解集：为方程组的一个特解，为的零空间范围。无约束优化形式：若为最优解，则有信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@187对偶问题对偶形式：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@188牛顿法牛顿减量为等式约束优化的可行解，则在附近原问题的二次近似为：设和分别为该问题和对偶问题的最优解，则满足：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@189性质2：牛顿减量具有仿射不变性。牛顿减量牛顿减量牛顿减量的性质：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@190可行下降方向可行下降方向：设满足方程组。若满足方程组，则。称为可行方向。若对于较小的，有，则为可行下降方向。信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@191等式约束的牛顿方法LOOP：计算及；若则终止退出；一维线性搜索：计算步长因子；迭代：初始化：给定初始解满足，以及信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@192消去等式约束的牛顿方法转换为等式约束下的牛顿方法：初始值，第次迭代值；初始值：迭代值：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@193非可行解为初始点的牛顿法函数二阶连续可微，因此有为等式约束优化的非可行解，则增量应尽可能使满足KKT条件，即：设和为KKT条件的解，即有：信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@194非可行解为初始点的牛顿法则KKT条件可表示为：令设为不满足KKT条件，则其迭代量需满足： 即信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@195当且时，终止迭代。非可行解为初始点的牛顿法LOOP：计算和；回溯一维线性搜索：迭代：初始化：给定初始解及，以及令；While信息与通信工程学院庄伯金bjzhuang@bupt.ed信息与通信工程学院庄伯金bjzhuang@196 其中，且满足。KKT系