凸优化理论与应用凸优化课件.ppt
可编辑,1,凸优化理论与应用,第三章 凸优化,可编辑,2,优化问题的基本形式,优化问题的基本描述：,优化变量,不等式约束,等式约束,无约束优化,可编辑,3,优化问题的基本形式,最优化值,最优化解,优化问题的域,可行点(解) (feasible) 且满足约束条件,可行域(可解集) 所有可行点的集合,可编辑,4,局部最优解,局部最优问题,若 为局部最优问题的最优解，则它为原最优问题的局部最优解。,可编辑,5,优化问题的等价形式(1),可编辑,6,优化问题的等价形式(2),可编辑,7,优化问题的等价形式(3),定理：设 为严格单调增函数； 满足 当且仅当 ； 满足 当且仅当 。则原优化问题与以下优化问题等价,可编辑,8,优化问题的等价形式(4),定理：原优化问题与以下优化问题等价,称为松弛变量,可编辑,9,优化问题的等价形式(5),定理：设 满足等式 成立，当且仅当 。则原优化问题与以下优化问题等价,可编辑,10,可分离变量优化问题,可编辑,11,优化问题的上半图形式,可编辑,12,凸优化问题的基本形式,凸优化问题的基本描述：,为仿射函数,为凸函数,若 为准凸函数，则优化问题称为准凸优化问题。,性质：凸优化问题的可行域是凸集。,可编辑,13,抽象凸优化问题,例：,等价于凸优化问题,可编辑,14,凸优化问题的局部最优解,定理：凸优化问题的局部最优解均是全局最优解。,可编辑,15,凸优化问题最优解,定理：设 为凸优化问题的可行域， 可微。则 为最优解当且仅当 成立。,可编辑,16,凸优化问题最优解,定理：无约束凸优化问题中，若 可微。则 为最优解当且仅当 成立。,例：无约束二次优化问题,可知,可编辑,17,凸优化问题的最优解,可编辑,18,凸优化问题的最优解,可编辑,19,凸优化问题的等价形式,可编辑,20,凸优化问题的等价形式,等价于,定理：设凸优化问题,可编辑,21,准凸优化问题,注：准凸优化问题的局部最优解不一定是全局最优解。,准凸优化问题-最优解的充分条件,可编辑,22,定理：设 为准凸优化问题的可行域， 可微。若有则 为准凸优化问题的最优解。,可编辑,23,准凸优化问题的上半图形式,设 为准凸函数 的凸函数族表示，即,则准凸优化问题的可行解问题为,设 为准凸优化问题的最优解，若上述问题可解，则 。否则 。,可编辑,24,准凸优化问题二分法求解,给定一个足够小的 和足够大的 ，使得区间 能包含最优解 。给定,LOOP：令求解可行解问题；若可解，则令 ，否则令若 ，则结束，否则goto LOOP。,可编辑,25,线性规划(linear program,LP),LP问题的一般描述,可编辑,26,LP问题的几种类型,标准LP问题,不等式形式LP问题,可编辑,27,标准LP问题的转换,可编辑,28,LP问题的例,Chebyshev center of a polyhedron,Piecewise-linear minimization,Linear-fractional programming,可编辑,29,Chebyshev center of a polyhedron,多面体,Chebyshev center：到多面体边界距离最大的内点（最深的点）,问题描述,LP形式,可编辑,30,Piecewise-linear minimization,问题描述,上半图形式,LP形式,可编辑,31,Linear-fractional programming,问题描述,LP形式,可编辑,32,二次规划(quadratic program,QP),QP问题的基本描述,可编辑,33,二次约束二次规划,quadratically constrained quadratic program (QCQP),可编辑,34,QP问题的例,Least-squares and regression,Distance between polyhedra,Markowitz portfolio optimization,LP with Random Cost,可编辑,35,Least-squares and regression,问题描述,可编辑,36,Distance between polyhedra,问题描述,QP形式,LP with Random Cost,其中 是随机变量，其期望为 ，协方差矩阵为目标函数的期望和方差,可编辑,37,LP问题,LP with Random Cost,风险敏感性目标函数LP with Random Cost,可编辑,38,Markowitz portfolio optimization,可编辑,39,其中： 为某段时期初持有的第 种证券价值， 为该段时间内第 种证券的收益率。 为该段时间内收益率的期望， 为收益率的协方差矩阵。,问题描述：,可编辑,40,Second-order cone program, SOCP,SOCP问题的基本描述,二次锥约束条件,可编辑,41,Robust linear programming,例： 为确定的常数， 为变量，其范围满足,SOCP形式,LP with random constraints,LP问题中，假定 为独立分布的高斯随机向量，其期望和协方差矩阵分别为 和 。假设每个约束条件以超过一定的概率成立，即随机约束的LP问题,可编辑,42,LP with random constraints,记 ，则 为高斯分布的随机变量，其期望和方差分别为原问题可转化为SOCP问题：,可编辑,43,可编辑,44,几何规划(Geometric programming),单项式与多项式,几何规划的基本描述,可编辑,45,几何规划的凸形式转换,令,几何规划的凸形式,可编辑,46,广义不等式约束,广义不等式约束的优化问题,SOCP的描述,多目标优化问题(矢量优化),可编辑,47,问题基本描述：,其中,最优解与Pareto最优解,可能值区域最优解 使得 为 上的最小值。Pareto最优解 使得 为 上的极小值。,可编辑,48,正则化最小二乘问题,问题描述,可编辑,49,Pareto最优解求解,给定 ，原问题标量化为标量优化问题为凸优化问题，其最优解为Pareto最优解。,可编辑,50,注：通过求解凸矢量优化问题的标量化问题，可以获得几乎所有的Pareto最优解。,可编辑,51,作业,P189 4.3P191 4.7P192 4.8P194 4.15P196 4.21,
