非線性規(guī)劃模型參考模板

1、非線性規(guī)劃模型在上一次作業(yè)中，我們對線性規(guī)劃模型進行了相應的介紹及優(yōu)缺點，然而在實際問題中并不是所有的問題都可以利用線性規(guī)劃模型求解。實際問題中許多都可以歸結為一個非線性規(guī)劃問題，即如果目標函數(shù)和約束條件中包含有非線性函數(shù)，則這樣的問題稱為非線性規(guī)劃問題。一般來說，解決非線性的問題要比線性的問題難得多，不像線性規(guī)劃有適用于一般情況的單純形法。對于線性規(guī)劃來說，其可行域一般是一個凸集，只要存在最優(yōu)解，則其最優(yōu)解一定在可行域的邊界上達到；對于非線性規(guī)劃，即使是存在最優(yōu)解，卻是可以在可行域的任一點達到，因此，對于非線性規(guī)劃模型，迄今為止還沒有一種適用于一般情況的求解方法，我們在本文中也只是介紹了幾個

2、比較常用的幾個求解方法。一、非線性規(guī)劃的分類1無約束的非線性規(guī)劃當問題沒有約束條件時，即求多元函數(shù)的極值問題，一般模型為此類問題即為無約束的非線性規(guī)劃問題1.1無約束非線性規(guī)劃的解法 1.1.1一般迭代法即為可行方向法。對于問題給出的極小點的初始值，按某種規(guī)律計算出一系列的，希望點陣的極限就是的一個極小點。由一個解向量求出另一個新的解向量向量是由方向和長度確定的，所以即求解和，選擇和的原則是使目標函數(shù)在點陣上的值逐步減小，即 檢驗是否收斂與最優(yōu)解，及對于給定的精度，是否。 1.1.2一維搜索法當用迭代法求函數(shù)的極小點時，常常用到一維搜索，即沿某一已知方向求目標函數(shù)的極小點。一維搜索的方法很多，

3、常用的有：（1）試探法（“成功失敗”，斐波那契法，0.618法等）；（2）插值法（拋物線插值法，三次插值法等）；（3）微積分中的求根法（切線法，二分法等）。1 / 6考慮一維極小化問題若是區(qū)間上的下單峰函數(shù)，我們介紹通過不斷地縮短的長度，來搜索得的近似最優(yōu)解的兩個方法。通過縮短區(qū)間，逐步搜索得的最優(yōu)解的近似值 2.1.3梯度法選擇一個使函數(shù)值下降速度最快的的方向。把在點的方向導數(shù)最小的方向作為搜索方向，即令.計算步驟： （1）選定初始點和給定的要求，； （2）若，則停止計算，否則； （3）在處沿方向做一維搜索得，返回第二步，直到求得最優(yōu)解為止.可以求得： 2.1.4共軛梯度法又稱共軛斜量法，僅

4、適用于正定二次函數(shù)的極小值問題：A為階實對稱正定陣從任意初始點和向量出發(fā)，由和可以得到能夠證明向量是線性無關的，且關于A是兩兩共軛的。從而可得到，則為的極小點。計算步驟：（1）對任意初始點和向量，?。?）若，即得到最優(yōu)解，停止計算，否則求（3）令；返回（2） 2.1.5牛頓法對于問題：由則由最優(yōu)條件當A為正定時，存在，于是有為最優(yōu)解 2.1.6擬牛頓法對于一般的二階可微函數(shù)，在點的局部有當正定時，也可用上面的牛頓法，這就是擬牛頓法。計算步驟：（1） 任取，（2）計算，若，則停止計算，否則計算，令；（3）令；返回（2）2有約束的非線性規(guī)劃2.1非線性規(guī)劃的最優(yōu)性條件若是非線性問題中的極小點，且對

5、點有效約束的梯度線性無關，則必存在向量使下述條件成立：此條件為庫恩-塔克條件（K-T條件），滿足K-T條件的點也稱為K-T點。K-T條件是非線性規(guī)劃最重要的理論基礎，是確定某點是否為最優(yōu)解的必要條件，但不一定是充要條件。對于凸規(guī)劃它一定是充要條件。2.2非線性規(guī)劃的可行方向法由于線性規(guī)劃的目標函數(shù)為線性函數(shù)，可行域為凸集，因而求出的最優(yōu)解就是整個可行域上的全局最優(yōu)解。非線性規(guī)劃卻不然，有時求出的某個解雖是一部分可行域上的極值點，但并不一定是整個可行域上的全局最優(yōu)解。假設非線性規(guī)劃問題中的一個可行解，但不是最優(yōu)解，為了進一步尋找最優(yōu)解在它的可行下降方向中選取其中一個方向，并確定最佳步長，使得反復

6、進行這一過程，直到得到滿足精度要求為止，這種方法稱為可行方向法，也稱迭代法。 2.3有約束非線性規(guī)劃的解法 2.3.1外點法 （1）對于等式約束問題做輔助函數(shù)如果最優(yōu)解滿足或近似滿足則就是問題的最優(yōu)解或近似解 （2）對于不等式約束問題做輔助函數(shù)求. （3）對于一般問題做輔助函數(shù)求解 2.3.2內點法 內點法是在可行域內進行得，并一直保持在可行域內進行搜索，只適用于不等式約束的問題輔助函數(shù)：X趨于R的邊界時，使趨向于正無窮，的常用形式求解2 非線性規(guī)劃的缺陷不足算法優(yōu)點缺點梯度法計算量小，存儲變量較少,初始點要求不高初值依賴，收斂慢，最速下降法適用于尋優(yōu)過程的前期迭代或作為間插步驟，越接近極值點時，收斂熟讀越慢，后期宜選用收斂快的算法牛頓法收斂速度很快當維數(shù)較