凸优化理论与应用凸优化PPT课件.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 令求解可行解问题 若可解 则令 否则令若 则结束 否则gotoLOOP 可编辑 25 线性规划 linearprogram LP LP问题的一般描述 可编辑 26 LP问题的几种类型 标准LP问题 不等式形式LP问题 可编辑 27 标准LP问题的转换 可编辑 28 LP问题的例 Chebyshevcenterofapolyhedron Piecewise linearminimization Linear fractionalprogramming 可编辑 29 Chebyshevcenterofapolyhedron 多面体 Chebyshevcenter 到多面体边界距离最大的内点 最深的点 问题描述 LP形式 可编辑 30 Piecewise linearminimization 问题描述 上半图形式 LP形式 可编辑 31 Linear fractionalprogramming 问题描述 LP形式 可编辑 32 二次规划 quadraticprogram QP QP问题的基本描述 可编辑 33 二次约束二次规划 quadraticallyconstrainedquadraticprogram QCQP 可编辑 34 QP问题的例 Least squaresandregression Distancebetweenpolyhedra Markowitzportfoliooptimization LPwithRandomCost 可编辑 35 Least squaresandregression 问题描述 可编辑 36 Distancebetweenpolyhedra 问题描述 QP形式 LPwithRandomCost 其中是随机变量 其期望为 协方差矩阵为目标函数的期望和方差 可编辑 37 LP问题 LPwithRandomCost 风险敏感性目标函数LPwithRandomCost 可编辑 38 Markowitzportfoliooptimization 可编辑 39 其中 为某段时期初持有的第种证券价值 为该段时间内第种证券的收益率 为该段时间内收益率的期望 为收益率的协方差矩阵 问题描述 可编辑 40 Second orderconeprogram SOCP SOCP问题的基本描述 二次锥约束条件 可编辑 41 Robustlinearprogramming 例 为确定的常数 为变量 其范围满足 SOCP形式 LPwithrandomconstraints LP问题中 假定为独立分布的高斯随机向量 其期望和协方差矩阵分别为和 假设每个约束条件以超过一定的概率成立 即随机约束的LP问题 可编辑 42 LPwithrandomconstraints 记 则为高斯分布的随机变量 其期望和方差分别为原问题可转化为SOCP问题 可编辑 43 可编辑 44 几何规划 Geometricprogramming 单项式与多项式 几何规划的基本描述 可编辑 45 几何规划的凸形式转换 令 几何规划的凸形式 可编辑 46 广义不等式约束 广义不等式约束的优化问题 SOCP的描述 多目标优化问题 矢量优化 可编辑 47 问题基本描述 其中 最优解与Pareto最优解 可能值区域最优解使得为上的最小值 Pareto最优解使得为上的极小值 可编辑 48 正则化最小二乘问题 问题描述 可编辑 49 Pareto最优解求解 给定 原问