凸優化

凸函數最佳化，或叫做凸最佳化，凸最小化，是數學最佳化的一個子領域，研究定義於凸集中的凸函數最小化的問題。凸最佳化在某種意義上說較一般情形的數學最佳化問題要簡單，譬如在凸最佳化中局部最佳值必定是全域最佳值。凸函數的凸性使得凸分析中的有力工具在最佳化問題中得以應用，如次導數等。

凸最佳化應用於很多學科領域，諸如自動控制系統，訊號處理，通訊和網路，電子電路設計，數據分析和建模，統計學（最佳化設計），以及金融。在近來運算能力提高和最佳化理論發展的背景下，一般的凸最佳化已經接近簡單的線性規劃一樣直捷易行。許多最佳化問題都可以轉化成凸最佳化（凸最小化）問題。

定義

令${\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]

• 最小平方
• 線性規劃
• 線性約束的二次規劃
• 半正定規劃
• 二階錐規劃

方法

凸最佳化（凸最小化）問題可以用以下幾種方法求解：

• 捆集法
• 次梯度法
• 內點法