凸優化

维基百科,自由的百科全书
跳到导航 跳到搜索

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

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

定義[编辑]

為一凸集,且為一凸函數。凸最佳化就是要找出一點,使得每一滿足[1][2]在最佳化理論中,稱為可行域稱為目標函數稱為全局最優值,或全域最佳解[3]

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

其中 為凸函數。[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.