凸优化

凸函数最优化，或叫做凸最优化，凸最小化，是数学最优化的一个子领域，研究定义于凸集中的凸函数最小化的问题。凸最优化在某种意义上说较一般情形的数学优化问题要简单，譬如在凸最优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在优化问题中得以应用，如次导数等。

凸最优化应用于很多学科领域，诸如自动控制系统，信号处理，通信和网络，电子电路设计，数据分析和建模，统计学（优化设计），以及金融。在近来运算能力提高和优化理论发展的背景下，一般的凸最优化已经接近简单的线性规划一样直捷易行。许多优化问题都可以转化成凸最优化（凸最小化）问题。

定义

令${\mathcal {X}}\subset \mathbb {R} ^{n}$为一凸集，且$f:{\mathcal {X}}\to \mathbb {R}$为一凸函数。凸最优化就是要找出一点$x^{\ast }\in {\mathcal {X}}$，使得每一$x\in {\mathcal {X}}$满足$f(x^{\ast })\leq f(x)$。在优化理论中，${\mathcal {X}}$称为可行域，$f$称为目标函数，$x^{\ast }$称为全局最优值，或全局最优解。

或者可以表示为下面的标准型：

${\begin{aligned}&\operatorname {min} &&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}$

其中 $f,g_{1}\ldots g_{m}:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ 为凸函数。

举例

以下问题都是凸最优化问题，或可以通过改变变量而转化为凸最优化问题：

• 最小二乘
• 线性规划
• 线性约束的二次规划
• 半正定规划
• 二阶锥规划

方法

凸最优化（凸最小化）问题可以用以下几种方法求解：

• 捆集法
• 次梯度法
• 内点法

参考资料

• Boyd, Stephen P.; Vandenberghe, Lieven. Convex Optimization (pdf). Cambridge University Press. 2004 [October 15, 2011]. ISBN 978-0-521-83378-3. （原始内容存档 (PDF)于2017-07-13）. 

• Ruszczyński, Andrzej. Nonlinear Optimization. Princeton University Press. 2006.