最優化

最佳化指從一組可選擇的方案中，根據一定標準選擇最佳方案的過程。其間往往要在特殊情況下，對在某個集合上最小化或最大化一個函數的問題進行建模、分析，並通過解析或數值方法求解。一般分為離散優化、連續優化兩個子領域。

最優化在多個領域發揮著重要作用：應用數學（對工業與工程學發展至關重要）、運籌學（電腦科學、數學與經濟學的交叉領域）、分析與數值分析、統計學（用於分布的最大似然估計）、博弈論中的策略研究，以及控制與指令理論等。

在更一般的方法中，優化問題是指通過在允許的集合中有系統地選擇輸入值並計算函數值，來最小化或最大化一個實函數的問題。將優化理論與技術推廣至其他形式，構成了應用數學的一個廣泛領域。更一般地說，優化包括在給定定義域（或輸入）的前提下，找到某目標函數的「最佳可達值」。

許多可用數學模型描述的系統都會經過最優化。結果與預測的質量取決於模型的合理性、所選優化變量的恰當性、演算法的效率，以及數值處理的手段。幾百年來，求解方法的發展一直受到數學界的關注。

## 優化問題

根據變量的類型（連續或離散），優化問題可分為兩類：

- 離散變量的優化問題稱作離散優化，當中的整數、排列或圖之類對象必須屬於可數集。
- 連續變量的優化問題稱作連續優化，當中最優自變量要屬於連續集。這類問題可以包括約束優化與多峰問題。

優化問題可用以下方式表示：

已知：函數$f:\ A\to \mathbb R$從某集合A映射到實數

求：元素$x_0\in A$，使$\forall x\in A,\ f_{x_0}\le f(x)$（「最小化」），或使$x\in A,\ f_{x_0}\ge f(x)$（「最大化」）。

這樣表述後，稱作優化問題或數學規劃問題。很多現實問題與理論問題都可用這個一般框架建模。

由於下式成立：

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

只需解最小化問題。只考慮最大化問題的相反觀點是同理的。

物理學領域，使用這種技術提出的問題可稱「能量最小化」，將函數f值視為所建模系統的能量。機器學習中，總要用損失函數持續評估模型的質量，損失函數取得極小值意味著一組可能的最優參數，同時具有最優（最小）的誤差。

A通常是歐氏空間$\mathbb R^n$的子集，一般要求A的成員需滿足一組約束（等式或不等式）。f的定義域A稱作搜索空間或選擇集，A的元素稱作候選解或可行解。

函數f有多種叫法，常見的有目標函數、判別函數、損失函數、成本函數（最小化）、效率函數、適應度函數（最大化），某些領域還有能量函數、能量泛函等等。使得目標函數取最值（取決於問題）的可行解就是最優解。

數學中，傳統優化問題通常用最小化形式表示。

極值$\mathbf{x}^{\ast}$是局部的，定義為$\exists \delta>0$，滿足一定條件。例如，極小值要滿足

$$\forall\mathbf{x}\in A \; \text{where} \;\left\Vert\mathbf{x}-\mathbf{x}^{\ast}\right\Vert\leq\delta,\, f(\mathbf{x}^{\ast})\le f(\mathbf{x})$$

這就是說，在$\mathbf{x}^*$周圍的一些閉球上，所有的函數值都大於或者等於在該點的函數值。

極小值至少於附近的任何元素一樣好，最小值則至少與每個可行解一樣好。一般來說，除非目標函數是凸函數，否則會存在多個極小值。凸優化問題中，若有位於可行集內（不位於邊緣）的極小值，則它也是最小值；而非凸優化問題可能有多個極小值。

非凸問題所用的大量演算法（包括大多數商業求解器）都無法區分局部最優解與全局最優解，而是將前者視作原問題的實際解。全局優化是應用數學與數值分析的一個分支，主要研究能在有限時間內收斂到非凸問題實際最優解的確定性算法。

## 符號

優化問題常用特殊符號表示，如下：

