凸优化理论与应用.ppt

《凸优化理论与应用.ppt》由会员分享，可在线阅读，更多相关《凸优化理论与应用.ppt（217页珍藏版）》请在三一办公上搜索。

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

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

3、 Sets),凸集的定义：集合C内任意两点间的线段均在集合C内，则称集合C为凸集。,13,凸集,凸包的定义：包含集合C的最小的凸集。,14,锥(Cones),锥的定义：,凸锥的定义：集合C既是凸集又是锥。,锥包的定义：集合C内点的所有锥组合。,15,超平面和半空间,超平面(hyperplane)：,半空间(Halfspace)：,16,欧氏球和椭球,欧氏球(euclidean ball):,椭球(ellipsoid):,17,范数球和范数锥,范数(norm)：,范数球(norm ball)：,范数锥(norm cone)：,18,多面体(Polyhedra),多面体：,单纯形(simplex)

4、：,19,半正定锥(Positive semidefinite cone),n阶对称矩阵集：,n阶半正定矩阵集：,n阶正定矩阵集：,n阶半正定矩阵集为凸锥！,20,保持凸性的运算,集合交运算仿射变换透视/投射函数(perspective function),21,保持凸性的运算,线性分式函数(linear-fractional function),22,真锥(proper cone),真锥的定义：锥 满足如下条件,K具有内点,K内不含直线,23,广义不等式,真锥 下的偏序关系：,例：逐项不等式矩阵不等式,广义不等式,严格广义不等式,24,广义不等式的性质,25,严格广义不等式的性质,26,最值

5、和极值,最小元的定义：设，对，都有 成立，则称 为 的最小元。,极小元的定义：设，对于，若，则 成立，则称 为 的极小元。,27,分割超平面(separating hyperplane),定理：设 和 为两不相交凸集，则存在超平面将 和 分离。即：,28,支撑超平面(supporting hyperplane),定义：设集合，为 边界上的点。若存在，满足对任意，都有 成立，则称超平面 为集合 在点 处的支撑超平面。,定理：凸集边界上任意一点均存在支撑超平面。定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。,29,对偶锥(dual cone),对偶锥的定义：设 为锥

6、，则集合 称为对偶锥。,对偶锥的性质：,真锥的对偶锥仍然是真锥！,30,对偶广义不等式,广义不等式与对偶等价性质,最小元的对偶特性：,31,对偶广义不等式,极小元的对偶特性,反过来不一定成立！,32,作业,P60 2.8P60 2.10P60 2.14P62 2.16P62 2.18P64 2.30P64 2.31P64 2.33,33,凸优化理论与应用,第二章 凸函数,34,凸函数的定义,1.定义域 为凸集；,2.，有,凸函数的定义：函数，满足,凸函数的扩展定义：若 为凸函数，则可定义其扩展函数 为,凸函数的扩展函数也是凸函数！,35,凸函数的一阶微分条件,若函数 的定义域 为开集，且函数

7、一阶可微，则函数 为凸函数当且仅当 为凸集，且对,36,凸函数的二阶微分条件,若函数 的定义域 为开集，且函数 二阶可微，则函数 为凸函数当且仅当 为凸集，且对，其Hessian矩阵,37,凸函数的例,幂函数,负对数函数,负熵函数,范数函数,指数函数,38,凸函数的例,39,下水平集(sublevel set),定理：凸函数的任一下水平集均为凸集。,任一下水平集均为凸集的函数不一定为凸函数。,40,函数上半图(epigraph),定理：函数 为凸函数当且仅当 的上半图为凸集。,41,Jensen不等式,为凸函数，则有：,Jensen不等式的另外形式：,42,保持函数凸性的算子,凸函数的逐点最大

8、值,凸函数与仿射变换的复合,凸函数的非负加权和,43,保持函数凸性的算子,复合运算,最小值算子,凸函数的透视算子,44,共轭函数(conjugate function),定义：设函数，其共轭函数，定义为,共轭函数的例,共轭函数具有凸性！,45,共轭函数的性质,Fenchels inequality,性质：若 为凸函数，且 的上半图是闭集，则有,46,准凸函数(quasiconvex function),准凸函数的例,47,准凸函数的判定定理,定理：函数 为准凸函数，当且仅当 为凸集，且对，有,定理：若函数 一阶可微，则 为准凸函数，当且仅当 为凸集，且对，有,48,最小值函数,非负权值函数的最

