約束最佳化(Constrained Optimization)，即約束最佳化問題，是最佳化問題的分支。它是在一系列約束條件下，尋找一組參數值，使某個或某一組函式的目標值達到最優。其中約束條件既可以是等式約束也可以是不等式約束。尋找這一組參數值的關鍵可是：滿足約束條件和目標值要達到最優。求解約束問題的方法可分為傳統方法和進化算法。
基本介紹
- 中文名：約束最佳化
- 外文名：Constrained Optimization
- 領域：數學、最佳化問題
- 問題求解關鍵：滿足約束條件和目標值要達到最優
- 分類：線性和非線性；單目標和多目標
- 方法：傳統方法和進化算法
定義,傳統方法,進化算法,
定義
不失一般性，約束最佳化問題可以描述為如下形式：
其中 x 是決策變數，f( x )是目標函式，
是不等式約束，
是等式約束，D={
|
}是搜尋空間， D中所有滿足約束條件的解構成可行域S，即 S={x|
}，可行域中的點稱為可行解。對於不等式約束
，若在 x 點處滿足
，則稱
在x點處是積極約束。等式約束
在所有可行解處是積極約束。
若對某一
，存在常數
，使得對
{x| 
}，有
，則稱
為局部最優解；若對一切
都有
，則稱
為全局最優解。求解最最佳化問題NLP，就是要求目標函式f(x)在約束條件下的極小點，即求出其全局最優解，但在一般情況下，往往只能求出它的一個局部最優解。
當f(x)為線性函式時稱為線性規劃問題，反之如果是非線性則為非線性規劃問題。當約束問題包含一個目標函式時，稱為單目標約束最佳化問題；當約束問題包含多個目標函式時，稱為多目標約束最佳化問題。
傳統方法
傳統方法存在如下問題：
(1) 傳統的基於梯度的最佳化方法(如可行方向法、約束變尺度法)對約束條件的處理往往是先尋找一個可行且下降的方向，然後沿此方向進行線性搜尋，並重複上述步驟以得到問題的最優解，然而該最優解往往是局部最優的。
(2) 對於許多實際的約束最佳化問題，一方面，由於目標函式往往形式複雜，不僅問題的維數比較高，而且最佳化曲面中存在多個極小點，這使得傳統的基於梯度的算法難以奏效。另一方面，實際問題中目標函式往往是不連續或不可微，有些問題目標函式甚至沒有解析表達式，傳統算法難以解決這類問題。
(3) 由於約束的存在，使得決策變數的可行搜尋空間不規則(如非凸，不連通等)，從而增加了搜尋到最優解的難度，有時甚至很難找到可行解。
進化算法
簡介
進化算法是一種智慧型的全局最佳化方法，它對函式本身性質要求非常低，往往只要求目標函式值是可以計算的，不要求它具有連續性、可微性及其它解析性質，同時它又是基於群體進化的算法，因此可採用進化算法解決約束最佳化問題。用進化算法解決約束最佳化問題的關鍵在於如何進行有效的約束處理，即如何有效均衡在可行區域與不可行區域的搜尋。
與傳統方法相比的優勢
(1) 在一般情況下，進化算法能否收斂到全局最優解與初始群體無關，而傳統最佳化方法則依賴於初始解；
(2) 進化算法具有全局搜尋能力，而很多傳統最佳化方法往往會陷入局部最優；
(3) 進化算法的適用範圍廣，能有效地解決不同類型的問題，而傳統最佳化方法在設計時往往就只能解訣某一類型的問題。
存在的不足
(1) 進化算法中的參數，如群體規模、進化代數、重組機率、變異機率等，往往需要根據經驗設定，且在一定程度上與問題相關；
(2) 進化算法的收斂問題，進化算法求解實際問題時的收斂性判定缺乏理論指導。