### 函數最值

$$\min_{x\in\mathbb R}\; \left(x^2 + 1\right)$$

這是求，從實數集$\mathbb{R}$中選擇x時，目標函數$x^2+1$的最小值。此問最小值為1，出現在$x=0$處。

相似地。

$$\max_{x\in\mathbb R}\; 2x$$

是求目標函數$2x$的最大值，其中x是任意實數。由於目標函數無界，所以不存在最大值，答案是「無窮大」或「未定義」。

### 最佳輸入

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

或等價的

$$\underset{x}{\operatorname{arg\,min}} \; x^2 + 1, \; \text{subject to:} \; x\in(-\infty,-1].$$

這是求參數x在區間$(-\infty,\ -1]$時，能使目標函數$x^2+1$取最值的值。此問題的答案是$x=-1$，因為$x=0$不可行，不屬於可行集。

相似地。

$$\underset{x\in[-5,5], \; y\in\mathbb R}{\operatorname{arg\,max}} \; x\cos y,$$

或等價的

$$\underset{x, \; y}{\operatorname{arg\,max}} \; x\cos y, \; \text{subject to:} \; x\in[-5,5], \; y\in\mathbb R,$$

表示使目標函數$x\cos y$取最大值的$\{x,\ y\}$對，且x要滿足約束：位於區間$[-5,\ 5]$內。此問題的答案是$\{5,\ 2k\pi\}$與$\{-5,\ (2k+1)\pi\}$，其中k的範圍是所有整數。

算符$\operatorname{arg\,min},\ \operatorname{arg\,max}$有時也作$\text{argmin},\ \text{argmax}$，分別代表最小值點與最大值點。

## 歷史

### 起源

最優化問題可能由歐幾里得於公元前3世紀在其經典著作《幾何原本》中最早提出。三百年後，亞歷山大的希羅在其著作《光學》中提出了「最短路徑原理」，實例便是我們耳熟能詳的「將軍飲馬問題」。

<image>

### 微分的引入

17世紀，微分的出現推動了真正意義上最優化技術的發展。牛頓先提出了一種迭代法，通過引入導數（源於與萊布尼茨的合作）來尋找函數的局部極值。

18世紀，歐拉與拉格朗日的研究催生了變分法——泛函分析的一個分支，涵蓋了多種優化方法。後者還發明了一種帶約束的優化技術：拉格朗日乘數法。

### 近現代

用於部分優化情形的「線性規劃」（linear programming）是喬治·伯納德·丹齊格提出的，不過其中大部分理論是列昂尼德·坎托羅維奇於1939年提出的。丹齊格在1947年提出單純形法，馮·諾依曼等人也在同時期致力於線性規劃的理論研究（如對偶）。

其他著名的最優化研究者有：

- 理察·貝爾曼
- 德梅萃·博賽卡斯
- Michel Bierlaire
- Stephen P. Boyd
- Roger Fletcher
- Martin Grötschel
- Ronald A. Howard
- 弗瑞茲·約翰
- Narendra Karmarkar
- 威廉·卡魯什
- Leonid Khachiyan
- Bernard Koopman
- 哈羅德·W·庫恩
- 洛瓦茲·拉茲洛
- 大衛·倫伯傑
- 阿爾卡迪·內米羅夫斯基
- 尤里·涅斯捷羅夫
- 列夫·龐特里亞金
- R. Tyrrell Rockafellar
- Naum Z. Shor
- 阿爾伯特·W·塔克

## 主要分支

