凸優化

令${\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. . 1996: 291 [2013-09-25]. （原始内容存档于2013-09-29）.
2. Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich. . 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. (pdf). Cambridge University Press. 2004 [October 15, 2011]. ISBN 978-0-521-83378-3. （原始内容存档 (PDF)于2017-07-13）.

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