凸优化理论和常见的应用

1、凸优化理论和常见的应用1优化理论概述什么是优化问题？Objective functionConstraint functions2几类经典的优化问题线性规划问题最小二乘问题凸优化问题凸优化问题理论上有有效的方法进行求解！3本课程的主要内容理论部分凸集和凸函数凸优化问题对偶问题应用部分逼近与拟合统计估计几何问题算法部分非约束优化方法等式约束优化方法内点法4熟悉了解凸优化理论的基本原理和基本方法；掌握实际问题转化为凸优化问题的基本方法；掌握最优化问题的经典算法。课程要求5参考书目Stephen Boyd and Lieven Vandenberghe, “Convex Optimization”,

2、 Cambridge University Press.袁亚湘、孙文瑜，“最优化理论与方法”，科学出版社，1999。 6凸优化理论与应用第一章凸集7仿射集(Affine sets)直线的表示：线段的表示：8仿射集(Affine sets)仿射集的定义：过集合C内任意两点的直线均在集合C内，则称集合C为仿射集。仿射集的例：直线、平面、超平面9仿射集仿射包：包含集合C的最小的仿射集。仿射维数：仿射包的维数。10仿射集内点（interior）：相对内点（relative interior）：11凸集(Convex Sets)凸集的定义：集合C内任意两点间的线段均在集合C内，则称集合C为凸集。12凸集

3、凸包的定义：包含集合C的最小的凸集。13锥(Cones)锥的定义：凸锥的定义：集合C既是凸集又是锥。锥包的定义：集合C内点的所有锥组合。14超平面和半空间超平面(hyperplane) ：半空间(Halfspace)：15欧氏球和椭球欧氏球(euclidean ball):椭球(ellipsoid):16范数球和范数锥范数(norm)：范数球(norm ball)：范数锥(norm cone)：17多面体(Polyhedra)多面体：单纯形(simplex)：18半正定锥(Positive semidefinite cone)n阶对称矩阵集：n阶半正定矩阵集：n阶正定矩阵集：n阶半正定矩阵集为

4、凸锥！19保持凸性的运算集合交运算仿射变换透视/投射函数(perspective function)20保持凸性的运算线性分式函数(linear-fractional function)21真锥(proper cone)真锥的定义：锥 满足如下条件K具有内点K内不含直线22广义不等式真锥 下的偏序关系：例：逐项不等式矩阵不等式广义不等式严格广义不等式23广义不等式的性质24严格广义不等式的性质25最值和极值最小元的定义：设 ，对 ，都有 成立，则称 为 的最小元。极小元的定义：设 ，对于 ，若 ，则 成立，则称 为 的极小元。26分割超平面(separating hyperplane)定理：设

5、 和 为两不相交凸集，则存在超平面将 和 分离。即：27支撑超平面(supporting hyperplane)定义：设集合 ， 为 边界上的点。若存在 ，满足对任意 ，都有 成立，则称超平面 为集合 在点 处的支撑超平面。定理：凸集边界上任意一点均存在支撑超平面。定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。28对偶锥(dual cone)对偶锥的定义：设 为锥，则集合 称为对偶锥。对偶锥的性质：真锥的对偶锥仍然是真锥！29对偶广义不等式广义不等式与对偶等价性质最小元的对偶特性：30对偶广义不等式极小元的对偶特性反过来不一定成立！31作业P62 32凸优化理论

6、与应用第二章 凸函数33凸函数的定义1.定义域 为凸集；2. ，有凸函数的定义：函数 ，满足凸函数的扩展定义：若 为凸函数，则可定义其扩展函数 为凸函数的扩展函数也是凸函数！34凸函数的一阶微分条件若函数 的定义域 为开集，且函数 一阶可微，则函数 为凸函数当且仅当 为凸集，且对35凸函数的二阶微分条件若函数 的定义域 为开集，且函数 二阶可微，则函数 为凸函数当且仅当 为凸集，且对 ，其Hessian矩阵36凸函数的例幂函数负对数函数负熵函数范数函数指数函数37凸函数的例38下水平集(sublevel set)定理：凸函数的任一下水平集均为凸集。任一下水平集均为凸集的函数不一定为凸函数。称为