- 線性規劃：當目標函數f是線性函數而且集合A是由線性等式函數和線性不等式函數來確定的，我們稱這一類問題為線性規劃
- 整數規劃：當線性規劃問題的部分或所有的變量局限於整數值時，我們稱這一類問題為整數規劃問題
- 二次規劃：目標函數是二次函數，而且集合A必須是由線性等式函數和線性不等式函數來確定的。
- 分數規劃：研究的是如何優化兩個非線性函數的比例。
- 非線性規劃：研究的是目標函數或是限制函數中含有非線性函數的問題。
- 隨機規劃：研究的是某些變量是隨機變量的問題。
- 動態規劃：研究的是最優策略基於將問題分解成若干個較小的子問題的優化問題。
- 組合最優化：研究的是可行解是離散或是可轉化為離散的問題。
- 無限維最優化：研究的是可行解的集合是無限維空間的子集的問題，一個無限維空間的例子是函數空間。
- 凸優化研究目標函數為凸函數（最小化）或凹函數（最大化），且約束集為凸集的問題。這可以看成非線性規劃的特例，或凸二次規劃的推廣。
- 線性規劃（LP），是凸規劃的一種，研究目標函數f為線性函數、約束只包含線性等式與不等式的問題。若這種約束集是有界集合，又稱作多面體或多胞形。
- 二階錐規劃（SOCP）是凸規劃的一種，包括某些類型的二次規劃。
- 半正定規劃（SDP）是凸規劃的一個子領域，其中底變量是半正定矩陣，它是線性規劃與凸二次規劃的推廣。
- 錐規劃是凸規劃的一般形式。LP、SOCP、SDP都是其特例。
- 幾何規劃是一種表示不等式約束的正項式、表示等式約束的單項式化為凸規劃的技術。
- 整數規劃研究部分或所有變量取整數值的線性規劃，不屬於凸規劃，往往比常規線性規劃困難很多。
- 二次規劃允許目標函數包含二次項，而可行集須用線性等式與不等式指定。若有特殊形式的二次項，則屬於凸規劃。
- 分式規劃研究兩非線性函數之比的優化。一類凹分式規劃可轉為凸優化問題。
- 非線性規劃研究目標函數和/或約束包含非線性部分的一般情形。可能屬於凸規劃也可能不屬於，規劃是否為凸一般會影響求解難度。
- 隨機規劃研究某些約束或參數取決於隨機變量的問題。
- 穩健優化類似於隨機規劃，試圖捕捉優化問題基礎數據中的隨機性。穩健優化試圖找到在不定集定義的不確定性的所有可能下，都有效的解。
- 組合優化關注可行解集離散，或可簡化為離散情形的問題。
- 隨機優化用於搜索過程中的隨機（噪聲）函數測量或隨機輸入。
- 無窮維優化研究可行解集為無窮維空間（如函數空間）子集的情形。
- 啟發式與元啟發算法對待優化問題（幾乎）不做假設。啟發式算法一般不能保證找到最優解，而可用於找到很多複雜優化問題的近似解。
- 約束滿足研究目標函數f為常數的情形（常見於人工智慧領域，特別是自動推理）。
- 約束編程是一種編程範式，變量間關係表為約束。
- 分離規劃（disjunctive programming）研究必須滿足至少一個約束，而非所有約束的問題。分離規劃尤其適用於調度。
- 空間映射是工程系統建模與優化的概念，利用具有物理意義的代理模型，達到保持模型精度，而減小計算量的效果。

在一些子領域中，這些技術用於動態環境（隨時間變化的決策）中的優化：

- 變分法是指找到實現某目標的最佳方法，如找到邊界為特定曲線，而面積儘可能小的曲面。
- 最優控制是變分法的推廣，引入了控制策略。
- 動態規劃是解隨機優化問題的一種方法，具有隨機、未知的模型參數，其優化策略基於將問題分割為子問題。描述子問題間關係的方程叫做貝爾曼方程。
- 均衡約束數學規劃問題的約束包含變分不等式或互補式。

### 多目標優化

在優化問題中加入多個目標，會增加問題複雜性。例如，優化結構設計時人們希望設計輕而堅固。兩目標發生衝突時，就要做出權衡：可能有一種最輕的設計、一種最堅固的設計與無數種重量與強度相折中的設計。犧牲一項標準，改進另一項標準的折衷設計集合稱作帕累托集，據最佳設計的重量與強度繪製的曲線叫帕累托前沿（Pareto frontier）。

