凸优化复习提纲.pdfVIP

考试安排 6月12日（星期四）下午2:30-4:30，闭卷考试 3212：SC********、BA********、SA10******、 SA11******、SA12****** 3213：SA13001***、SA13006***、SA13008*** 3214：SA13010***、SA13011***、SA13023***、 SA13157***、SA13214***、SA13231***、 SA13232*** 1 课程总结 讨论一类容易的优化问题：凸优化问题 分析问题 哪些是凸优化问题？（凸集、凸函数） 凸优化问题有哪些性质？（对偶理论） 讨论几种简单的优化算法：无约束优化、有约束优化 2 凸集 定义：集合内任意点的凸组合仍然在集合内 保持集合凸性的操作 交集 仿射函数 透视函数 线性分数函数 （仿射+透视） 3 凸函数 定义：凸组合的函数值小于等于函数值的凸组合 高维情况下的等价定义 一阶可微情况下的等价定义 二阶可微情况下的等价定义 注意：凸函数的域一定要为凸集！ 保持函数凸性的操作 非负加权和、仿射映射、极大值函数 函数的组合 函数的透视 4 凸集遇上凸函数 凸函数的次水平集必然是凸集 次水平集为凸集的函数是拟凸函数 凸优化问题 目标函数为凸函数，可行解集为凸集的极小化问题 目标函数为凸函数，不等式约束函数为凸函数，等式约 束函数为仿射函数的极小化问题 基本概念：域、可行解集、最优解集、等等 典型问题：线性规划、二次规划、二次约束二次规划 5 对偶 拉格朗日函数、对偶函数、对偶问题 对偶间隙何时为零 （强对偶何时成立） 当拉格朗日函数存在鞍点时，强对偶成立，且鞍点是原对 偶最优解 KKT条件 （五条） 6 优化算法 新解=旧解+步长×方向 步长选择策略：固定步长、递减步长、Armijo Rule 无约束优化 （求解KKT条件） 一阶方法 （负梯度方向），次梯度方法 二阶方法 （牛顿方向、拟牛顿方向） 有约束优化 （求解KKT条件） 约束满足的牛顿法 原对偶方法：（增广）拉格朗日法、交替方向乘子法 7