9、大值函数,保持准凸性的算子,复合函数,49,准凸函数的凸函数族表示,若 为准凸函数，根据 的任意 下水平集，我们可以构造一个凸函数族，使得,性质：若 为准凸函数 的凸函数族表示，对每一个，若，则有,50,对数凸函数,对数凸函数的例,51,对数凸函数和凹函数的性质,性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。,定理：函数 二阶可微，则 为对数凸函数当且仅当,性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。,推论：函数 对每一个 在 上对数凸，则函数 也是对数凸函数。,52,对数凸函数和凹函数的性质,定理：函数 为对数凹函数，则函数 是对数凹函数。,53,广义不等式下

10、的凸性,广义单调性的定义：设 为真锥，函数 称为 单调增，若函数 满足：,定理(对偶等价)：函数 为 凸函数，当且仅当对所有，为凸函数。,54,作业(1),P116 3.16P116 3.21,55,作业(2),P121 3.41P122 3.49(1)(2),56,凸优化理论与应用,第三章 凸优化,57,优化问题的基本形式,优化问题的基本描述：,优化变量,不等式约束,等式约束,无约束优化,58,优化问题的基本形式,最优化值,最优化解,优化问题的域,可行点(解)(feasible)满足约束条件,可行域(可解集)所有可行点的集合,59,局部最优问题,局部最优问题,60,优化问题的等价形式(1),

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

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

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

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

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

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

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

18、opy maximization,原始问题：,共轭函数：,对偶函数：,105,Minimum volume covering ellipsoid,原始问题：,对偶函数：,共轭函数：,106,拉格朗日对偶问题,拉格朗日对偶问题的描述：,对偶可行域,最优值,最优解,107,LP问题的对偶问题,标准LP问题,对偶函数,对偶问题,等价描述,108,弱对偶性,定理（弱对偶性）：设原始问题的最优值为，对偶问题的最优值为，则 成立。,optimal duality gap,可以利用对偶问题找到原始问题最优解的下界。,109,强对偶性,强对偶性并不是总是成立的。,定义（强对偶性）：设原始问题的最优值为，对偶问

19、题的最优值为。若 成立，则称原始问题和对偶问题之间具有强对偶性。,凸优化问题通常（但并不总是）具有强对偶性。,110,强对偶性,存在，满足,弱化的Slater条件：若不等式约束条件的前 个为线性不等式约束条件，则Slater条件可以弱化为：,111,Least-squares solution of linear equations,原问题：,对偶问题：,具有强对偶性,112,Lagrange dual of QCQP,QCQP：,拉格朗日函数：,对偶函数：,113,Lagrange dual of QCQP,对偶问题：,Slater条件：存在，满足,114,Entropy maximizat

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

21、优化问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则,即,120,KKT优化条件,设优化问题中，函数 可微。设 为原始优化问题的最优解，为对偶问题的最优解，且两者具有强对偶性，则 满足如下条件：,KKT条件为必要条件！,121,凸优化问题的KKT条件,122,例,原始凸优化问题,KKT条件,123,例,其中,解得,124,凸优化问题的对偶求解,125,扰动问题,扰动问题：,当 时即为原始问题。,若 为正，则第 个不等式约束被放宽；若 为负，则第 个不等式约束被收紧。,记 为扰动问题的最优解。若扰动问题无最优解，则记,126,灵敏度分析,设对偶问题存在最优解，且与原始问题具有强对偶性，若

22、非干扰问题的最优对偶解为，则有,若 在 处可微，则,127,定义（弱选择性）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。,选择定理,对偶不等式组,设原始问题的约束条件：,对偶问题,原始问题的约束条件与对偶不等式组具有弱选择性。,128,选择定理,对偶不等式组,设原始问题的严格不等式约束条件：,原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。,129,定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。,选择定理,对偶不等式组,设原始问题为凸优化问题，其严格不等式约束条件为：,若存在，满足，则上述两不等式约束系统具有强选择性。

