帶有約束條件的極值問題稱為約束極值問題，也叫規劃問題。若某非線性規劃的目標函式為自變數x的二次函式，約束條件又全是線性的，就稱這種規劃為二次規劃。
基本介紹
- 中文名：約束極值問題
- 適用範圍：數理科學
- 學科：運籌學
定義,求解,罰函式法轉化,簡介,常用函式法,
定義
帶有約束條件的極值問題稱為約束極值問題，也叫規劃問題。
若某非線性規劃的目標函式為自變數x的二次函式，約束條件又全是線性的，就稱這種規劃為二次規劃。
求解
求解約束極值問題要比求解無約束極值問題困難得多。為了簡化其最佳化工作，可採用以下方法：將約束問題化為無約束問題；將非線性規劃問題化為線性規劃問題，以及能將複雜問題變換為較簡單問題的其他方法。
庫恩-塔克條件是非線性規劃領域中最重要的理論成果之一，是確定某點為最優點的必要條件，但一般它並不是充分條件（對於凸規劃，它既是最優點存在的必要條件，同時也是充分條件）。
罰函式法轉化
簡介
利用罰函式法，可將非線性規劃問題的求解，轉化為求解一系列無約束極值問題，因而也稱這種方法為序列無約束最小化技術(Sequential Uneonstrained Minization Tech—nique，SUMT)。
罰函式法求解非線性規劃問題的思想是，利用問題中的約束函式作出適當的罰函式，由此構造出帶參數的增廣目標函式，把問題轉化為無約束非線性規劃問題。主要有兩種形式，一種叫外罰函式法，另一種叫內罰函式法。外部罰函式法是從非可行解出發逐漸移動到可行區域的方法。內部罰函式法也稱為障礙罰函式法，這種方法是在可行域內部進行搜尋，約束邊界起到類似圍牆的作用，如果當前解遠離約束邊界時，則罰函式值是非常小的，否則罰函式值接近無窮大的方法。
常用函式法
由於進化計算中通常採用，因此主要介紹外部罰函式法。
在進化計算中，研究者選擇外部罰函式法的原因主要是該方法不需要提供初始可行解。
需要提供初始可行解則是內部罰函式法的主要缺點。由於進化算法套用到實際問題中可能存在搜尋可行解就是NP難問題，因此這個缺點是非常致命的。
外部罰函式法一般形式為：B(x)=f(x)+[∑riGi+∑cjHj]
其中B(x)是最佳化過程中新的目標函式，Gi和Hj分別是約束條件gi(x)和hj(x)的函式，ri和cj是常數，稱為罰因子。Gi和Hj最常見的形式是Gi=max[0, gi(x)]a；Hj=|hj(x)|b，其中a和b一般是1或者2。
