演算法最佳化之外點法（罰函式法）

外點法（罰函式法）的基本概念：

罰函式法又稱乘子法，是指將有約束最最佳化問題轉化為求解無約束最最佳化問題：其中

為足夠大的正數， 起“懲罰”作用， 稱之為罰因子，

稱為罰函式。內部罰函式法也稱為障礙罰函式法。

這種方法是在可行域內部進行搜尋，約束邊界起到類似圍牆的作用，如果當前解遠離約束邊界時，則罰函式值是非常小的，否則罰函式值接近無窮大的方法。在進化計算中，研究者選擇外部罰函式法的原因主要是該方法不需要提供初始可行解。其中

是最佳化過程中新的目標函式，

和

分別是約束條件

和

的函式，

是常數，稱為罰因子。

外點法（罰函式法）的適用範圍：

非線性規劃有約束

的問題，一般用在非線性規劃

不等式約束

的問題。

外點法（罰函式法）的數學定義：

1。考慮約束問題：

其中

是

上的連續函式

2。 由目標函式和約束函式組成輔助函式，把原來的約束問題轉化維極小化輔助函式的無約束問題

（1） 對於等式約束問題

可定義輔助函式

其中引數

是很大的正數

把（1）轉化為無約束的問題

顯然，（3）的最優解比使得

接近零，因為如果不這樣的話，問題（3）中 的

項將是很大的正數，現行點必不是極小點。由此可見，求解問題（3）就能夠得到問題（1）的近似解。

（2）對於不等式約束問題

這與上面構造輔助函式的基本思想一致：

1）在可行點輔助函式值等於原來的目標函式值

2）在不可行點，輔助函式值等於原來的目標函式值加上一個很大的正數

定義函式：

其中

是很大的正數

將問題（4）轉化為無約束問題：

透過問題（6）求得問題（4）的近似解

（3）對於一般情形（0），定義函式

其中

具有下列形式：

典型取法：

通常取

這樣，把約束問題（0）轉化為無約束問題：

其中

是很大的正數，

是連續函式

求解問題（9）能夠得到約束問題（0）的近似解，而且

越大，近似程度越好

（1）

稱為罰項

（2）

稱為罰因子

（3）

稱為罰函式

應用案例：

例：

罰函式

可透過求解下列無約束問題，求得（1）的近似解：

用解析方法求解無約束問題：

令

，解得

顯然，

越大，

越接近問題（1）得最優解，當

無窮大 時，

。