若設計不被其他設計支配，就是「帕累托最優」的（等同於「帕累托有效」，或在帕累托集合中）：被支配設計在某些方面比別的設計差，而在任何方面都不比別的設計好。

帕累托最優給出了理想目標，而沒有對目標的組合進行相對評定。在帕累托最優方案中進行選擇的任務屬於決策者。

多目標優化問題可進一步推廣為向量優化，其中（部分）排序不再由帕累托排序給出。

### 多峰、全局優化

優化問題通常是多峰的，即擁有多個好的解決方案，它們可能都是全局最優解（成本函數值相同）。獲得所有（或至少一部分）解是多峰優化的目標。

經典優化技術採用的迭代法面對多峰問題的表現並不令人滿意，因為即使運行起點不同，也不能保證獲得不同的解。

對可能存在多個極值的全局優化問題，常用演算法有進化算法、貝葉斯優化與模擬退火等。

## 臨界點與極值的分類

### 可行性問題

可滿足性問題又稱可行性問題，是指在不考慮目標值的情況下找到任何可行解的問題。可以視為數學優化的一種特例，即每個解的目標值都相同，於是每個解都是最優解。

很多優化演算法都要從可行點出發。獲得可行點的一種方法是用鬆弛變量放鬆可行性條件，只要有足夠的鬆弛變量，任何起點都是可行的。然後，最小化該鬆弛變量，直到鬆弛不為正。

### 存在性

卡爾·魏爾施特拉斯的極值定理指出，緊集上的連續實值函數會達到其最值。更一般地，緊集上的下半連續函數會達到其最小值，緊集上的上半連續函數會達到其最大值。

### 最優性的必要條件

費馬引理指出，無約束問題的最優點是駐點，即目標函數的一階導或梯度為零（見導數判別法）。更一般地，最優點可能出現在臨界點，即目標函數的一階導或梯度為零或未定義，或在選擇集的邊界上。一階條件（組）是指令內部最優點處的一階導等於零的方程（組）。

等式約束問題的最優點可用拉格朗日乘數法找到。帶等式和/或不等式約束的問題的最優值可由卡魯什-庫恩-塔克條件求得。

### 最優性的充分條件

一階導檢驗可以識別可能是極值的點，但不能區分極小值與極大值。無約束問題的目標函數二階可微時，可通過檢驗二階導（矩陣，叫做黑塞矩陣）來區分；有約束問題中，可檢驗目標函數與約束條件的二階導矩陣（稱作有界黑塞矩陣）。區分極大極小值與其他駐點的條件叫做二階條件（見導數判別法）。若候選解滿足一階條件，則滿足二階條件便足以確定至少是局部最優。

### 最優解的敏感性與連續性

包絡定理描述了基本參數變化時，最優解的值如何變化。計算這種變化的過程稱為比較靜力學。

Claude Berge（1963）提出的極大值定理描述了最優解作為基本參數之函數的連續性。

### 最優解的計算

對目標函數二階可微的無約束問題，可通過尋找梯度為零的點（駐點）確定一些臨界點。更一般地，對凸函數及其他局部利普希茨函數的最小化問題，零次梯度意味著已找到極小值。

此外，臨界點還可根據黑塞矩陣的正定性分類：若臨界點處的黑塞矩陣是正定的，則是極小值；若是負定的，則是極大值；若是不定的，則是某種鞍點。

在拉格朗日乘數的幫助下，有約束問題往往可以轉為無約束問題。拉格朗日鬆弛法也能為困難的約束問題提供近似解。

目標函數是凸函數時，極小值也就是最小值。對凸函數的最小化，存在高效的數值技術，如內點法。

### 全局收斂

更一般地，若目標函數不是二次函數，那麼很多優化方法都會用其他方法確保某些迭代子列收斂到最優解。第一種仍很流行的是線搜索，這種方法沿一個維度對函數進行優化。第二種越來越流行的，是置信域方法。線搜索與置信域方法都被用於現代不可微優化中。通常，全局優化器比先進的局部優化器（如BFGS演算法）慢得多，因此通常可從不同起點啟動局部優化器，構建高效的全局優化器。

