Remove ads
最佳化指從一組可選擇的方案中，根據一定標準選擇最佳方案的過程，往往要在特定情況下最大化或最小化某一特定函數或變數。[1]一般分為離散最佳化、連續最佳化兩個子領域。最佳化問題出現在電腦科學、工程學[2]到作業研究、經濟學等所有定量學科中，幾百年來求解方法的發展一直受到數學界的關注。[3] 在更一般的方法中，最佳化問題往往要系統地選擇輸入值、計算函數值以最大化或最小化某實函數。將最佳化理論與技術推廣到其他的表述，構成了應用數學的一個分支。更一般地說，最佳化包括在給定定義域（或輸入）的情形下，找到某目標函數的「最佳可達值」。
Remove ads
最佳化問題可用以下方式表示：[4]
這樣表述後，稱作最佳化問題或數學規劃問題。很多現實問題與理論問題都可用這個一般框架建模。
由於下式成立：
只需解最小化問題。只考慮最大化問題的相反觀點是同理的。
物理學領域，使用這種技術提出的問題可稱「能量最小化」，將函數f值視為所建模系統的能量。機器學習中，總要用損失函數持續評估模型的品質，損失函數取得極小值意味著一組可能的最佳參數，同時具有最佳（最小）的誤差。
A通常是歐氏空間的子集，一般要求A的成員需滿足一組約束（等式或不等式）。f的定義域A稱作搜尋空間或選擇集，A的元素稱作候選解或可行解。
函數f有多種叫法，常見的有目標函數、判別函數、損失函數、成本函數（最小化）[5]、效率函數、適應度函數（最大化），某些領域還有能量函數、能量泛函等等。使得目標函數取最值（取決於問題）的可行解就是最佳解。
數學中，傳統最佳化問題通常用最小化形式表示。
極值是局部的，定義為，滿足一定條件。例如，極小值要滿足
這就是說，在周圍的一些閉球上，所有的函數值都大於或者等於在該點的函數值。
極小值至少於附近的任何元素一樣好，最小值則至少與每個可行解一樣好。一般來說，除非目標函數是凸函數，否則會存在多個極小值。凸最佳化問題中，若有位於可行集內（不位於邊際）的極小值，則它也是最小值；而非凸最佳化問題可能有多個極小值。
非凸問題所用的大量演算法（包括大多數商業求解器）都無法區分局部最佳解與全域最佳解，而是將前者視作原問題的實際解。全域最佳化是應用數學與數值分析的一個分支，主要研究能在有限時間內收斂到非凸問題實際最佳解的確定性演算法。
Remove ads
最佳化問題常用特殊符號表示，如下：
Remove ads
這是求，從實數集中選擇x時，目標函數的最小值。此問最小值為1，出現在處。
相似地，
Remove ads
![{\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,}](http://wikimedia.org/api/rest_v1/media/math/render/svg/39c071258fcecb43aaf25920b9833589bc35036c)
或等價的
![{\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{subject to:}}\;x\in (-\infty ,-1].}](http://wikimedia.org/api/rest_v1/media/math/render/svg/a2ecc7504e271936684860c5d738740d0841edac)
這是求參數x在區間時，能使目標函數取最值的值。此問題的答案是，因為不可行，不屬於可行集。
![{\displaystyle (-\infty ,\ -1]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/50793e8ffbfd8d1f35ccab94e75c58736afd072f)
相似地，
![{\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos y,}](http://wikimedia.org/api/rest_v1/media/math/render/svg/ee3de833a31bfb33700e63b8d5df04565e899915)
或等價的
![{\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,}](http://wikimedia.org/api/rest_v1/media/math/render/svg/29cd276141e8e134eb156b2fa537ced38c14a5b3)
表示使目標函數取最大值的對，且x要滿足約束：位於區間內。此問題的答案是與，其中k的範圍是所有整數。
![{\displaystyle [-5,\ 5]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/747026ef8f345e2391441225fde05ad6ae10d06d)
算符有時也作，分別代表最小值點與最大值點。
Remove ads
皮埃爾·德·費馬與約瑟夫·拉格朗日發現了基於微積分的公式以確定最佳值，艾薩克·牛頓與卡爾·弗里德里希·高斯提出迭代法以逼近最佳值。
用於部分最佳化情形的「線性規劃」（linear programming）是喬治·伯納德·丹齊格提出的，不過其中大部分理論是列昂尼德·坎托羅維奇於1939年提出的。丹齊格在1947年提出單體法，馮·諾依曼等人也在同時期致力於線性規劃的理論研究（如對偶）。[6]
其他著名的最佳化研究者有：
Remove ads
- 線性規劃：當目標函數f是線性函數而且集合A是由線性等式函數和線性不等式函數來確定的， 我們稱這一類問題為線性規劃
- 整數規劃：當線性規劃問題的部分或所有的變數局限於整數值時， 我們稱這一類問題為整數規劃問題
- 二次規劃：目標函數是二次函數，而且集合A必須是由線性等式函數和線性不等式函數來確定的。
- 分數規劃：研究的是如何最佳化兩個非線性函數的比例。
- 非線性規劃：研究的是目標函數或是限制函數中含有非線性函數的問題。
- 隨機規劃：研究的是某些變數是隨機變數的問題。
- 動態規劃：研究的是最佳策略基於將問題分解成若干個較小的子問題的最佳化問題。
- 組合最佳化：研究的是可行解是離散或是可轉化為離散的問題。
- 無限維最佳化：研究的是可行解的集合是無限維空間的子集的問題，一個無限維空間的例子是函數空間。
- 凸最佳化研究目標函數為凸函數（最小化）或凹函數（最大化），且約束集為凸集的問題。這可以看成非線性規劃的特例，或凸二次規劃的推廣。
- 整數規劃研究部分或所有變數取整數值的線性規劃，不屬於凸規劃，往往比常規線性規劃困難很多。
- 二次規劃允許目標函數包含二次項，而可行集須用線性等式與不等式指定。若有特殊形式的二次項，則屬於凸規劃。
- 分式規劃研究兩非線性函數之比的最佳化。一類凹分式規劃可轉為凸最佳化問題。
- 非線性規劃研究目標函數和/或約束包含非線性部分的一般情形。可能屬於凸規劃也可能不屬於，規劃是否為凸一般會影響求解難度。
- 隨機規劃研究某些約束或參數取決於隨機變數的問題。
- 穩健最佳化類似於隨機規劃，試圖捕捉最佳化問題基礎資料中的隨機性。穩健最佳化試圖找到在不定集定義的不確定性的所有可能下，都有效的解。
- 組合最佳化關注可行解集離散，或可簡化為離散情形的問題。
- 隨機最佳化用於搜尋過程中的隨機（噪聲）函數測量或隨機輸入。
- 無窮維最佳化研究可行解集為無窮維空間（如函數空間）子集的情形。
- 啟發式與元啟發演算法對待最佳化問題（幾乎）不做假設。啟發式演算法一般不能保證找到最佳解，而可用於找到很多複雜最佳化問題的近似解。
- 約束滿足研究目標函數f為常數的情形（常見於人工智慧領域，特別是自動推理）。
- 約束編程是一種編程範式，變數間關係表為約束。
- 分離規劃（disjunctive programming）研究必須滿足至少一個約束，而非所有約束的問題。分離規劃尤其適用於排程。
- 空間對映是工程系統建模與最佳化的概念，利用具有物理意義的代理模型，達到保持模型精度，而減小計算量的效果。
在一些子領域中，這些技術用於動態環境（隨時間變化的決策）中的最佳化：
Remove ads
在最佳化問題中加入多個目標，會增加問題複雜性。例如，最佳化結構設計時人們希望設計輕而堅固。兩目標發生衝突時，就要做出權衡：可能有一種最輕的設計、一種最堅固的設計與無數種重量與強度相折中的設計。犧牲一項標準，改進另一項標準的折衷設計集合稱作柏拉圖集，據最佳設計的重量與強度繪製的曲線叫柏拉圖前沿（Pareto frontier）。
若設計不被其他設計支配，就是「柏拉圖最佳」的（等同於「柏拉圖有效」，或在柏拉圖集合中）：被支配設計在某些方面比別的設計差，而在任何方面都不比別的設計好。
柏拉圖最佳給出了理想目標，而沒有對目標的組合進行相對評定。在柏拉圖最佳方案中進行選擇的任務屬於決策者。
多目標最佳化問題可進一步推廣為向量最佳化，其中（部分）排序不再由柏拉圖排序給出。
Remove ads
最佳化問題通常是多峰的，即擁有多個好的解決方案，它們可能都是全域最佳解（成本函數值相同）。獲得所有（或至少一部分）解是多峰最佳化的目標。
經典最佳化技術採用的迭代法面對多峰問題的表現並不令人滿意，因為即使執行起點不同，也不能保證獲得不同的解。
可滿足性問題又稱可行性問題，是指在不考慮目標值的情況下找到任何可行解的問題。可以視為數學最佳化的一種特例，即每個解的目標值都相同，於是每個解都是最佳解。
很多最佳化演算法都要從可行點出發。獲得可行點的一種方法是用鬆弛變數放鬆可行性條件，只要有足夠的鬆弛變數，任何起點都是可行的。然後，最小化該鬆弛變數，直到鬆弛不為正。
卡爾·魏爾施特拉斯的極值定理指出，緊集上的連續實值函數會達到其最值。更一般地，緊集上的下半連續函數會達到其最小值，緊集上的上半連續函數會達到其最大值。
費馬引理指出，無約束問題的最佳點是駐點，即目標函數的一階導或梯度為零（見導數判別法）。更一般地，最佳點可能出現在臨界點，即目標函數的一階導或梯度為零或未定義，或在選擇集的邊界上。一階條件（組）是指令內部最佳點處的一階導等於零的方程式（組）。
等式約束問題的最佳點可用拉格朗日乘數法找到。帶等式和/或不等式約束的問題的最佳值可由卡魯什-庫恩-塔克條件求得。
一階導檢定可以辨識可能是極值的點，但不能區分極小值與極大值。無約束問題的目標函數二階可微時，可通過檢定二階導（矩陣，叫做黑塞矩陣）來區分；有約束問題中，可檢定目標函數與約束條件的二階導矩陣（稱作有界黑塞矩陣）。區分極大極小值與其他駐點的條件叫做二階條件（見導數判別法）。若候選解滿足一階條件，則滿足二階條件便足以確定至少是局部最佳。
包絡定理描述了基本參數變化時，最佳解的值如何變化。計算這種變化的過程稱為比較靜力學。
Claude Berge（1963）提出的極大值定理描述了最佳解作為基本參數之函數的連續性。
對目標函數二階可微的無約束問題，可通過尋找梯度為零的點（駐點）確定一些臨界點。更一般地，對凸函數及其他局部利普希茨函數的最小化問題，零次梯度意味著已找到極小值。
此外，臨界點還可根據黑塞矩陣的正定性分類：若臨界點處的黑塞矩陣是正定的，則是極小值；若是負定的，則是極大值；若是不定的，則是某種鞍點。
在拉格朗日乘數的幫助下，有約束問題往往可以轉為無約束問題。拉格朗日鬆弛法也能為困難的約束問題提供近似解。
更一般地，若目標函數不是二次函數，那麼很多最佳化方法都會用其他方法確保某些迭代子列收斂到最佳解。第一種仍很流行的是線搜尋，這種方法沿一個維度對函數進行最佳化。第二種越來越流行的，是置信域方法。線搜尋與置信域方法都被用於現代不可微最佳化中。通常，全域最佳化器比先進的局部最佳化器（如BFGS演算法）慢得多，因此通常可從不同起點啟動局部最佳化器，構建高效的全域最佳化器。
求解時往往使用有限步內終止的演算法，或（在某些類的問題上）收斂到解的迭代法，或儘可能為某些問題提供近似解的啟發式演算法（迭代不一定收斂）。
迭代法用於解非線性規劃，依其求值的是黑塞矩陣、梯度或函數值而有所不同。求黑塞矩陣（H）和梯度（G）可以提高收斂速度，但對變化足夠平滑的函數，這會增加每次迭代的計算複雜度（計算成本），有時可能會過高。
最佳化器的一個重要指標就是所需的函數求值次數，因為這往往需要大量計算，通常比最佳化本身的計算量大得多，因為最佳化器要對N個變數進行操作。導數為此類最佳化器提供了詳細資訊，但算起來更困難。例如，近似梯度至少要求N+1次函數值。二階導的近似（黑塞矩陣需要）每次迭代要求N²次函數值，例如牛頓法，而更簡單的純梯度最佳化器則只需要N次。最佳化器的選擇取決於具體問題。
- 需要黑塞矩陣的方法（或用差分計算近似值）：
- 需要梯度的方法（或近似值，或次梯度）：
- 坐標下降法：每次迭代更新一次坐標。
- 共軛梯度法：針對大型問題的迭代法（理論上在二次目標函數的有限步數內終止，但在有限精度電腦上不常能達到）。
- 梯度下降法（或「最陡下降法」「最陡上升法」）：具有歷史與理論意義的（較慢）方法，在尋找巨大問題的近似解時再次受到關注。
- 次梯度法：使用廣義梯度迭代大型局部利普希茨函數的方法。根據Boris T. Polyak的觀點，次梯度投影法類似於共軛梯度法。
- 捆綁下降法（Bundle method of descent）：適用於局部利普希茨函數的中小型問題，尤其適用於凸最小化問題（類似於共軛梯度法）。
- 橢球法：適用於目標函數為擬凸函數的小型問題的迭代法，在理論上有重要意義，特別是在確定某些組合最佳化問題的多項式時間複雜度方面。與擬牛頓法有相似之處。
- 弗蘭克–沃爾夫法（條件梯度法）：用於具有線性約束的特殊結構問題，特別是交通網路問題。對於一般的無約束問題簡化為梯度法，而梯度法（對幾乎所有問題）已經過時。
- 擬牛頓法：適於大中型（N<1000）問題的迭代法。
- 同時擾動隨機逼近（SPSA），用於隨機最佳化，運用隨機（高效）梯度逼近。
- 只需要函數值的方法：若問題是連續可微的，那麼可用有限差分法逼近梯度，這時可用基於梯度的方法。
- 插值法
- 模式搜尋，收斂特性優於Nelder–Mead法（啟發式演算法，帶單體），下詳。
- 鏡像下降
除了（有限終止）演算法與（收斂）迭代法，還有啟發式演算法，是指任何不能保證（數學上）找到解，但某些實際情況中有用的演算法。一些著名的啟發式演算法：
剛體力學問題（尤其鉸接剛體力學）常常需要數學規劃技巧，因為可以將剛體力學視為解約束流形上的常微分方程式，[7]約束是各種非線性幾何約束，如「這兩點必須重合」「此曲面不得穿過其他曲面」「此點須始終位於此曲線上的某處」之類。此外，1計算接觸力的問題也可由線性互補問題解決，也可看作是二次規劃問題。
很多設計問題可表述為最佳化規劃。這種應用叫做設計最佳化，其中一類是工程最佳化，最近不斷發展的另一類是多學科設計最佳化，在很多領域都很有用，尤其適用於航空航天工程問題。
經濟學與行為主體的最佳化密切相關，有人將經濟學作為一門科學，描述為「將人類行為視作目的與稀缺性之關係的研究」，還有其他用途。[9]現代最佳化理論包括傳統最佳化理論，也與博弈論、經濟均衡研究有重疊。《經濟文獻雜誌》的JEL分類系統將數學規劃、最佳化技術與相關主題歸入JEL:C61-C63。
微觀經濟學中，效用最大化及其對偶問題支出最小化，都是經濟最佳化問題。在行為一致的情形下，消費者被假定為效用最大化，公司被假定為利潤最大化。此外，主體常被建模為風險厭惡者。資產定價也用最佳化理論建模，不過其基礎數學依賴於隨機過程的最佳化，而非靜態最佳化。國際貿易理論也用最佳化解釋國家間的貿易模式。投資組合最佳化是經濟學中多目標最佳化的一個例子。
1970年代以來，經濟學家利用控制論建立了隨時間變化的動態決策模型。[10]例如，動態搜尋模型用於研究勞動力市場行為。[11]確定性模型與隨機模型之間的區別至關重要。[12]總體經濟學的動態隨機一般均衡（DSGE）模型描述整個經濟的動態，是工人、消費者、投資者與政府相互依賴的最佳化決策結果。[13][14]
最佳化技術在電氣工程的一些常見應用如有源濾波器設計、[15]減少超導儲磁系統中的雜散磁場、微波結構的空間對映設計、[16]手機天線、[17][18][19]基於電磁學的設計等等。自1993年提出空間對映以來，微波元件與天線的電磁驗證設計最佳化已廣泛使用了適當的物理/經驗代理模型及空間對映方法。[20][21]最佳化技術也用於功率流分析。[22]
最佳化已廣泛用於土木工程。營建管理與交通工程是土木工程中非常依賴最佳化的主要分支。通過最佳化解決的最常見的土木工程問題有道路的切割與填築、基礎設施生命週期分析、[23]資源均衡、[24][25]水資源分配、交通管理[26]及進度最佳化。
另一個廣泛使用最佳化技術的領域是作業研究。[27]作業研究也使用隨機建模與類比來支援改進決策。近年來，作業研究越來越多地使用隨機規劃類比適應事件的動態決策；此類問題可通過大規模最佳化與隨機最佳化方法來解決。
數學最佳化被廣泛用於現代控制器設計。模型預測控制（MPC）與即時最佳化（RTO）等進階控制器都採用了數學最佳化。這些演算法線上執行，通過迭代求解約束與待控制系統模型在內的數學最佳化模型，反覆確定決策變數的值，如工藝裝置中的扼流圈開口。
最佳化技術常用於地球物理參數估計。根據一組測量資料（如地震記錄），通常要求底層岩石與流體的物理特性與幾何形狀。地球物理學中大多數問題都是非線性的，確定性方法與隨機方法都有廣泛使用。
構象異構常用非線性最佳化方法。
最佳化技術被用於計算系統生物學的許多方面，如建立模型、最佳化實驗設計、代謝工程與合成生物學等。[28]線性規劃被用於計算發酵產物的最大可能產量，[28]從多個微陣列資料集推斷基因調控網路[29]以及從高通量資料推斷轉錄調控網路等。[30]非線性規劃被用於分析能量代謝[31]，並被應用於代謝工程與生化途徑的參數估計。[32]
現代的電腦科學技術和人工智慧科學把最佳化作為一個重要的領域來研究。我們也可以認為人工智慧的一些演算法，就是類比了人類尋求實際問題最佳解的過程。例如，利用人工智慧方法設計軟體，配合外部的電子裝置例如網路攝影機辨識人臉；利用資料探勘和神經網路演算法來尋找投資的最佳時機等。
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
Remove ads