7、 的 下水平集。定义：集合39函数上半图(epigraph)定理：函数 为凸函数当且仅当 的上半图为凸集。称为函数 的上半图。定义：集合40Jensen不等式 为凸函数，则有：Jensen不等式的另外形式：41保持函数凸性的算子凸函数的逐点最大值凸函数与仿射变换的复合凸函数的非负加权和42保持函数凸性的算子复合运算最小值算子凸函数的透视算子43共轭函数(conjugate function)定义：设函数 ，其共轭函数 ，定义为共轭函数的例共轭函数具有凸性！44共轭函数的性质Fenchels inequality性质：若 为凸函数，且 的上半图是闭集，则有性质：设 为凸函数，且可微，对于 ，若则

8、45准凸函数(quasiconvex function)准凸函数的例定义：设函数 ，若函数的定义域和任意下水平集则称函数 为准凸函数。46准凸函数的判定定理定理：函数 为准凸函数，当且仅当 为凸集，且对 ，有定理：若函数 一阶可微，则 为准凸函数，当且仅当 为凸集，且对 ，有 ，有定理：若函数 二阶可微，且满足对则函数 准凸函数。47保持准凸性的算子最小值函数非负权值函数的最大值函数复合函数48准凸函数的凸函数族表示若 为准凸函数，根据 的任意 下水平集，我们可以构造一个凸函数族 ，使得性质：若 为准凸函数 的凸函数族表示，对每一个 ，若 ，则有49对数凸函数 为凸集为凸函数。定义：函数 称为

9、对数凸函数，若函数 满足：定理：函数 的定义域为凸集，且 ，则 为对数凸函数，当且仅当对 有对数凸函数的例50对数凸函数和凹函数的性质性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。定理：函数 二阶可微，则 为对数凸函数当且仅当性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。推论：函数 对每一个 在 上对数凸，则函数 也是对数凸函数。51对数凸函数和凹函数的性质定理：函数 为对数凹函数，则函数 是对数凹函数。52广义不等式下的凸性广义单调性的定义：设 为真锥，函数 称为 单调增，若函数 满足：广义凸函数的定义：设 为真锥，函数 称为 凸，若函数 满足对 均有定理(对偶

10、等价)：函数 为 凸函数，当且仅当对所有 ， 为凸函数。53作业(1)54作业(2)P122 3.49 (1)(2)55凸优化理论与应用第三章 凸优化56优化问题的基本形式优化问题的基本描述：优化变量不等式约束等式约束无约束优化57优化问题的基本形式最优化值最优化解 优化问题的域 可行点(解) (feasible) 满足约束条件 可行域(可解集) 所有可行点的集合58局部最优问题局部最优问题59优化问题的等价形式(1)定理：若 则原优化问题与以下优化问题等价60优化问题的等价形式(2)定理：设 为一一对应，且 则原优化问题与以下优化问题等价61优化问题的等价形式(3)定理：设 为严格单调增函数

11、； 满足 当且仅当 ； 满足 当且仅当 。则原优化问题与以下优化问题等价62优化问题的等价形式(4)定理：原优化问题与以下优化问题等价 称为松弛变量63优化问题的等价形式(5)定理：设 满足等式 成立，当且仅当 。则原优化问题与以下优化问题等价64可分离变量优化问题性质：其中可以分离变量定理：优化问题65优化问题的上半图形式66凸优化问题的基本形式凸优化问题的基本描述： 为仿射函数 为凸函数 若 为准凸函数，则优化问题称为准凸优化问题。 性质：凸优化问题的可行域是凸集。67凸优化问题的例例：等价于凸优化问题68凸优化问题的局部最优解定理：凸优化问题的局部最优解均是全局最优解。69凸优化问题最优

12、解的微分条件定理：设 为凸优化问题的可行域， 可微。则 为最优解当且仅当 成立。定理：非约束凸优化问题中，若 可微。则 为最优解当且仅当 成立。70凸优化问题的等价形式则 为最优解当且仅当 ，且存在向量 满足 定理：设凸优化问题仅有等式约束71凸优化问题的等价形式则 为最优解当且仅当 ，且 定理：设凸优化问题72凸优化问题的等价形式等价于 定理：设凸优化问题其中 73凸优化问题的等价形式等价于 定理：设凸优化问题74准凸优化问题 为准凸函数， 为凸函数。准凸优化问题的基本描述注：准凸优化问题的局部最优解不一定是全局最优解。75准凸优化问题的上半图形式设 为准凸函数 的凸函数族表示，即 则准凸优

13、化问题的可行解问题为设 为准凸优化问题的最优解，若上述问题可解，则 。否则 。76准凸优化问题二分法求解给定一个足够小的 和足够大的 ，使得区间 能包含最优解 。给定LOOP：令求解可行解问题；若可解，则令 ，否则令若 ，则结束，否则goto LOOP。 77线性规划(linear program,LP)LP问题的一般描述78LP问题的几种类型标准LP问题不等式形式LP问题79标准LP问题的转换80LP问题的例Chebyshev center of a polyhedronPiecewise-linear minimizationLinear-fractional programming81C