## 計算優化技術

求解時往往使用有限步內終止的演算法，或（在某些類的問題上）收斂到解的迭代法，或儘可能為某些問題提供近似解的啟發式算法（迭代不一定收斂）。

### 優化演算法

- 喬治·伯納德·丹齊格為線性規劃提出的單純形法
- 單純形法的推廣，為二次規劃與線性分式規劃設計
- 特別適用於網路優化的單純形法變體
- 組合演算法
- 量子優化演算法

### 迭代法

迭代法用於解非線性規劃，依其求值的是黑塞矩陣、梯度或函數值而有所不同。求黑塞矩陣（H）和梯度（G）可以提高收斂速度，但對變化足夠平滑的函數，這會增加每次迭代的計算複雜度（計算成本），有時可能會過高。

優化器的一個重要指標就是所需的函數求值次數，因為這往往需要大量計算，通常比優化本身的計算量大得多，因為優化器要對N個變量進行操作。導數為此類優化器提供了詳細資訊，但算起來更困難。例如，近似梯度至少要求N+1次函數值。二階導的近似（黑塞矩陣需要）每次迭代要求N²次函數值，例如牛頓法，而更簡單的純梯度優化器則只需要N次。優化器的選擇取決於具體問題。

- 牛頓法
- 序列二次規劃：基於牛頓法，適於中小尺度約束問題。某些版本可處理高維問題。
- 內點法：這是一大類用於約束優化的方法，其中有些只使用（次）梯度資訊，另一些則需要黑塞矩陣。
- 需要梯度的方法（或近似值，或次梯度）：
- 坐標下降法：每次迭代更新一次坐標。
- 共軛梯度法：針對大型問題的迭代法（理論上在二次目標函數的有限步數內終止，但在有限精度電腦上不常能達到）。
- 梯度下降法（或「最陡下降法」「最陡上升法」）：具有歷史與理論意義的（較慢）方法，在尋找巨大問題的近似解時再次受到關注。
- 次梯度法：使用廣義梯度迭代大型局部利普希茨函數的方法。根據Boris T. Polyak的觀點，次梯度投影法類似於共軛梯度法。
- 捆綁下降法（Bundle method of descent）：適用於局部利普希茨函數的中小型問題，尤其適用於凸最小化問題（類似於共軛梯度法）。
- 橢球法：適用於目標函數為擬凸函數的小型問題的迭代法，在理論上有重要意義，特別是在確定某些組合優化問題的多項式時間複雜度方面。與擬牛頓法有相似之處。
- 弗蘭克–沃爾夫法（條件梯度法）：用於具有線性約束的特殊結構問題，特別是交通網路問題。對於一般的無約束問題簡化為梯度法，而梯度法（對幾乎所有問題）已經過時。
- 擬牛頓法：適於大中型（N<1000）問題的迭代法。
- 同時擾動隨機逼近（SPSA），用於隨機優化，運用隨機（高效）梯度逼近。
- 只需要函數值的方法：若問題是連續可微的，那麼可用有限差分法逼近梯度，這時可用基於梯度的方法。
- 插值法
- 模式搜索，收斂特性優於Nelder–Mead法（啟發式算法，帶單純形），下詳。
- 鏡像下降

### 啟發式

除了（有限終止）演算法與（收斂）迭代法，還有啟發式算法，是指任何不能保證（數學上）找到解，但某些實際情況中有用的演算法。一些著名的啟發式算法：

- 差分進化算法
- 動態鬆弛法
- 進化算法
- 遺傳算法
- 隨機重啟的爬山算法
- 模因演算法
- Nelder–Mead法：近似最小化的流行啟發式算法（不需計算梯度）
- 粒子群優化
- 模擬退火
- 隨機隧道
- 禁忌搜索

## 應用

### 力學

