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

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

精选参考书目StephenBoydandLieven精选凸优化理论与应用第一章凸集精选凸优化理论与应用第一章精选仿射集(Affinesets)直线的表示：线段的表示：精选仿射集(Affinesets)直线的表示：线段的表示：精选仿射集(Affinesets)仿射集的定义：过集合C内任意两点的直线均在集合C内，则称集合C为仿射集。仿射集的例：直线、平面、超平面精选仿射集(Affinesets)仿射集的定义：过集合C内精选仿射集仿射包：包含集合C的最小的仿射集。仿射维数：仿射包的维数。精选仿射集仿射包：包含集合C的最小的仿射集。仿射维数：仿射包精选仿射集内点（interior）：相对内点（relativeinterior）：精选仿射集内点（interior）：相对内点（relativ精选凸集(ConvexSets)凸集的定义：集合C内任意两点间的线段均在集合C内，则称集合C为凸集。精选凸集(ConvexSets)凸集的定义：集合C内任意两精选凸集凸包的定义：包含集合C的最小的凸集。精选凸集凸包的定义：包含集合C的最小的凸集。精选锥(Cones)锥的定义：凸锥的定义：集合C既是凸集又是锥。锥包的定义：集合C内点的所有锥组合。精选锥(Cones)锥的定义：凸锥的定义：集合C既是凸集又是精选超平面和半空间超平面(hyperplane)：半空间(Halfspace)：精选超平面和半空间超平面(hyperplane)：半空间(精选欧氏球和椭球欧氏球(euclideanball):椭球(ellipsoid):精选欧氏球和椭球欧氏球(euclideanball):椭球精选范数球和范数锥范数(norm)：范数球(normball)：范数锥(normcone)：精选范数球和范数锥范数(norm)：范数球(normbal精选多面体(Polyhedra)多面体：单纯形(simplex)：精选多面体(Polyhedra)多面体：单纯形(simple精选半正定锥(Positivesemidefinitecone)n阶对称矩阵集：n阶半正定矩阵集：n阶正定矩阵集：n阶半正定矩阵集为凸锥！精选半正定锥(Positivesemidefinitec精选保持凸性的运算集合交运算仿射变换透视/投射函数(perspectivefunction)精选保持凸性的运算集合交运算精选保持凸性的运算线性分式函数(linear-fractionalfunction)精选保持凸性的运算线性分式函数(linear-fractio精选真锥(propercone)真锥的定义：锥满足如下条件K具有内点K内不含直线精选真锥(propercone)真锥的定义：锥精选广义不等式真锥下的偏序关系：例：逐项不等式矩阵不等式广义不等式严格广义不等式精选广义不等式真锥下的偏序关系：例：广义不等式严格广精选广义不等式的性质精选广义不等式的性质精选严格广义不等式的性质精选严格广义不等式的性质精选最值和极值最小元的定义：设，对，都有成立，则称为的最小元。极小元的定义：设，对于，若，则成立，则称为的极小元。精选最值和极值最小元的定义：设，对精选分割超平面(separatinghyperplane)定理：设和为两不相交凸集，则存在超平面将和分离。即：精选分割超平面(separatinghyperplane)精选支撑超平面(supportinghyperplane)定义：设集合，为边界上的点。若存在，满足对任意，都有成立，则称超平面为集合在点处的支撑超平面。定理：凸集边界上任意一点均存在支撑超平面。定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。精选支撑超平面(supportinghyperplane)精选对偶锥(dualcone)对偶锥的定义：设为锥，则集合称为对偶锥。对偶锥的性质：真锥的对偶锥仍然是真锥！精选对偶锥(dualcone)对偶锥的定义：设为锥，精选对偶广义不等式广义不等式与对偶等价性质最小元的对偶特性：精选对偶广义不等式广义不等式与对偶等价性质最小元的对偶特性：精选对偶广义不等式极小元的对偶特性反过来不一定成立！精选对偶广义不等式极小元的对偶特性反过来不一定成立！精选作业P602.8P602.10P602.14P622.16P622.18P642.30P642.31P642.33精选作业P602.8精选凸优化理论与应用第二章凸函数精选凸优化理论与应用第二章凸函数精选凸函数的定义1.定义域为凸集；2.，有凸函数的定义：函数，满足凸函数的扩展定义：若为凸函数，则可定义其扩展函数为凸函数的扩展函数也是凸函数！精选凸函数的定义1.定义域为凸集；2.精选凸函数的一阶微分条件若函数的定义域为开集，且函数一阶可微，则函数为凸函数当且仅当为凸集，且对精选凸函数的一阶微分条件若函数的定义域精选凸函数的二阶微分条件若函数的定义域为开集，且函数二阶可微，则函数为凸函数当且仅当为凸集，且对，其Hessian矩阵精选凸函数的二阶微分条件若函数的定义域精选凸函数的例幂函数负对数函数负熵函数范数函数指数函数精选凸函数的例幂函数负对数函数负熵函数范数函数指数函数精选凸函数的例精选凸函数的例精选下水平集(sublevelset)定理：凸函数的任一下水平集均为凸集。任一下水平集均为凸集的函数不一定为凸函数。 称为的下水平集。定义：集合精选下水平集(sublevelset)定理：凸函数的任一下精选函数上半图(epigraph)定理：函数为凸函数当且仅当的上半图为凸集。 称为函数的上半图。定义：集合精选函数上半图(epigraph)定理：函数为凸函数精选Jensen不等式为凸函数，则有：Jensen不等式的另外形式：精选Jensen不等式为凸函数，则有：Jensen不等精选保持函数凸性的算子凸函数的逐点最大值凸函数与仿射变换的复合凸函数的非负加权和精选保持函数凸性的算子凸函数的逐点最大值凸函数与仿射变换的复精选保持函数凸性的算子复合运算最小值算子凸函数的透视算子精选保持函数凸性的算子复合运算最小值算子凸函数的透视算子精选共轭函数(conjugatefunction)定义：设函数，其共轭函数，定义为共轭函数的例共轭函数具有凸性！精选共轭函数(conjugatefunction)定义：设精选共轭函数的性质Fenchel’sinequality性质：若为凸函数，且的上半图是闭集，则有性质：设为凸函数，且可微，对于，若 则精选共轭函数的性质Fenchel’sinequality性精选准凸函数(quasiconvexfunction)准凸函数的例定义：设函数，若函数的定义域和任意下水平集

则称函数为准凸函数。精选准凸函数(quasiconvexfunction)准凸精选准凸函数的判定定理定理：函数为准凸函数，当且仅当为凸集，且对，有定理：若函数一阶可微，则为准凸函数，当且仅当为凸集，且对，有 ，有定理：若函数二阶可微，且满足对 则函数准凸函数。精选准凸函数的判定定理定理：函数为准凸函数，精选最小值函数非负权值函数的最大值函数保持准凸性的算子复合函数精选最小值函数非负权值函数的最大值函数保持准凸性的算子复合函精选准凸函数的凸函数族表示若为准凸函数，根据的任意下水平集，我们可以构造一个凸函数族，使得性质：若为准凸函数的凸函数族表示，对每一个，若，则有精选准凸函数的凸函数族表示若为准凸函数，根精选对数凸函数 为凸集 为凸函数。定义：函数称为对数凸函数，若函数满足：定理：函数的定义域为凸集，且，则为对数凸函数，当且仅当对有对数凸函数的例精选对数凸函数 为凸集 为凸函数精选对数凸函数和凹函数的性质性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。定理：函数二阶可微，则为对数凸函数当且仅当性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。推论：函数对每一个在上对数凸，则函数也是对数凸函数。精选对数凸函数和凹函数的性质性质：对数凸性与凹性对函数乘积和精选对数凸函数和凹函数的性质定理：函数为对数凹函数，则函数是对数凹函数。精选对数凸函数和凹函数的性质定理：函数精选广义不等式下的凸性广义单调性的定义：设为真锥，函数称为单调增，若函数满足：广义凸函数的定义：设为真锥，函数称为凸，若函数满足对 均有定理(对偶等价)：函数为凸函数，当且仅当对所有，为凸函数。精选广义不等式下的凸性广义单调性的定义：设精选作业(1)P1163.16P1163.21精选作业(1)P1163.16精选作业(2)P1213.41P1223.49(1)(2)精选作业(2)P1213.41精选凸优化理论与应用第三章凸优化精选凸优化理论与应用第三章凸优化精选优化问题的基本形式优化问题的基本描述：优化变量不等式约束等式约束无约束优化精选优化问题的基本形式优化问题的基本描述：优化变量不等式约束精选优化问题的基本形式最优化值最优化解优化问题的域可行点(解)(feasible)满足约束条件可行域(可解集)所有可行点的集合精选优化问题的基本形式最优化值最优化解优化问题的域精选局部最优问题局部最优问题精选局部最优问题局部最优问题精选优化问题的等价形式(1)定理：若则原优化问题与以下优化问题等价精选优化问题的等价形式(1)定理：若则原优化问题与以下精选优化问题的等价形式(2)定理：设为一一对应，且则原优化问题与以下优化问题等价精选优化问题的等价形式(2)定理：设精选优化问题的等价形式(3)定理：设为严格单调增函数；满足当且仅当；满足当且仅当。则原优化问题与以下优化问题等价精选优化问题的等价形式(3)定理：设精选优化问题的等价形式(4)定理：原优化问题与以下优化问题等价称为松弛变量精选优化问题的等价形式(4)定理：原优化问题与以下优化问题等精选优化问题的等价形式(5)定理：设满足等式成立，当且仅当。则原优化问题与以下优化问题等价精选优化问题的等价形式(5)定理：设精选可分离变量优化问题性质： 其中 可以分离变量定理：优化问题精选可分离变量优化问题性质： 其中 可以分离变量定理：优化问精选优化问题的上半图形式精选优化问题的上半图形式精选凸优化问题的基本形式凸优化问题的基本描述：为仿射函数为凸函数若为准凸函数，则优化问题称为准凸优化问题。性质：凸优化问题的可行域是凸集。精选凸优化问题的基本形式凸优化问题的基本描述：精选凸优化问题的例例： 等价于凸优化问题精选凸优化问题的例例： 等价于凸优化问题精选凸优化问题的局部最优解定理：凸优化问题的局部最优解均是全局最优解。精选凸优化问题的局部最优解定理：凸优化问题的局部最优解均是全精选凸优化问题最优解的微分条件定理：设为凸优化问题的可行域，可微。则为最优解当且仅当成立。定理：非约束凸优化问题中，若可微。则为最优解当且仅当成立。精选凸优化问题最优解的微分条件定理：设为凸优化问题的精选凸优化问题的等价形式 则为最优解当且仅当，且存在向量满足定理：设凸优化问题仅有等式约束精选凸优化问题的等价形式 则为最优解当且仅当精选凸优化问题的等价形式 则为最优解当且仅当，且定理：设凸优化问题精选凸优化问题的等价形式 则为最优解当且仅当精选凸优化问题的等价形式 等价于

定理：设凸优化问题 其中

精选凸优化问题的等价形式 等价于定理：设凸优化问精选凸优化问题的等价形式 等价于

定理：设凸优化问题精选凸优化问题的等价形式 等价于定理：设凸优化问精选准凸优化问题 为准凸函数，为凸函数。准凸优化问题的基本描述注：准凸优化问题的局部最优解不一定是全局最优解。精选准凸优化问题 为准凸函数，精选准凸优化问题的上半图形式设为准凸函数的凸函数族表示，即则准凸优化问题的可行解问题为设为准凸优化问题的最优解，若上述问题可解，则。否则。精选准凸优化问题的上半图形式设为准凸函数精选准凸优化问题二分法求解给定一个足够小的和足够大的，使得区间能包含最优解。给定LOOP：令求解可行解问题；若可解，则令，否则令若，则结束，否则gotoLOOP。精选准凸优化问题二分法求解给定一个足够小的和足够大的精选线性规划(linearprogram,LP)LP问题的一般描述精选线性规划(linearprogram,LP)LP问题的精选LP问题的几种类型标准LP问题不等式形式LP问题精选LP问题的几种类型标准LP问题不等式形式LP问题精选标准LP问题的转换精选标准LP问题的转换精选LP问题的例ChebyshevcenterofapolyhedronPiecewise-linearminimizationLinear-fractionalprogramming精选LP问题的例Chebyshevcenterofa精选Chebyshevcenterofapolyhedron多面体Chebyshevcenter：到多面体边界距离最大的内点（最深的点）问题描述LP形式精选Chebyshevcenterofapolyhe精选Piecewise-linearminimization问题描述上半图形式LP形式精选Piecewise-linearminimizatio精选Linear-fractionalprogramming问题描述LP形式精选Linear-fractionalprogrammin精选二次规划(quadraticprogram,QP)QP问题的基本描述精选二次规划(quadraticprogram,QP)QP精选二次约束二次规划quadraticallyconstrainedquadraticprogram(QCQP)精选二次约束二次规划quadraticallyconstr精选QP问题的例Least-squaresandregressionDistancebetweenpolyhedra精选QP问题的例Least-squaresandregr精选Least-squaresandregression问题描述精选Least-squaresandregression精选Distancebetweenpolyhedra问题描述QP形式精选Distancebetweenpolyhedra问题精选Second-orderconeprogram,SOCPSOCP问题的基本描述二次锥约束条件精选Second-orderconeprogram,S精选SOCP问题的例－Robustlinearprogramming问题描述 其中不是完全确定的常数。例：为确定的常数，为变量，其范围满足 SOCP形式精选SOCP问题的例－Robustlinearprogr精选几何规划(Geometricprogramming)单项式与多项式几何规划的基本描述精选几何规划(Geometricprogramming)单精选几何规划的凸形式转换令几何规划的凸形式精选几何规划的凸形式转换令几何规划的凸形式精选广义不等式约束广义不等式约束的优化问题SOCP的描述精选广义不等式约束广义不等式约束的优化问题SOCP的描述精选凸优化理论与应用第四章对偶问题精选凸优化理论与应用第四章对偶问题精选优化问题的拉格朗日函数设优化问题：拉格朗日(Lagrangian)函数：对固定的，拉格朗日函数为关于和的仿射函数。精选优化问题的拉格朗日函数设优化问题：拉格朗日(Lagran精选拉格朗日对偶函数拉格朗日对偶函数(lagrangedualfunction)：若拉格朗日函数没有下界，则令拉格朗日对偶函数为凹函数。对和，若原最优化问题有最优值，则精选拉格朗日对偶函数拉格朗日对偶函数(lagrangedu精选对偶函数的例Least-squaressolutionoflinearequationsStandardformLPTwo-waypartitioningproblem精选对偶函数的例Least-squaressolution精选Least-squaressolutionoflinearequations原问题：拉格朗日函数：拉格朗日对偶函数：精选Least-squaressolutionofli精选StandardformLP原问题：拉格朗日函数：拉格朗日对偶函数：精选StandardformLP原问题：拉格朗日函数：拉精选Two-waypartitioningproblem原问题：拉格朗日函数：拉格朗日对偶函数：精选Two-waypartitioningproblem精选对偶函数与共轭函数共轭函数共轭函数与对偶函数存在密切联系具有线性不等式约束和线性等式约束的优化问题：对偶函数：精选对偶函数与共轭函数共轭函数共轭函数与对偶函数存在密切联系精选Equalityconstrainednormminimization问题描述：共轭函数：对偶函数：精选Equalityconstrainednormmi精选Entropymaximization原始问题：共轭函数：对偶函数：精选Entropymaximization原始问题：共轭函精选Minimumvolumecoveringellipsoid原始问题：对偶函数：共轭函数：精选Minimumvolumecoveringelli精选拉格朗日对偶问题拉格朗日对偶问题的描述：对偶可行域最优值最优解精选拉格朗日对偶问题拉格朗日对偶问题的描述：对偶可行域最优值精选LP问题的对偶问题标准LP问题对偶函数对偶问题等价描述精选LP问题的对偶问题标准LP问题对偶函数对偶问题等价描述精选弱对偶性定理（弱对偶性）：设原始问题的最优值为，对偶问题的最优值为，则成立。optimaldualitygap可以利用对偶问题找到原始问题最优解的下界。精选弱对偶性定理（弱对偶性）：设原始问题的最优值为精选强对偶性强对偶性并不是总是成立的。定义（强对偶性）：设原始问题的最优值为，对偶问题的最优值为。若成立，则称原始问题和对偶问题之间具有强对偶性。凸优化问题通常（但并不总是）具有强对偶性。Slater定理：若凸优化问题存在严格可行解，即存在，满足 则优化问题具有强对偶性。该条件称为Slater条件。精选强对偶性强对偶性并不是总是成立的。定义（强对偶性）：设精选强对偶性 存在，满足弱化的Slater条件：若不等式约束条件的前个为线性不等式约束条件，则Slater条件可以弱化为：精选强对偶性 存在，满足精选Least-squaressolutionoflinearequations原问题：对偶问题：具有强对偶性精选Least-squaressolutionofli精选LagrangedualofQCQPQCQP：拉格朗日函数：对偶函数：精选LagrangedualofQCQPQCQP：拉格精选LagrangedualofQCQP对偶问题：Slater条件：存在，满足精选LagrangedualofQCQP对偶问题：Sl精选Entropymaximization原始问题：对偶函数：对偶问题：精选Entropymaximization原始问题：对偶函精选Entropymaximization弱化的Slater条件：存在，满足精选Entropymaximization弱化的Slate精选Minimumvolumecoveringellipsoid原始问题：对偶函数：对偶问题：精选Minimumvolumecoveringelli精选Minimumvolumecoveringellipsoid弱化的Slater条件总成立，因此该优化问题具有强对偶性。弱化的Slater条件：存在，满足精选Minimumvolumecoveringelli精选对偶可行解的不等式对于一优化问题，若为一可行解，为对偶问题可行解，则有如下不等式： 为次优解，其中不等式可以用于对次优解的精度估计精选对偶可行解的不等式对于一优化问题，若为一可行解，精选互补松弛条件 所以设为原始优化问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则 即精选互补松弛条件 所以设为原始优化问题的最优解，精选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条件。精选对偶问题优化问题的拉格朗日函数及对偶函数的概念和性质；精选常见应用问题逼近问题的几种基本描述；统计估计问题的基本描述。精选常见应用问题逼近问题的几种基本描述；精选常用算法无约束问题常用算法：下降法最速下降牛顿法等式约束问题的常用算法等式约束条件的消去牛顿法内点法精选常用算法无约束问题常用算法：精选凸优化理论与应用庄伯金Bjzhuang@精选凸优化理论与应用庄伯金精选优化理论概述什么是优化问题？ObjectivefunctionConstraintfunctions精选优化理论概述什么是优化问题？Objectivefunc精选几类经典的优化问题线性规划问题最小二乘问题凸优化问题凸优化问题理论上有有效的方法进行求解！精选几类经典的优化问题线性规划问题最小二乘问题凸优化问题凸优精选本课程的主要内容理论部分凸集和凸函数凸优化问题对偶问题应用部分逼近与拟合统计估计几何问题算法部分非约束优化方法等式约束优化方法内点法精选本课程的主要内容理论部分精选熟悉了解凸优化理论的基本原理和基本方法；掌握实际问题转化为凸优化问题的基本方法；掌握最优化问题的经典算法。课程要求精选熟悉了解凸优化理论的基本原理和基本方法；课程要求精选参考书目StephenBoydandLievenVandenberghe,“ConvexOptimization”,CambridgeUniversityPress.袁亚湘、孙文瑜，“最优化理论与方法”，科学出版社，1999。

精选参考书目StephenBoydandLieven精选凸优化理论与应用第一章凸集精选凸优化理论与应用第一章精选仿射集(Affinesets)直线的表示：线段的表示：精选仿射集(Affinesets)直线的表示：线段的表示：精选仿射集(Affinesets)仿射集的定义：过集合C内任意两点的直线均在集合C内，则称集合C为仿射集。仿射集的例：直线、平面、超平面精选仿射集(Affinesets)仿射集的定义：过集合C内精选仿射集仿射包：包含集合C的最小的仿射集。仿射维数：仿射包的维数。精选仿射集仿射包：包含集合C的最小的仿射集。仿射维数：仿射包精选仿射集内点（interior）：相对内点（relativeinterior）：精选仿射集内点（interior）：相对内点（relativ精选凸集(ConvexSets)凸集的定义：集合C内任意两点间的线段均在集合C内，则称集合C为凸集。精选凸集(ConvexSets)凸集的定义：集合C内任意两精选凸集凸包的定义：包含集合C的最小的凸集。精选凸集凸包的定义：包含集合C的最小的凸集。精选锥(Cones)锥的定义：凸锥的定义：集合C既是凸集又是锥。锥包的定义：集合C内点的所有锥组合。精选锥(Cones)锥的定义：凸锥的定义：集合C既是凸集又是精选超平面和半空间超平面(hyperplane)：半空间(Halfspace)：精选超平面和半空间超平面(hyperplane)：半空间(精选欧氏球和椭球欧氏球(euclideanball):椭球(ellipsoid):精选欧氏球和椭球欧氏球(euclideanball):椭球精选范数球和范数锥范数(norm)：范数球(normball)：范数锥(normcone)：精选范数球和范数锥范数(norm)：范数球(normbal精选多面体(Polyhedra)多面体：单纯形(simplex)：精选多面体(Polyhedra)多面体：单纯形(simple精选半正定锥(Positivesemidefinitecone)n阶对称矩阵集：n阶半正定矩阵集：n阶正定矩阵集：n阶半正定矩阵集为凸锥！精选半正定锥(Positivesemidefinitec精选保持凸性的运算集合交运算仿射变换透视/投射函数(perspectivefunction)精选保持凸性的运算集合交运算精选保持凸性的运算线性分式函数(linear-fractionalfunction)精选保持凸性的运算线性分式函数(linear-fractio精选真锥(propercone)真锥的定义：锥满足如下条件K具有内点K内不含直线精选真锥(propercone)真锥的定义：锥精选广义不等式真锥下的偏序关系：例：逐项不等式矩阵不等式广义不等式严格广义不等式精选广义不等式真锥下的偏序关系：例：广义不等式严格广精选广义不等式的性质精选广义不等式的性质精选严格广义不等式的性质精选严格广义不等式的性质精选最值和极值最小元的定义：设，对，都有成立，则称为的最小元。极小元的定义：设，对于，若，则成立，则称为的极小元。精选最值和极值最小元的定义：设，对精选分割超平面(separatinghyperplane)定理：设和为两不相交凸集，则存在超平面将和分离。即：精选分割超平面(separatinghyperplane)精选支撑超平面(supportinghyperplane)定义：设集合，为边界上的点。若存在，满足对任意，都有成立，则称超平面为集合在点处的支撑超平面。定理：凸集边界上任意一点均存在支撑超平面。定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。精选支撑超平面(supportinghyperplane)精选对偶锥(dualcone)对偶锥的定义：设为锥，则集合称为对偶锥。对偶锥的性质：真锥的对偶锥仍然是真锥！精选对偶锥(dualcone)对偶锥的定义：设为锥，精选对偶广义不等式广义不等式与对偶等价性质最小元的对偶特性：精选对偶广义不等式广义不等式与对偶等价性质最小元的对偶特性：精选对偶广义不等式极小元的对偶特性反过来不一定成立！精选对偶广义不等式极小元的对偶特性反过来不一定成立！精选作业P602.8P602.10P602.14P622.16P622.18P642.30P642.31P642.33精选作业P602.8精选凸优化理论与应用第二章凸函数精选凸优化理论与应用第二章凸函数精选凸函数的定义1.定义域为凸集；2.，有凸函数的定义：函数，满足凸函数的扩展定义：若为凸函数，则可定义其扩展函数为凸函数的扩展函数也是凸函数！精选凸函数的定义1.定义域为凸集；2.精选凸函数的一阶微分条件若函数的定义域为开集，且函数一阶可微，则函数为凸函数当且仅当为凸集，且对精选凸函数的一阶微分条件若函数的定义域精选凸函数的二阶微分条件若函数的定义域为开集，且函数二阶可微，则函数为凸函数当且仅当为凸集，且对，其Hessian矩阵精选凸函数的二阶微分条件若函数的定义域精选凸函数的例幂函数负对数函数负熵函数范数函数指数函数精选凸函数的例幂函数负对数函数负熵函数范数函数指数函数精选凸函数的例精选凸函数的例精选下水平集(sublevelset)定理：凸函数的任一下水平集均为凸集。任一下水平集均为凸集的函数不一定为凸函数。 称为的下水平集。定义：集合精选下水平集(sublevelset)定理：凸函数的任一下精选函数上半图(epigraph)定理：函数为凸函数当且仅当的上半图为凸集。 称为函数的上半图。定义：集合精选函数上半图(epigraph)定理：函数为凸函数精选Jensen不等式为凸函数，则有：Jensen不等式的另外形式：精选Jensen不等式为凸函数，则有：Jensen不等精选保持函数凸性的算子凸函数的逐点最大值凸函数与仿射变换的复合凸函数的非负加权和精选保持函数凸性的算子凸函数的逐点最大值凸函数与仿射变换的复精选保持函数凸性的算子复合运算最小值算子凸函数的透视算子精选保持函数凸性的算子复合运算最小值算子凸函数的透视算子精选共轭函数(conjugatefunction)定义：设函数，其共轭函数，定义为共轭函数的例共轭函数具有凸性！精选共轭函数(conjugatefunction)定义：设精选共轭函数的性质Fenchel’sinequality性质：若为凸函数，且的上半图是闭集，则有性质：设为凸函数，且可微，对于，若 则精选共轭函数的性质Fenchel’sinequality性精选准凸函数(quasiconvexfunction)准凸函数的例定义：设函数，若函数的定义域和任意下水平集

则称函数为准凸函数。精选准凸函数(quasiconvexfunction)准凸精选准凸函数的判定定理定理：函数为准凸函数，当且仅当为凸集，且对，有定理：若函数一阶可微，则为准凸函数，当且仅当为凸集，且对，有 ，有定理：若函数二阶可微，且满足对 则函数准凸函数。精选准凸函数的判定定理定理：函数为准凸函数，精选最小值函数非负权值函数的最大值函数保持准凸性的算子复合函数精选最小值函数非负权值函数的最大值函数保持准凸性的算子复合函精选准凸函数的凸函数族表示若为准凸函数，根据的任意下水平集，我们可以构造一个凸函数族，使得性质：若为准凸函数的凸函数族表示，对每一个，若，则有精选准凸函数的凸函数族表示若为准凸函数，根精选对数凸函数 为凸集 为凸函数。定义：函数称为对数凸函数，若函数满足：定理：函数的定义域为凸集，且，则为对数凸函数，当且仅当对有对数凸函数的例精选对数凸函数 为凸集 为凸函数精选对数凸函数和凹函数的性质性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。定理：函数二阶可微，则为对数凸函数当且仅当性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。推论：函数对每一个在上对数