14、hebyshev center of a polyhedron多面体Chebyshev center：到多面体边界距离最大的内点（最深的点）问题描述LP形式82Piecewise-linear minimization问题描述上半图形式LP形式83Linear-fractional programming问题描述LP形式84二次规划(quadratic program,QP)QP问题的基本描述85二次约束二次规划quadratically constrained quadratic program (QCQP)86QP问题的例Least-squares and regressionDistan

15、ce between polyhedra87Least-squares and regression问题描述88Distance between polyhedra问题描述QP形式89Second-order cone program, SOCPSOCP问题的基本描述二次锥约束条件90SOCP问题的例Robust linear programming问题描述其中 不是完全确定的常数。例： 为确定的常数， 为变量，其范围满足SOCP形式91几何规划(Geometric programming)单项式与多项式几何规划的基本描述92几何规划的凸形式转换令几何规划的凸形式93广义不等式约束广义不等式约

16、束的优化问题SOCP的描述94凸优化理论与应用第四章 对偶问题95优化问题的拉格朗日函数设优化问题：拉格朗日(Lagrangian)函数：对固定的 ，拉格朗日函数 为关于 和 的仿射函数。96拉格朗日对偶函数拉格朗日对偶函数(lagrange dual function) ：若拉格朗日函数没有下界，则令拉格朗日对偶函数为凹函数。对 和 ，若原最优化问题有最优值 ，则97对偶函数的例Least-squares solution of linear equationsStandard form LPTwo-way partitioning problem98Least-squares soluti

17、on of linear equations原问题：拉格朗日函数：拉格朗日对偶函数：99Standard form LP原问题：拉格朗日函数：拉格朗日对偶函数：100Two-way partitioning problem原问题：拉格朗日函数：拉格朗日对偶函数：101对偶函数与共轭函数共轭函数共轭函数与对偶函数存在密切联系具有线性不等式约束和线性等式约束的优化问题： 对偶函数：102Equality constrained norm minimization问题描述：共轭函数：对偶函数：103Entropy maximization原始问题：共轭函数：对偶函数：104Minimum volum

18、e covering ellipsoid原始问题：对偶函数：共轭函数：105拉格朗日对偶问题拉格朗日对偶问题的描述：对偶可行域最优值最优解106LP问题的对偶问题标准LP问题对偶函数对偶问题等价描述107弱对偶性定理（弱对偶性） ：设原始问题的最优值为 ，对偶问题的最优值为 ，则 成立。optimal duality gap可以利用对偶问题找到原始问题最优解的下界。108强对偶性强对偶性并不是总是成立的。定义（强对偶性） ：设原始问题的最优值为 ，对偶问题的最优值为 。若 成立，则称原始问题和对偶问题之间具有强对偶性。凸优化问题通常（但并不总是）具有强对偶性。Slater定理：若凸优化问题存在

19、严格可行解，即存在 ，满足则优化问题具有强对偶性。该条件称为Slater条件。109强对偶性存在 ，满足弱化的Slater条件：若不等式约束条件的前 个为线性不等式约束条件，则Slater条件可以弱化为：110Least-squares solution of linear equations原问题：对偶问题：具有强对偶性111Lagrange dual of QCQPQCQP：拉格朗日函数：对偶函数：112Lagrange dual of QCQP对偶问题：Slater条件：存在 ，满足113Entropy maximization原始问题：对偶函数：对偶问题：114Entropy maxi

20、mization弱化的Slater条件：存在 ，满足115Minimum volume covering ellipsoid原始问题：对偶函数：对偶问题：116Minimum volume covering ellipsoid弱化的Slater条件总成立，因此该优化问题具有强对偶性。弱化的Slater条件：存在 ，满足117对偶可行解的不等式对于一优化问题，若 为一可行解， 为对偶问题可行解，则有如下不等式： 为 次优解，其中不等式可以用于对次优解的精度估计118互补松弛条件所以设 为原始优化问题的最优解， 为对偶问题的最优解，若两者具有强对偶性，则即119KKT优化条件设优化问题中，函数 可

