凸优化理论与应用PPT课件

.,1,凸优化理论与应用,庄伯金Bjzhuang,.,2,优化理论概述,什么是优化问题？,Objectivefunction,Constraintfunctions,.,3,几类经典的优化问题,线性规划问题,最小二乘问题,凸优化问题,凸优化问题理论上有有效的方法进行求解！,.,4,本课程的主要内容,理论部分凸集和凸函数凸优化问题对偶问题应用部分逼近与拟合统计估计几何问题算法部分非约束优化方法等式约束优化方法内点法,.,5,熟悉了解凸优化理论的基本原理和基本方法；掌握实际问题转化为凸优化问题的基本方法；掌握最优化问题的经典算法。,课程要求,.,6,参考书目,StephenBoydandLievenVandenberghe,“ConvexOptimization”,CambridgeUniversityPress.袁亚湘、孙文瑜，“最优化理论与方法”，科学出版社，1999。,.,7,凸优化理论与应用,第一章凸集,.,8,仿射集(Affinesets),直线的表示：,线段的表示：,.,9,仿射集(Affinesets),仿射集的定义：过集合C内任意两点的直线均在集合C内，则称集合C为仿射集。仿射集的例：直线、平面、超平面,.,10,仿射集,仿射包：包含集合C的最小的仿射集。,仿射维数：仿射包的维数。,.,11,仿射集,内点（interior）：,相对内点（relativeinterior）：,.,12,凸集(ConvexSets),凸集的定义：集合C内任意两点间的线段均在集合C内，则称集合C为凸集。,.,13,凸集,凸包的定义：包含集合C的最小的凸集。,.,14,锥(Cones),锥的定义：,凸锥的定义：集合C既是凸集又是锥。,锥包的定义：集合C内点的所有锥组合。,.,15,超平面和半空间,超平面(hyperplane)：,半空间(Halfspace)：,.,16,欧氏球和椭球,欧氏球(euclideanball):,椭球(ellipsoid):,.,17,范数球和范数锥,范数(norm)：,范数球(normball)：,范数锥(normcone)：,.,18,多面体(Polyhedra),多面体：,单纯形(simplex)：,.,19,半正定锥(Positivesemidefinitecone),n阶对称矩阵集：,n阶半正定矩阵集：,n阶正定矩阵集：,n阶半正定矩阵集为凸锥！,.,20,保持凸性的运算,集合交运算仿射变换透视/投射函数(perspectivefunction),.,21,保持凸性的运算,线性分式函数(linear-fractionalfunction),.,22,真锥(propercone),真锥的定义：锥满足如下条件,K具有内点,K内不含直线,.,23,广义不等式,真锥下的偏序关系：,例：逐项不等式矩阵不等式,广义不等式,严格广义不等式,.,24,广义不等式的性质,.,25,严格广义不等式的性质,.,26,最值和极值,最小元的定义：设，对，都有成立，则称为的最小元。,极小元的定义：设，对于，若，则成立，则称为的极小元。,.,27,分割超平面(separatinghyperplane),定理：设和为两不相交凸集，则存在超平面将和分离。即：,.,28,支撑超平面(supportinghyperplane),定义：设集合，为边界上的点。若存在，满足对任意，都有成立，则称超平面为集合在点处的支撑超平面。,定理：凸集边界上任意一点均存在支撑超平面。定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。,.,29,对偶锥(dualcone),对偶锥的定义：设为锥，则集合称为对偶锥。,对偶锥的性质：,真锥的对偶锥仍然是真锥！,.,30,对偶广义不等式,广义不等式与对偶等价性质,最小元的对偶特性：,.,31,对偶广义不等式,极小元的对偶特性,反过来不一定成立！,.,32,作业,P602.8P602.10P602.14P622.16P622.18P642.30P642.31P642.33,.,33,凸优化理论与应用,第二章凸函数,.,34,凸函数的定义,1.定义域为凸集；,2.，有,凸函数的定义：函数，满足,凸函数的扩展定义：若为凸函数，则可定义其扩展函数为,凸函数的扩展函数也是凸函数！,.,35,凸函数的一阶微分条件,若函数的定义域为开集，且函数一阶可微，则函数为凸函数当且仅当为凸集，且对,.,36,凸函数的二阶微分条件,若函数的定义域为开集，且函数二阶可微，则函数为凸函数当且仅当为凸集，且对，其Hessian矩阵,.,37,凸函数的例,幂函数,负对数函数,负熵函数,范数函数,指数函数,.,38,凸函数的例,.,39,下水平集(sublevelset),定理：凸函数的任一下水平集均为凸集。,任一下水平集均为凸集的函数不一定为凸函数。,.,40,函数上半图(epigraph),定理：函数为凸函数当且仅当的上半图为凸集。,.,41,Jensen不等式,为凸函数，则有：,Jensen不等式的另外形式：,.,42,保持函数凸性的算子,凸函数的逐点最大值,凸函数与仿射变换的复合,凸函数的非负加权和,.,43,保持函数凸性的算子,复合运算,最小值算子,凸函数的透视算子,.,44,共轭函数(conjugatefunction),定义：设函数，其共轭函数，定义为,共轭函数的例,共轭函数具有凸性！,.,45,共轭函数的性质,Fenchelsinequality,性质：若为凸函数，且的上半图是闭集，则有,.,46,准凸函数(quasiconvexfunction),准凸函数的例,.,47,准凸函数的判定定理,定理：函数为准凸函数，当且仅当为凸集，且对，有,定理：若函数一阶可微，则为准凸函数，当且仅当为凸集，且对，有,.,48,最小值函数,非负权值函数的最大值函数,保持准凸性的算子,复合函数,.,49,准凸函数的凸函数族表示,若为准凸函数，根据的任意下水平集，我们可以构造一个凸函数族，使得,性质：若为准凸函数的凸函数族表示，对每一个，若，则有,.,50,对数凸函数,对数凸函数的例,.,51,对数凸函数和凹函数的性质,性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。,定理：函数二阶可微，则为对数凸函数当且仅当,性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。,推论：函数对每一个在上对数凸，则函数也是对数凸函数。,.,52,对数凸函数和凹函数的性质,定理：函数为对数凹函数，则函数是对数凹函数。,.,53,广义不等式下的凸性,广义单调性的定义：设为真锥，函数称为单调增，若函数满足：,定理(对偶等价)：函数为凸函数，当且仅当对所有，为凸函数。,.,54,作业(1),P1163.16P1163.21,.,55,作业(2),P1213.41P1223.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：令求解可行解问题；若可解，则令，否则令若，则结束，否则gotoLOOP。,.,78,线性规划(linearprogram,LP),LP问题的一般描述,.,79,LP问题的几种类型,标准LP问题,不等式形式LP问题,.,80,标准LP问题的转换,.,81,LP问题的例,Chebyshevcenterofapolyhedron,Piecewise-linearminimization,Linear-fractionalprogramming,.,82,Chebyshevcenterofapolyhedron,多面体,Chebyshevcenter：到多面体边界距离最大的内点（最深的点）,问题描述,LP形式,.,83,Piecewise-linearminimization,问题描述,上半图形式,LP形式,.,84,Linear-fractionalprogramming,问题描述,LP形式,.,85,二次规划(quadraticprogram,QP),QP问题的基本描述,.,86,二次约束二次规划,quadraticallyconstrainedquadraticprogram(QCQP),.,87,QP问题的例,Least-squaresandregression,Distancebetweenpolyhedra,.,88,Least-squaresandregression,问题描述,.,89,Distancebetweenpolyhedra,问题描述,QP形式,.,90,Second-orderconeprogram,SOCP,SOCP问题的基本描述,二次锥约束条件,.,91,SOCP问题的例Robustlinearprogramming,例：为确定的常数，为变量，其范围满足,SOCP形式,.,92,几何规划(Geometricprogramming),单项式与多项式,几何规划的基本描述,.,93,几何规划的凸形式转换,令,几何规划的凸形式,.,94,广义不等式约束,广义不等式约束的优化问题,SOCP的描述,.,95,凸优化理论与应用,第四章对偶问题,.,96,优化问题的拉格朗日函数,设优化问题：,拉格朗日(Lagrangian)函数：,对固定的，拉格朗日函数为关于和的仿射函数。,.,97,拉格朗日对偶函数,拉格朗日对偶函数(lagrangedualfunction)：,若拉格朗日函数没有下界，则令,拉格朗日对偶函数为凹函数。,对和，若原最优化问题有最优值，则,.,98,对偶函数的例,Least-squaressolutionoflinearequations,StandardformLP,Two-waypartitioningproblem,.,99,Least-squaressolutionoflinearequations,原问题：,拉格朗日函数：,拉格朗日对偶函数：,.,100,StandardformLP,原问题：,拉格朗日函数：,拉格朗日对偶函数：,.,101,Two-waypartitioningproblem,原问题：,拉格朗日函数：,拉格朗日对偶函数：,.,102,对偶函数与共轭函数,共轭函数,共轭函数与对偶函数存在密切联系,具有线性不等式约束和线性等式约束的优化问题：,对偶函数：,.,103,Equalityconstrainednormminimization,问题描述：,共轭函数：,对偶函数：,.,104,Entropymaximization,原始问题：,共轭函数：,对偶函数：,.,105,Minimumvolumecoveringellipsoid,原始问题：,对偶函数：,共轭函数：,.,106,拉格朗日对偶问题,拉格朗日对偶问题的描述：,对偶可行域,最优值,最优解,.,107,LP问题的对偶问题,标准LP问题,对偶函数,对偶问题,等价描述,.,108,弱对偶性,定理（弱对偶性）：设原始问题的最优值为，对偶问题的最优值为，则成立。,optimaldualitygap,可以利用对偶问题找到原始问题最优解的下界。,.,109,强对偶性,强对偶性并不是总是成立的。,定义（强对偶性）：设原始问题的最优值为，对偶问题的最优值为。若成立，则称原始问题和对偶问题之间具有强对偶性。,凸优化问题通常（但并不总是）具有强对偶性。,.,110,强对偶性,存在，满足,弱化的Slater条件：若不等式约束条件的前个为线性不等式约束条件，则Slater条件可以弱化为：,.,111,Least-squaressolutionoflinearequations,原问题：,对偶问题：,具有强对偶性,.,112,LagrangedualofQCQP,QCQP：,拉格朗日函数：,对偶函数：,.,113,LagrangedualofQCQP,对偶问题：,Slater条件：存在，满足,.,114,Entropymaximization,原始问题：,对偶函数：,对偶问题：,.,115,Entropymaximization,弱化的Slater条件：存在，满足,.,116,Minimumvolumecoveringellipsoid,原始问题：,对偶函数：,对偶问题：,.,117,Minimumvolumecoveringellipsoid,弱化的Slater条件总成立，因此该优化问题具有强对偶性。,弱化的Slater条件：存在，满足,.,118,对偶可行解的不等式,对于一优化问题，若为一可行解，为对偶问题可行解，则有如下不等式：,为次优解，其中,不等式可以用于对次优解的精度估计,.,119,互补松弛条件,所以,设为原始优化问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则,即,.,120,KKT优化条件,设优化问题中，函数可微。设为原始优化问题的最优解，为对偶问题的最优解，且两者具有强对偶性，则满足如下条件：,KKT条件为必要条件！,.,121,凸优化问题的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,则优化问题具有强对偶性，其对偶问题亦可解。,假设存在，满足严格不等式条件,不等式约束优化问题,问题描述：,为凸函数