查看“︁凸優化”︁的源代码

{{More footnotes|time=2013-09-25}}

{{noteTA
|G1=IT
|G2=Math
|1=zh-tw:最佳;zh-cn:最优;
|2=zh-tw:凸最佳;zh-cn:凸最优;
}}

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

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

== 定義 ==
令<math>\mathcal{X} \subset \mathbb{R}^n</math>為一凸集，且<math>f:\mathcal{X}\to \mathbb{R}</math>為一凸函數。'''凸最佳化'''就是要找出一點<math>x^\ast \in \mathcal{X}</math>，使得每一<math>x \in \mathcal{X}</math>滿足<math>f(x^\ast)\le f(x)</math>。<ref>{{cite book |last1=Hiriart-Urruty |first1=Jean-Baptiste |last2=Lemaréchal |first2=Claude |title=Convex analysis and minimization algorithms: Fundamentals |page=291 |year=1996 |url=http://books.google.de/books?id=Gdl4Jc3RVjcC&printsec=frontcover&dq=lemarechal+convex+analysis+and+minimization&hl=de&sa=X&ei=E602T4GXGMzQsgaPtJ2VDA&ved=0CDUQ6AEwAA#v=onepage&q=convex%20minimization&f=false |access-date=2013-09-25 |archive-date=2013-09-29 |archive-url=https://web.archive.org/web/20130929064215/http://books.google.de/books?id=Gdl4Jc3RVjcC&printsec=frontcover&dq=lemarechal+convex+analysis+and+minimization&hl=de&sa=X&ei=E602T4GXGMzQsgaPtJ2VDA&ved=0CDUQ6AEwAA#v=onepage&q=convex%20minimization&f=false |dead-url=no }}</ref><ref>{{cite book |last1=Ben-Tal |first1=Aharon |last2=Nemirovskiĭ |first2=Arkadiĭ Semenovich |title=Lectures on modern convex optimization: analysis, algorithms, and engineering applications |pages=335–336 |year=2001 |url=http://books.google.de/books?id=M3MqpEJ3jzQC&printsec=frontcover&dq=Lectures+on+Modern+Convex+Optimization:+Analysis,+Algorithms,&hl=de&sa=X&ei=26c2T6G7HYrIswac0d2uDA&ved=0CDIQ6AEwAA#v=onepage&q=convex%20programming&f=false |access-date=2013-09-25 |archive-date=2013-09-29 |archive-url=https://web.archive.org/web/20130929064223/http://books.google.de/books?id=M3MqpEJ3jzQC&printsec=frontcover&dq=Lectures+on+Modern+Convex+Optimization:+Analysis,+Algorithms,&hl=de&sa=X&ei=26c2T6G7HYrIswac0d2uDA&ved=0CDIQ6AEwAA#v=onepage&q=convex%20programming&f=false |dead-url=no }}</ref>在最佳化理論中，<math>\mathcal{X}</math>稱為'''可行域'''，<math>f</math>稱為'''目標函數'''，<math>x^\ast</math>稱為'''全局最優值'''，或'''全域最佳解'''。

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

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

其中 
<math>f, g_1 \ldots g_m : \mathbb{R}^n \rightarrow \mathbb{R}</math> 
為凸函數。<ref>Boyd/Vandenberghe, p. 7</ref>

== 舉例 ==
以下問題都是凸最佳化問題，或可以通過改變變量而轉化為凸最佳化問題：<ref>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).
</ref>

* [[最小二乘]]
* [[線性規劃]]
* 線性約束的[[二次規劃]]
* [[半正定规划]]
* [[二阶锥规划]]

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

* 捆集法
* [[次梯度法]]
* [[內點法]]

== 腳註 ==
<references/>

== 參考資料 ==
* {{cite book|title=Convex Optimization|first1=Stephen P.|last1=Boyd|first2=Lieven|last2=Vandenberghe|year=2004|publisher=Cambridge University Press|isbn=978-0-521-83378-3|url=http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|format=pdf|accessdate=October 15, 2011|archive-date=2017-07-13|archive-url=https://web.archive.org/web/20170713015116/http://stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|dead-url=no}}

* {{cite book
  | last = Ruszczyński
  | first = Andrzej
  | title = Nonlinear Optimization
  | publisher = Princeton University Press
  | year = 2006
}}

[[Category:數學最佳化]]
[[Category:凸分析]]