21、微。设 为原始优化问题的最优解， 为对偶问题的最优解，且两者具有强对偶性，则 满足如下条件：KKT条件为必要条件！120凸优化问题的KKT条件可微。设 满足KKT条件，则 为原始问题的最优解，而 为对偶问题的最优解，且两者具有强对偶性。设原始问题为凸优化问题中，函数121例原始凸优化问题KKT条件122例其中解得123凸优化问题的对偶求解存在唯一解 。若 为原始问题的可行解，则 即为原始问题的最优解；若 不是原始问题的可行解，则原始问题不存在最优解。设原始优化问题与对偶问题具有强对偶性，且 为对偶问题的最优解。 存在唯一的最小解，即124扰动问题扰动问题：当 时即为原始问题。若 为正，则第 个

22、不等式约束被放宽；若 为负，则第 个不等式约束被收紧。记 为扰动问题的最优解。若扰动问题无最优解，则记125灵敏度分析设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为 ，则有若 在 处可微，则126选择定理定义（弱选择性）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。对偶不等式组设原始问题的约束条件：对偶问题原始问题的约束条件与对偶不等式组具有弱选择性。127选择定理对偶不等式组设原始问题的严格不等式约束条件：原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。128选择定理定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这

23、两个系统具有强选择性。对偶不等式组设原始问题为凸优化问题，其严格不等式约束条件为：若存在 ，满足 ，则上述两不等式约束系统具有强选择性。129选择定理对偶不等式组设原始问题为凸优化问题，其不等式约束条件为：则原始问题的不等式约束条件与对偶不等式组具有强选择性。若存在 ，满足 ，且下述优化问题存在最优解130罚函数的例 范数：死区线性罚函数：对数门限罚函数131鲁棒的罚函数若 大到一定程度时，罚函数为 的线性函数，则称该罚函数为鲁棒的罚函数。Huber罚函数132最小范数问题问题描述：其中 为方程组 的解。可以消去等式约束将其转换为范数逼近问题：133最小范数问题最小平方范数问题：范数 ，最优解

24、满足：最小罚问题：绝对值和最小问题：范数 ，原问题可转换为LP问题：134正则逼近二元矢量优化问题描述：正则化问题：最优解描述了两分量的一条折中曲线。135正则逼近Tikhonov正则化问题：为二次优化问题：最优解的形式：136正则逼近Tikhonov光滑正则化问题： 为二阶差分算子：137信号复原已知加噪信号：信号复原问题的描述：函数 为正则函数或光滑函数。138信号复原139信号复原140信号复原141鲁棒逼近问题描述：随机鲁棒逼近： 为随机变量，逼近问题转换为最小化期望例：随机鲁棒逼近为：转换为：142随机鲁棒逼近 为随机变量：最小平方随机鲁棒逼近为：转换为：其中143最坏情况鲁棒逼近考

25、虑 ，最坏情况鲁棒逼近为： 例：随机鲁棒逼近为：转换为：144凸优化理论与应用第6章 统计估计145概率分布的参数估计随机变量的概率密度为 ，其中 为概率分布的参数，且参数未知。参数估计的目标就是通过一些已知样本估计获得参数的最优近似值。问题描述 为样本观测值； 为对数似然函数；若似然函数为凹函数，则优化问题为凸优化问题。146具有独立同分布噪声的线性测量线性测量模型： 为观测值或测量值； 为未知参数向量； 独立同分布噪声，其概率密度为 。似然函数为最大似然估计问题为：147例高斯白噪声对数似然函数：区间 上均匀分布的噪声：对数似然函数：148逻辑回归随机变量 的概率分布为： 为参数； 为可观

26、测的解释变量； 为观察值。对数似然函数：149假定测验随机变量 ，有 种可能（假定）的分布；假定 ： 的概率分布为假定测验的目标：由观察值猜测随机变量最有可能服从哪种假定的分布。当 时，称为二元假定测验。随机检测子：非负元素矩阵 150假定测验 为当 实际服从第1种假定分布而猜测为第2种假定分布的概率； 为当 实际服从第2种假定分布而猜测为第1种假定分布的概率；多目标优化形式：检测概率矩阵151假定测验最小最大值形式尺度优化形式：152例 在两种假设下的概率分布为：153例154实验设计线性测量问题最大似然估计值： 独立同分布高斯白噪声，服从分布 。估计误差 均值为0，方差为信赖椭圆为155实

