凸优化 ¶

Acknowledgement¶

Dimitri P. Bertsekas

Nonlinear Programming 最优化、建模、算法和理论 - 北大

引论 ¶

优化算法很多时候都要利用数学上的结构，而凸优化就是利用了凸集、凸函数等结构，来简化优化问题的求解。

只要能建立成凸优化问题，就可以利用现成的工具包进行求解

• cvx toolbox 在多项式时间复杂度中，找到全局最优解

可以在 \(O(n^{3.5})\) 左右时间复杂度中，找到全局最优解

大纲 ¶

无约束优化问题 ：直接求导、最速下降法、共轭梯度法、牛顿法等；

等式约束优化问题：拉格朗日 (Lagrange) 乘数法；

不等式约束优化问题 ：KKT 条件。

思路 ¶

松弛 ¶

逼近 ¶

用一个接近原始目标的简化目标函数代替原目标函数

下降法 ¶

替代函数 ¶

• BSUM
• ineaxt
• ADMM

EM 算法

收敛性和复杂度分析 ¶

一阶方法：只利用目标函数的一阶导数信息 最好使用