運(yùn)籌學(xué)第4章非線性規(guī)劃

運(yùn)籌帷幄之中決勝千里之外第4章

非線性規(guī)劃Non-linearProgramming§4.1基本概念§4.2凸函數(shù)和凸規(guī)劃§4.3一維搜索方法§4.4無(wú)約束最優(yōu)化方法§4.5約束最優(yōu)化方法第4章

非線性規(guī)劃1.非線性規(guī)劃問(wèn)題例4.1.1

曲線的最優(yōu)擬合問(wèn)題§4.1基本概念例2構(gòu)件容積問(wèn)題§4.1基本概念1.非線性規(guī)劃問(wèn)題數(shù)學(xué)規(guī)劃約束集或可行域MP中目標(biāo)函數(shù)和約束函數(shù)中至少有一個(gè)不是x的線性函數(shù)，稱(MP)為非線性規(guī)劃§4.1基本概念MP的可行解或可行點(diǎn)向量化表示當(dāng)p=0,q=0時(shí)，稱為無(wú)約束非線性規(guī)劃或者無(wú)約束最優(yōu)化問(wèn)題。否則，稱為約束非線性規(guī)劃或者約束最優(yōu)化問(wèn)題?！?.1基本概念最優(yōu)解和極小點(diǎn)§4.1基本概念最優(yōu)解和極小點(diǎn)§4.1基本概念例：非線性規(guī)劃的圖解法2)(=xfAB2.非線性規(guī)劃方法概述：§4.1基本概念線搜索框架下的迭代算法基本迭代格式§4.1基本概念第1步

選取初始點(diǎn)0x，k:=0;

第2步

構(gòu)造搜索方向kp；

第3步

根據(jù)kp，確定步長(zhǎng)kt；

第4步

令kkkkptxx+=+1，

若1+kx已滿足某種終止條件，停止迭代，輸出

近似解1+kx；否則令k:=k+1，轉(zhuǎn)回第2步。

§4.2凸函數(shù)和凸規(guī)劃1.凸函數(shù)的定義(a)凸函數(shù)(b)凹函數(shù)§4.2凸函數(shù)和凸規(guī)劃§4.2凸函數(shù)和凸規(guī)劃2.凸函數(shù)的一些基本性質(zhì)注：一般來(lái)說(shuō)上述定理的逆是不成立的?！?.2凸函數(shù)和凸規(guī)劃2.凸函數(shù)的一些基本性質(zhì)§4.2凸函數(shù)和凸規(guī)劃2.凸函數(shù)的一些基本性質(zhì)各階主子式負(fù)正相間（第一個(gè)為負(fù)）3.凸規(guī)劃的定義約束集如果(MP)的約束集X是凸集，目標(biāo)函數(shù)f是X上的凸函數(shù)，則(MP)叫做非線性凸規(guī)劃，或簡(jiǎn)稱為凸規(guī)劃?！?.2凸函數(shù)和凸規(guī)劃定理4.2.6

凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解?！?.2凸函數(shù)和凸規(guī)劃4.凸規(guī)劃的性質(zhì)：本節(jié)練習(xí)1.

驗(yàn)證

§4.3一維搜索方法精確一維搜索方法：0.618法，Newton法非精確一維搜索方法：

Goldstein法，

Armijo法1.0.618法（近似黃金分割法）§4.3一維搜索方法2.Newton法§4.3一維搜索方法第1步

給定初始點(diǎn)1t，0>e，1:=k；

第2步

如果ej<￠)(kt，停止迭代，輸出kt。否則，當(dāng)0)(=￠￠ktj時(shí)，停止，

解題失敗；當(dāng)0)(1￠￠ktj時(shí)，轉(zhuǎn)下一步；

第3步

計(jì)算)()(1kkkkttttjj￠￠￠-=+，如果e<-+kktt1，停止迭代，輸出1+kt。否則1:+=kk，轉(zhuǎn)第2步。

3.Goldstein法§4.3一維搜索方法Goldstein法步驟:§4.3一維搜索方法4.Armijo法§4.3一維搜索方法取定Mm<<<10，用一下兩個(gè)式子限定kt不太大也不太?。?/p>

)0()0()(jjj￠+￡kkmtt

)0()0()(jjj￠+>kkmMtMt

§4.4無(wú)約束最優(yōu)化方法無(wú)約束問(wèn)題的最優(yōu)性條件最速下降法共軛方向法1、無(wú)約束問(wèn)題的最優(yōu)化條件§4.4無(wú)約束最優(yōu)化方法§4.4無(wú)約束最優(yōu)化方法1、無(wú)約束問(wèn)題的最優(yōu)化條件2.最速下降法（又稱梯度法）§4.4無(wú)約束最優(yōu)化方法§4.4無(wú)約束最優(yōu)化方法最速下降法的計(jì)算步驟：3.共軛方向法§4.4無(wú)約束最優(yōu)化方法§4.4無(wú)約束最優(yōu)化方法3.共軛方向法F-R法步驟§4.4無(wú)約束最優(yōu)化方法§4.5約束最優(yōu)化方法約束最優(yōu)化問(wèn)題的最優(yōu)化條件簡(jiǎn)約梯度法懲罰函數(shù)法其中(MP)1.約束最優(yōu)化問(wèn)題的最優(yōu)化條件§4.5約束最優(yōu)化方法Kuhn-Tucker條件（K-T條件）：§4.5約束最優(yōu)化方法注：凡是滿足K-T條件的點(diǎn)叫K-T點(diǎn)§4.5約束最優(yōu)化方法簡(jiǎn)約梯度法(4.5.12)Wolfe法步驟懲罰函數(shù)法思想：利用問(wèn)題中的約束函數(shù)做出適當(dāng)?shù)膸в袇?shù)的懲罰函數(shù)，然后在原來(lái)的目標(biāo)函數(shù)上加上懲罰函數(shù)構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把(MP)問(wèn)題的求解轉(zhuǎn)換為求解一系列無(wú)約束非線性規(guī)劃問(wèn)題。罰函數(shù)法障礙函數(shù)法罰函數(shù)法設(shè)法適當(dāng)?shù)丶哟蟛豢尚悬c(diǎn)處對(duì)應(yīng)的目標(biāo)函數(shù)值，使不可行點(diǎn)不能成為相應(yīng)無(wú)約束極小化問(wèn)題的最優(yōu)解。罰函數(shù)實(shí)際應(yīng)用中，選取一個(gè)