剛體力學問題（尤其鉸接剛體力學）常常需要數學規劃技巧，因為可以將剛體力學視為解約束流形上的常微分方程，約束是各種非線性幾何約束，如「這兩點必須重合」「此曲面不得穿過其他曲面」「此點須始終位於此曲線上的某處」之類。此外，1計算接觸力的問題也可由線性互補問題解決，也可看作是二次規劃問題。

很多設計問題可表述為優化規劃。這種應用叫做設計優化，其中一類是工程優化，最近不斷發展的另一類是多學科設計優化，在很多領域都很有用，尤其適用於航空航天工程問題。

這種方法可用於宇宙學與天體物理學。

### 經濟學與金融學

經濟學與行為主體的優化密切相關，有人將經濟學作為一門科學，描述為「將人類行為視作目的與稀缺性之關係的研究」，還有其他用途。現代優化理論包括傳統優化理論，也與博弈論、經濟均衡研究有重疊。《經濟文獻雜誌》的JEL分類系統將數學規劃、優化技術與相關主題歸入JEL:C61-C63。

微觀經濟學中，效用最大化及其對偶問題支出最小化，都是經濟優化問題。在行為一致的情形下，消費者被假定為效用最大化，公司被假定為利潤最大化。此外，主體常被建模為風險厭惡者。資產定價也用最優化理論建模，不過其基礎數學依賴於隨機過程的優化，而非靜態最優化。國際貿易理論也用最優化解釋國家間的貿易模式。投資組合優化是經濟學中多目標優化的一個例子。

1970年代以來，經濟學家利用控制論建立了隨時間變化的動態決策模型。例如，動態搜索模型用於研究勞動力市場行為。確定性模型與隨機模型之間的區別至關重要。宏觀經濟學的動態隨機一般均衡（DSGE）模型描述整個經濟的動態，是工人、消費者、投資者與政府相互依賴的優化決策結果。

### 電氣工程

優化技術在電氣工程的一些常見應用如有源濾波器設計、減少超導儲磁系統中的雜散磁場、微波結構的空間映射設計、手機天線、基於電磁學的設計等等。自1993年提出空間映射以來，微波元件與天線的電磁驗證設計優化已廣泛使用了適當的物理/經驗代理模型及空間映射方法。優化技術也用於功率流分析。

### 土木工程

優化已廣泛用於土木工程。營建管理與運輸工程是土木工程中非常依賴優化的主要分支。通過優化解決的最常見的土木工程問題有道路的切割與填築、基礎設施生命周期分析、資源均衡、水資源分配、交通管理及進度優化。

### 運籌學

另一個廣泛使用優化技術的領域是運籌學。運籌學也使用隨機建模與模擬來支持改進決策。近年來，運籌學越來越多地使用隨機規劃模擬適應事件的動態決策；此類問題可通過大規模優化與隨機優化方法來解決。

### 控制工程

數學優化被廣泛用於現代控制器設計。模型預測控制（MPC）與實時優化（RTO）等高級控制器都採用了數學優化。這些演算法在線運行，通過迭代求解約束與待控制系統模型在內的數學優化模型，反覆確定決策變量的值，如工藝設備中的扼流圈開口。

### 地球物理

優化技術常用於地球物理參數估計。根據一組測量數據（如地震記錄），通常要求底層岩石與流體的物理特性與幾何形狀。地球物理學中大多數問題都是非線性的，確定性方法與隨機方法都有廣泛使用。

### 分子建模

構象異構常用非線性優化方法。

### 生物系統建模

優化技術被用於計算系統生物學的許多方面，如建立模型、優化實驗設計、代謝工程與合成生物學等。線性規劃被用於計算發酵產物的最大可能產量，從多個微陣列數據集推斷基因調控網路以及從高通量數據推斷轉錄調控網路等。非線性規劃被用於分析能量代謝，並被應用於代謝工程與生化途徑的參數估計。

## 與人工智慧的關係

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

## 外部連結

- Links to optimization source codes