非線性規(guī)劃模型

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

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

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

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

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

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