凸優化

维基百科,自由的百科全书
跳转至: 导航搜索

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

凸優化應用於很多學科領域,諸如自動控制系統,信號處理,通訊和網絡,電子電路設計,數據分析和建模,統計學(最優化設計),以及金融。在近來運算能力提高和最優化理論發展的背景下,一般的凸優化已經接近簡單的線性規劃一樣直捷易行。許多最優化問題都可以轉化成凸優化(凸最小化)問題,例如求凹函數 f 最大值的問題就等同於求凸函數 -f 最小值的問題。

定義[编辑]

\mathcal{X} \subset \mathbb{R}^n 為一凸集,且 f:\mathcal{X}\to \mathbb{R} 為一凸函數。凸優化就是要找出一點 x^\ast \in \mathcal{X} ,使得每一 x \in \mathcal{X} 滿足 f(x^\ast)\le f(x)[1] [2]在最佳化理論中, \mathcal{X} 稱為可行域f 稱為目標函數x^\ast 稱為全局最優值,或全域最佳解[3]

或者可以表示為下面的標準型:

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

其中 f, g_1 \ldots g_m : \mathbb{R}^n \rightarrow \mathbb{R} 為凸函數。[4]

舉例[编辑]

以下問題都是凸優化問題,或可以通過改變變量而轉化為凸優化問題:[5]

方法[编辑]

凸優化(凸最小化)問題可以用以下幾種方法求解:

凸最大化[编辑]

通常凸優化的定義要求目標函數 f 在可行域內被最小化,而在某些的線性規劃問題中也會研究最大化。

腳註[编辑]

  1. ^ Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude. Convex analysis and minimization algorithms: Fundamentals. 1996. 291. 
  2. ^ Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. 2001: 335–336. 
  3. ^ 凸優化──凸函數的最小化. 線代啟示錄. 2013-08-28 [2013-09-25]. 
  4. ^ Boyd/Vandenberghe, p. 7
  5. ^ 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).

參考資料[编辑]

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