凸优化

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

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

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

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

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

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

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

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

1. ^ Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude. Convex analysis and minimization algorithms: Fundamentals. 1996: 291 [2013-09-25]. （原始内容存档于2013-09-29）. 
2. ^ Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. 2001: 335–336 [2013-09-25]. （原始内容存档于2013-09-29）. 
3. ^ Boyd/Vandenberghe, p. 7
4. ^ For methods for convex minimization, see the volumes by Hiriart-Urruty and Lemaréchal (bundle) and the textbooks by Ruszczyński and Boyd and Vandenberghe (interior point).

• 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.