凸优化理论与应用凸优化.ppt

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