27、验设计实验设计的目标：寻找 ，使得误差的方差矩阵最小。向量优化形式：为整数问题，求解较困难。156实验设计当 时，令 近似为一连续实数，原问题可松弛转换为连续实数优化：157凸优化理论与应用第7章 无约束优化158无约束优化问题问题描述：无约束问题求解的两种方法：迭代逼近：求解梯度方程： 为凸函数，且二次可微。159例梯度方程二次优化：160迭代起始点满足条件2的几种函数：起始点 满足：函数 任意下水平集都是闭集；函数的定义域为当 时，161强凸性定义：函数 在 上具有强凸性，若 满足若函数 具有强凸性，则有 为最优值，则162强凸性则有 为最优值，则若函数 在 上具有强凸性，则可以证明存在

28、，满足 163强凸性对于 ，矩阵 的特征值从大到小依次为 。则有： 定义：矩阵 的条件数为最大特征值与最小特征值之比，即 。条件数的上界：164下降法下降法的基本原理：迭代 ，满足 为下降方向， 为步长因子。对于凸函数 ，当 满足 时，存在某个 ，使得 。165下降法下降法的一般步骤：给出初始点 ；循环迭代计算下降方向 ； 搜索步长因子 ； 迭代： 166步长因子搜索精确一维搜索：回溯一维搜索：给定参数循环迭代初始化：令 ； 若 ，则终止退出； 否则令 167步长因子搜索168梯度下降法算法简单，但收敛速度较慢。下降方向：终止条件：收敛性：其中 。169收敛性分析则有：设函数 具有强凸性，则存

29、在 和 ，满足：若 采用精确一维搜索，则 ，收敛速度因子：若 采用回溯一维搜索，收敛速度因子：条件数越大，收敛速度越小。170例当 时，算法收敛速度很慢。初始解为 ，采用精确一维搜索；迭代：171例步长因子采用回溯一维搜索。172最速下降法归一化最速下降方向：非归一化最速下降方向欧式范数：二次范数 ： 范数：173最速下降法174收敛性分析范数界：收敛速度因子：175牛顿法设函数 二阶可微，则在 附近， 的泰勒展式为：泰勒展开可作为 在 附近的近似；下降方向：为二次范数 上的最速下降方向。176牛顿法177牛顿减量令 为 在 处的牛顿减量。牛顿减量的性质1：性质2：牛顿减量可作为迭代求解的误差

30、估计。性质3：牛顿减量具有仿射不变性。178牛顿方法初始化：给定初始解 以及LOOP：计算：若 则终止退出；一维线性搜索：计算步长因子 ；迭代：179收敛性分析定理：假设 二阶连续可微，具有强凸性，即存在 ，满足：则存在 ，且海森矩阵满足Lipschitz条件，即存在 ，满足：若 ，则 ；若 ，则 ，且180收敛性分析定理：假设 二阶连续可微，具有强凸性，即存在 ，满足：则存在 ，对于 ，有且海森矩阵满足Lipschitz条件，即存在 ，满足：181例182凸优化理论与应用第8章 等式约束优化183等式约束优化问题问题描述： 为凸函数，且二次连续可微，且假设最优值 存在，则 为最优解当且仅当存

31、在 ，满足（KKT条件）：184例KKT系统：二次优化：KKT系统可解，则二次优化问题存在最优解。系数矩阵称为KKT矩阵。KKT矩阵非奇异当且仅当：185消去等式约束方程组 的解集： 为方程组的一个特解， 为 的零空间范围。无约束优化形式：若 为最优解，则有186对偶问题对偶形式：187牛顿法牛顿减量 为等式约束优化的可行解，则在 附近原问题的二次近似为：设 和 分别为该问题和对偶问题的最优解，则满足：188牛顿减量性质2：牛顿减量具有仿射不变性。牛顿减量牛顿减量的性质：189可行下降方向可行下降方向：设 满足方程组 。若 满足方程组 ，则 。 称为可行方向。若对于较小的 ，有 ，则 为可行下

32、降方向。190等式约束的牛顿方法LOOP：计算 及 ；若 则终止退出；一维线性搜索：计算步长因子 ；迭代：初始化：给定初始解 满足 ，以及191消去等式约束的牛顿方法转换为等式约束下的牛顿方法：初始值 ，第 次迭代值 ；初始值：迭代值：192非可行解为初始点的牛顿法函数 二阶连续可微，因此有 为等式约束优化的非可行解，则增量 应尽可能使 满足KKT条件，即：设 和 为KKT条件的解，即有：193非可行解为初始点的牛顿法则KKT条件可表示为：令设 为不满足KKT条件，则其迭代量需满足：即194非可行解为初始点的牛顿法当 且 时，终止迭代。LOOP：计算 和 ；回溯一维线性搜索：迭代：初始化：给定初始解 及 ，以及令 ；While 195KKT系统的求解其中 ，且满足 。1. 分解；2.若