23、,130,选择定理,对偶不等式组,设原始问题为凸优化问题，其不等式约束条件为：,131,罚函数的例,范数：,死区线性罚函数：,对数门限罚函数,132,鲁棒的罚函数,若 大到一定程度时，罚函数为 的线性函数，则称该罚函数为鲁棒的罚函数。,Huber罚函数,133,最小范数问题,问题描述：,其中 为方程组 的解。,可以消去等式约束将其转换为范数逼近问题：,134,最小范数问题,最小平方范数问题：范数，最优解满足：,最小罚问题：,绝对值和最小问题：范数，原问题可转换为LP问题：,135,正则逼近,二元矢量优化问题描述：,正则化问题：,最优解描述了两分量的一条折中曲线。,136,正则逼近,Tikhon

24、ov正则化问题：,为二次优化问题：,最优解的形式：,137,正则逼近,Tikhonov光滑正则化问题：,为二阶差分算子：,138,信号复原,已知加噪信号：,信号复原问题的描述：,函数 为正则函数或光滑函数。,139,信号复原,140,信号复原,141,信号复原,142,鲁棒逼近,问题描述：,随机鲁棒逼近：为随机变量，逼近问题转换为最小化期望,例：,随机鲁棒逼近为：,转换为：,143,随机鲁棒逼近,为随机变量：,最小平方随机鲁棒逼近为：,转换为：,其中,144,最坏情况鲁棒逼近,考虑，最坏情况鲁棒逼近为：,例：,随机鲁棒逼近为：,转换为：,145,凸优化理论与应用,第6章 统计估计,146,概率

25、分布的参数估计,随机变量的概率密度为，其中 为概率分布的参数，且参数未知。参数估计的目标就是通过一些已知样本估计获得参数的最优近似值。,问题描述,为样本观测值；,为对数似然函数；,若似然函数为凹函数，则优化问题为凸优化问题。,147,具有独立同分布噪声的线性测量,线性测量模型：,为观测值或测量值；,为未知参数向量；,独立同分布噪声，其概率密度为。,似然函数为,最大似然估计问题为：,148,例,高斯白噪声,对数似然函数：,区间 上均匀分布的噪声：,对数似然函数：,149,逻辑回归,随机变量 的概率分布为：,为参数；,为可观测的解释变量；为观察值。,对数似然函数：,150,假定测验,随机变量，有

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

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

28、 在 上具有强凸性，则可以证明存在，满足,164,强凸性,对于，矩阵 的特征值从大到小依次为。则有：,定义：矩阵 的条件数为最大特征值与最小特征值之比，即。,条件数的上界：,165,下降法,对于凸函数，当 满足 时，存在某个，使得。,166,下降法,下降法的一般步骤：,给出初始点；,167,步长因子搜索,精确一维搜索：,168,步长因子搜索,169,梯度下降法,算法简单，但收敛速度较慢。,下降方向：,终止条件：,170,收敛性分析,若 采用精确一维搜索，则，收敛速度因子：,若 采用回溯一维搜索，收敛速度因子：,条件数越大，收敛速度越小。,171,例,当 时，算法收敛速度很慢。,初始解为，采用精

29、确一维搜索；,迭代：,172,例,步长因子采用回溯一维搜索。,173,最速下降法,归一化最速下降方向：,非归一化最速下降方向,欧式范数：,二次范数：,范数：,174,最速下降法,175,收敛性分析,范数界：,收敛速度因子：,176,牛顿法,设函数 二阶可微，则在 附近，的泰勒展式为：,泰勒展开可作为 在 附近的近似；,下降方向：,为二次范数 上的最速下降方向。,177,牛顿法,178,牛顿减量,令,为 在 处的牛顿减量。,牛顿减量的性质1：,性质2：,牛顿减量可作为迭代求解的误差估计。,性质3：牛顿减量具有仿射不变性。,179,牛顿方法,初始化：给定初始解 以及,LOOP：,计算：,若 则终止

