最優化

最優化，是應用數學的一個分支。主要研究在特定情況下最大化或最小化某一特定函數或變量。

數學表述

最優化主要研究以下形式的問題：

給定一個函數$f:A\to \mathbb {R}$，尋找一個元素$\mathbf {x} ^{0}\in A$使得對於所有$A$中的$\mathbf {x}$，$f(\mathbf {x} ^{0})\leq f(\mathbf {x} )$（最小化）；或者$f(\mathbf {x} ^{0})\geq f(\mathbf {x} )$（最大化）。

這裡$A$一般為歐幾里得空間$\mathbb {R} ^{n}$中的子集，通常由一個$A$必須滿足的約束等式或者不等式來規定。 $A$的元素被稱為是可行解。函數$f$被稱為目標函數，或者代價函數。一個最小化（或者最大化）目標函數的可行解被稱為最優解。

這類問題有時也稱為「數學規劃」（譬如，線性規劃）。許多現實和理論問題都可以利用這樣的一般性框架來建模，成為一個最優化問題。

一般情況下，會存在若干個局部的極小值或者極大值。局部極小值$x^{*}$定義為對於一些$\delta >0$，以及所有的$x$ 滿足

$\|\mathbf {x} -\mathbf {x} ^{*}\|\leq \delta$;

公式

$f(\mathbf {x} ^{*})\leq f(\mathbf {x} )$

成立。這就是說，在$\mathbf {x} ^{*}$周圍的一些閉球上，所有的函數值都大於或者等於在該點的函數值。一般的，求局部極小值是容易的，但是要確保其為全域性的最小值，則需要一些附加性的條件，例如，該函數必須是凸函數。

根據以下的結論，最大化和最小化問題可以相互變換。一般情況下，最優化問題就可以只討論最小化即可。

$f(\mathbf {x} _{0})\geq f(\mathbf {x} )\Leftrightarrow -f(\mathbf {x} _{0})\leq -f(\mathbf {x} ),$

符號表示

最優化問題通常有一些較特別的符號標示方法。例如：

$\min _{x\in \mathbb {R} }\;x^{2}+1$

這是要求表達式$x^{2}+1$的最小值，這裡x取值為全體實數，$\mathbb {R}$。這個問題的最小值應該是$1$，當$x=0$。

$\max _{x\in \mathbb {R} }\;2x$

這是要求表達式$2x$的最大值，同樣地，$x$在全體實數上取值。對於這個問題，由於該表達式不是有上界的，因此不存在最大值，因此，答案應該是無限大，或者是不可定義的。

${\underset {x\in [-\infty ;-1]}{\operatorname {arg\,min} }}\;x^{2}+1\,$

這是求使表達式x²+1 達到最小值時x的值。在這裡x被限定在區間[-∞ ,-1]之間，所以上式的值是-1。

主要分支

• 線性規劃：當目標函數f是線性函數而且集合A是由線性等式函數和線性不等式函數來確定的， 我們稱這一類問題為線性規劃
• 整數規劃：當線性規劃問題的部分或所有的變量局限於整數值時， 我們稱這一類問題為整數規劃問題
• 二次規劃：目標函數是二次函數，而且集合A必須是由線性等式函數和線性不等式函數來確定的。
• 分數規劃：研究的是如何優化兩個非線性函數的比例。
• 非線性規劃：研究的是目標函數或是限制函數中含有非線性函數的問題。
• 隨機規劃：研究的是某些變量是隨機變量的問題。
• 動態規劃：研究的是最優策略基於將問題分解成若干個較小的子問題的優化問題。
• 組合最優化：研究的是可行解是離散或是可轉化為離散的問題。
• 無限維最優化：研究的是可行解的集合是無限維空間的子集的問題，一個無限維空間的例子是函數空間。

算法

對於無約束的優化問題， 如果函式是二次可微的話，可以通過找到目標函數梯度為0（也就是拐點）的那些點來解決此優化問題。我們需要用黑塞矩陣來確定此點的類型。如果黑塞矩陣是正定的話，該點是一個局部最小解， 如果是負定的話，該點是一個局部最大解，如果黑塞矩陣是不定的話，該點是某種鞍點。

要找到那些拐點，我們可以通過猜測一個初始點，然後用比如以下的迭代的方法來找到。

• 梯度下降法
• 牛頓法
• 共軛梯度法
• 線性搜索
• 置信域方法

如果目標函數在我們所關心的區域中是凸函數的話，那麼任何局部最小解也是全局最優解。現在已經有穩定，快速的數值計算方法來求二次可微地凸函數的最小值。

有約束條件的約束問題常常可以通過拉格朗日乘數轉化為非約束問題。

其他一些流行的方法有：

• 遺傳算法
• 神經網絡
• 微粒群算法
• 模擬退火
• 支持向量機
• 蟻群算法
• 類免疫演算法
• 演化策略
• 差分進化算法

與人工智能的關係

現代的計算機科學技術和人工智能科學把最優化作為一個重要的領域來研究。我們也可以認為人工智能的一些算法，就是模擬了人類尋求實際問題最優解的過程。例如，利用人工智能方法設計軟件，配合外部的電子設備例如攝像頭識別人臉；利用數據挖掘和神經網絡算法來尋找投資的最佳時機等。

參考文獻

• Stephen Boyd and Lieven Vandenberghe (2004). Convex Optimization （頁面存檔備份，存於網際網路檔案館），Cambridge University Press. ISBN 0-521-83378-7.

參閲

• 最優化問題
• 最大值的參數
• 博弈論
• 運籌學
• 模糊邏輯
• 隨機最優化
• 變分不等式
• 單體算法
• 內點法
• 對偶性 (最佳化)

外部連結

• NEOS Guide
• Online curve and surface fitting
• Xpress-MP - Optimization software free to students （頁面存檔備份，存於網際網路檔案館）