30、退出；,一维线性搜索：计算步长因子；,迭代：,180,收敛性分析,定理：假设 二阶连续可微，具有强凸性，即存在，满足：,则存在，,且海森矩阵满足Lipschitz条件，即存在，满足：,若，则；,若，则，且,181,收敛性分析,定理：假设 二阶连续可微，具有强凸性，即存在，满足：,则存在，对于，有,且海森矩阵满足Lipschitz条件，即存在，满足：,182,例,183,凸优化理论与应用,第8章 等式约束优化,184,等式约束优化问题,问题描述：,为凸函数，且二次连续可微，且,假设最优值 存在，则 为最优解当且仅当存在，满足（KKT条件）：,185,例,KKT系统：,二次优化：,KKT系统可解，

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

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

33、化：给定初始解 及，以及,令；,While,196,其中，且满足。,KKT系统的求解,1.分解；,2.若 非奇异，则可消元：,3.若 奇异，则KKT系统可改写为：,KKT系统：,197,凸优化理论与应用,第9章 内点法,198,则优化问题具有强对偶性，其对偶问题亦可解。,假设存在，满足严格不等式条件,不等式约束优化问题,问题描述：,为凸函数，且二次连续可微，且,假设最优值 存在；,199,不具备良好的连续可微性，考虑用对数阀函数来近似替代。,不等式约束的消去,示性函数消去不等式约束：,200,令,对数阀函数,对于，是 的光滑逼近。且当 时，有,带示性函数的优化问题可近似为：,201,对数阀函数

34、二阶连续可微，导数为：,对数阀函数,对数阀函数 是凸函数,202,中心线,对数阀近似问题的等价问题：,最优解为，则最优解集 称为优化问题的中心线。,203,中心线的对偶点,设，则存在 满足KKT条件：,为对偶问题的可行解。,令,则 是拉格朗日函数 的最小值解。,204,中心线的对偶点,设 为原始问题的最优值，则有：,因此，当 时，有。为原始问题的 次优解。,205,更新：,阀方法,初始化：给定严格可行解，及,LOOP：,中心步骤：以 为初始点求解优化问题，,迭代：,终止条件：若，则终止退出。,206,收敛性分析,外层循环迭代次数：,中心步骤实质为一个无约束或等式约束优化问题，其收敛性分析与相应

35、优化问题的收敛性分析结果一致。,207,例：,LP问题：,初始值：,208,当 时，原始问题不可解；,当 时，无法准确确定。,第一阶段方法,对于不等式约束的优化问题，如何寻找严格可行解或验证不可解？,求解优化问题：,该问题最优解存在，假设最优值为,当 时，存在严格可行解；,209,第一阶段方法,优化目标为逐项之和：,对于固定的，,210,寻找严格可行解的方法,牛顿法求解优化问题：,迭代终止条件：当前解，即终止迭代，严格可行解为。,211,凸优化理论与应用,复习,212,凸集,凸集与凸包的概念；几种常见的凸集多面体、单纯形、范数球、凸锥、真锥、范数锥、半正定锥等；保持凸集的运算集合交运算、仿射变

36、换、透视函数、线性分式函数广义不等式的概念支撑超平面、分割超平面的概念,213,凸函数,凸函数的概念及判定；常见凸函数；Jessen不等式；保持函数凸性的算子；共轭函数的概念、常见函数的共轭函数；向量凸函数（广义不等式下的凸性）,214,优化问题,优化问题的基本描述、等价形式；凸优化问题的基本描述、等价形式；常见凸优化问题。,215,对偶问题,优化问题的拉格朗日函数及对偶函数的概念和性质；一些常见问题的对偶函数；对偶函数与共轭函数的关系；对偶问题的描述；强对偶性的概念及Slater条件；KKT条件。,216,常见应用问题,逼近问题的几种基本描述；统计估计问题的基本描述。,217,常用算法,无约束问题常用算法：下降法最速下降牛顿法等式约束问题的常用算法等式约束条件的消去牛顿法内点法,