非線性規(guī)劃-無約束問題

非線性規(guī)劃—無約束問題基本概念非線性規(guī)劃模型極值問題凸函數(shù)和凹函數(shù)凸規(guī)劃下降迭代算法一維搜索Fibonacci法0.618法無約束極值問題的解法梯度法共軛梯度法變尺度法步長(zhǎng)加速法非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第1頁!

如果目標(biāo)函數(shù)或約束條件中含有一個(gè)或多個(gè)是變量的非線性函數(shù)，我們稱這類規(guī)劃問題為非線性規(guī)劃（nonlinearprogramming，簡(jiǎn)記為NP）。一般地，解非線性規(guī)劃問題要比解線性規(guī)劃問題困難的多，因?yàn)樗幌窠饩€性規(guī)劃問題有單純形法這一通用的方法，非線性規(guī)劃目前還沒有適合于各種問題的一般算法，各個(gè)方法都有自己特定的應(yīng)用范圍。1.1非線性規(guī)劃問題及其數(shù)學(xué)模型非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第2頁!

例：某金屬制品廠要加工一批容積為1米3的長(zhǎng)方形容器，按規(guī)格要求，上下底的材料為25元/m2，側(cè)面的材料為40元/m2，試確定長(zhǎng)、寬、高的尺寸，使這個(gè)容器的成本最低。設(shè)容器的長(zhǎng)為x1，寬為x2，則高為1/x1x2。根據(jù)題意得：非線性規(guī)劃模型非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第3頁!

由這兩個(gè)例子可以看出，這兩個(gè)例子在高等數(shù)學(xué)中代表了兩類不同類型的極值問題。例1是無條件極值；例2是有條件極值。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第4頁!ABDC非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第5頁!1.2極值問題線性規(guī)劃：目標(biāo)函數(shù)是線性函數(shù)，可行域?yàn)橥辜?，求出的最?yōu)解就是整個(gè)可行域上的全局最優(yōu)解。非線性規(guī)劃：有時(shí)求出的解是一部分可行域上的極值點(diǎn)，但并不一定是整個(gè)可行域上的全局最優(yōu)解。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第6頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第7頁!定理2：極值存在的充分條件非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第8頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第9頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第10頁!凸函數(shù)與凹函數(shù)的幾何意義即函數(shù)圖形上任意兩點(diǎn)的連線處處不在這個(gè)函數(shù)圖形的下方，稱它為凸函數(shù)，下凸的。線性函數(shù)既是凸函數(shù)，又是凹函數(shù)。X(1）X(2)凸函數(shù)X(1）X(2)凹函數(shù)非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第11頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第12頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第13頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第14頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第15頁!1.4凸規(guī)劃非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第16頁!1.5下降迭代算法

非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第17頁!設(shè)算法產(chǎn)生的點(diǎn)列{x(k)},收斂到解X*,且X(k)≠X*，k，若存在>0,及一個(gè)與迭代次數(shù)k無關(guān)的常數(shù)q>0，使1.線性收斂：當(dāng)＝1,q>0時(shí)稱為線性收斂速度。2.超線性收斂：當(dāng)1<<2,q>0，或＝1,q＝0時(shí)，稱為超線性收斂速度3.二階收斂：當(dāng)=2

，k充分大時(shí)有收斂速度非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第18頁!迭代中我們從一點(diǎn)出發(fā)沿下降可行方向找一個(gè)新的、性質(zhì)有所改善的點(diǎn)。下降方向：非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第19頁!常用的搜索算法結(jié)構(gòu)線性搜索求，新點(diǎn)使x(k+1)∈S初始x(1)∈S,k=1對(duì)x(k)點(diǎn)選擇下降可行方向d(k)是否滿足停機(jī)條件？停k=k+1yesno非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第20頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第21頁!2.1分?jǐn)?shù)法（斐波那契法）abX*a1b1abX*a1b1分?jǐn)?shù)法是尋找單峰函數(shù)極小點(diǎn)的一種方法。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第22頁!這樣如此繼續(xù)下去，就能越來越精確地估計(jì)出x*的位置。當(dāng)然，如果無限地搜索下去，可以精確地求出極小點(diǎn)x*。但實(shí)際計(jì)算時(shí)只能使x*包含在某個(gè)小區(qū)間內(nèi)，且此時(shí)小區(qū)間的長(zhǎng)度不超過某一給定的精度就可以了。如經(jīng)過n次搜索以后，已知x*位于區(qū)間[an,bn]中，且|an－bn|<其中是事先給定的精度，這時(shí)區(qū)間[an,bn]中的點(diǎn)都可以作為x*的近似點(diǎn)。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第23頁!

在區(qū)間[a,b]內(nèi)任取兩點(diǎn)a1和b1，計(jì)算函數(shù)值以縮短區(qū)間，縮短后的區(qū)間為[a,b1]或[a1,b]，顯然，這兩個(gè)區(qū)間長(zhǎng)度之和必大于[a,b]區(qū)間的長(zhǎng)度。也就是說，計(jì)算兩次函數(shù)值一般無法把長(zhǎng)度大于2的區(qū)間縮短成單位區(qū)間，但是對(duì)于長(zhǎng)度為2的區(qū)間，可以用如圖的方法選取試點(diǎn)a1和b1，圖中為任意小的正數(shù)，縮短后的區(qū)間長(zhǎng)度為1＋，故縮短后的區(qū)間長(zhǎng)度近似等于1。由此得：

F2=2根據(jù)同樣的方法，可得

F3=3,F4=5,F5=8,F6=13…..ab1-1+a1b1非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第24頁!

現(xiàn)在對(duì)于尋找近似極小點(diǎn)來說，如果希望誤差不超過，只需將原區(qū)間[a,b]縮短為包含極小點(diǎn)而區(qū)間長(zhǎng)度不超過的區(qū)間就可以了。這時(shí)計(jì)算函數(shù)值的次數(shù)n只要滿足：非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第25頁!（3）計(jì)算f(x2)與f(x2’)，比較它們的大小。方法同（2）（4）當(dāng)?shù)絢=n+1時(shí)，

xn-1=xn-1’=(an-2+bn-2)/2這時(shí)無法比較函數(shù)值f(xn-1)與f(xn-1’)來確定最后的區(qū)間[an-1,an-1]，非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第26頁!迭代次數(shù)anbn0-221-20.47622-1.04760.47623-1.0476-0.09524-0.6666-0.09525-0.6666-0.28576-0.6666-0.4723非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第27頁!初始[α,β],ε>0

λ=α+（1-t）(β-α)μ=α+t(β-α)β-α<ε?

STOP;λ*

=(α+β)/2yesf（λ）

-f（μ）>0?Noα=λ,λ=μ

μ=α+t(β-α)yesΒ=μ,μ=λλ=α+（1-t）(β-α)Noαλμβμβ

αλμβαλ具體算法：非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第28頁!再比較次與第三次的試驗(yàn)結(jié)果。1000(1)1382(2)16182000(3)1764如果仍然是第(2)點(diǎn)較第(3)點(diǎn)效果好，則去掉1764至2000這一段，然后在留下的一段中再找出第(4)點(diǎn)的對(duì)稱點(diǎn)，做第四次試驗(yàn)，其加入量為1382＋0.618(1764－1382)=1528g1000(1)1382(2)16182000(3)1764(4)1528如果仍然是第(4)點(diǎn)較第(2)點(diǎn)效果好，則去掉1618至1764這一段，對(duì)留下的1382至1618這一段中繼續(xù)試驗(yàn)下去就能找到最優(yōu)點(diǎn)，這樣可以用最少的試驗(yàn)次數(shù)找到最佳加入量。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第29頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第30頁!對(duì)f

在xk

點(diǎn)展開：

f(x)=f(xk)+f'(xk)(x-xk)+f″(xk)(x-xk)2/2+o(x-xk)2

取二次式（略去高階項(xiàng)）：

qk(x)=f(xk)+f'(xk)(x-xk)+(f″(xk)(x-xk)2)/2用qk(x)作為f(x)的近似。首先求qk(x)的導(dǎo)數(shù)，并令其等于零。

q′k(x)=f′(xk)+f″(xk)(x-xk)=0

得xk

+1=xk–f′(xk)/f″(xk)

取xk

+1為新的迭代點(diǎn)。以上過程即Newton法。特點(diǎn)：二階、局部收斂。（算法框圖見下頁）非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第31頁!當(dāng)f(x)在[a,b]上僅有三階導(dǎo)數(shù)，f′(a)f′(b)<0,以及f″(x)>0,則切線法產(chǎn)生的點(diǎn)列收斂到f(x)在[a,b]中的唯一極小點(diǎn)。當(dāng)f(x)是具有極小點(diǎn)的二次函數(shù)時(shí)，牛頓法可以一步達(dá)到極小點(diǎn)。當(dāng)f(x)的三階導(dǎo)數(shù)在[a,b]內(nèi)大于零時(shí)，迭代的初始點(diǎn)x0應(yīng)在a端點(diǎn)附近，f(x)的三階導(dǎo)數(shù)在[a,b]內(nèi)小于零時(shí)，迭代的初始點(diǎn)x0應(yīng)在b端點(diǎn)附近.非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第32頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第33頁!

試驗(yàn)點(diǎn)位置的確定方法不同。在試探法中試驗(yàn)點(diǎn)的位置是由某種給定的規(guī)律確定的，并未考慮函數(shù)值的分布。例如：黃金分割法是按照等比例0.618縮短率確定的。而在插值法中，試驗(yàn)點(diǎn)的位置是按函數(shù)值近似分布的極小點(diǎn)確定的。試探法僅僅利用了試驗(yàn)點(diǎn)函數(shù)值進(jìn)行大小的比較，而插值法還要利用函數(shù)值本身。所以，當(dāng)函數(shù)具有較好的解析性質(zhì)時(shí)，插值方法比試探方法效果更好。2、插值法與試探法的區(qū)別非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第34頁!p1p2p3f(x)p(x)f1f2f3x1=ax2x3=bx*xP*二次插值函數(shù)圖例于是函數(shù)p(x)就是一個(gè)確定的二次多項(xiàng)式，稱二次插值函數(shù)，如圖所示，虛線部分即為二次插值函數(shù)非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第35頁!注意：若c2=0，則即

說明三個(gè)插值點(diǎn)位于同一條直線上，因此說明區(qū)間已經(jīng)很小，插值點(diǎn)非常接近，故可將x2、f2輸出作為最優(yōu)解。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第36頁!

以后，根據(jù)fp*相對(duì)于x2的位置，并比較fp*與f2

，區(qū)間的縮短可以分為以下四種情況。x1x2x3xP*f2fP*x1x1x1x2x2x2xP*xP*xP*x3x3x3f2f2f2fP*fP*fP*bacd非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第37頁!6、終止準(zhǔn)則

當(dāng)滿足給定精度時(shí)，計(jì)算終止，并令

x*xP*(k),f*

f(x*)7、二次插值算法流程圖非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第38頁!設(shè)f(x)在[a,b]上僅有一個(gè)單峰函數(shù)。其基本原理和步驟：1、給定初始區(qū)間，初始點(diǎn)x1及初始步長(zhǎng)h0>0。2、用加步長(zhǎng)的外推法縮短初始區(qū)間。x1x2x3x4h02h0附:外推內(nèi)插法非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第39頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第40頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第41頁!1、無約束問題的最優(yōu)性條件定理1定理2梯度為0的點(diǎn)稱為函數(shù)的駐點(diǎn)。駐點(diǎn)可能是極小點(diǎn)，也可能是極大點(diǎn)，也可能即不是極大也不是極小，這時(shí)稱為函數(shù)的鞍點(diǎn)。定理2說明：UMP問題的局部最優(yōu)解必是目標(biāo)函數(shù)的駐點(diǎn)。注：非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第42頁!關(guān)于梯度的復(fù)習(xí)：梯度是一個(gè)向量。n元函數(shù)f(x1,x2,…xn)在某點(diǎn)x處的梯度為：梯度的方向與函數(shù)f的等值線的一個(gè)法線方向相同，從較低的等值線指向較高的等值線。梯度的方向就是函數(shù)f的值增加最快的方向，其相反方向就是函數(shù)值降低最快的方向。2、最速下降法非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第43頁!最速下降法計(jì)算步驟選區(qū)初始點(diǎn)x0和精度計(jì)算是否停止，輸出x0求p0=計(jì)算t0,使計(jì)算x1=x0+t0p0非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第44頁!說明：x1x0垂直于目標(biāo)函數(shù)的等值線（圖中的虛線）在x0的切線；最速下降方法相鄰的兩個(gè)搜索方向是相互垂直的，即x1x0垂直x1x2；最速下降法解決UMP的缺陷：迭代點(diǎn)越靠近最優(yōu)解則目標(biāo)函數(shù)下降的速度越慢；優(yōu)點(diǎn)：迭代點(diǎn)列總是收斂的，而且計(jì)算過程簡(jiǎn)單。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第45頁!使d(k+1)與d(1),d(2),…,d(k)都共軛：

d(k+1)

TGd(j)=0,j=1,2,…,k……⑤Gram-Schmidt過程：i,j=1,2,…,k

記y(j)=▽f(x(j+1))-▽f(x(j))=G(x(j+1)-x(j))=αjGd(j)…….⑥

根據(jù)⑥式，有d(i)Ty(j)=αjd(i)TGd(j)=0,i≠j……⑦

根據(jù)④，⑤，⑥有

d(k+1)

Ty(j)=αjd(k+1)TGd(j)=0,j=1,2,…,k……⑧⑧′共軛梯度法非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第46頁!上式中由⑩式有：-▽f(x(k+1))T▽f(x(j+1))

=0

由⑥式有：βj(k)d(j)Ty(j)=βj(k)αjd(j)TGd(j)于是βj(k)=0故④式中只有βk(k)≠0,記βk=βk(k)

可得到公式：

d(k+1)=-▽f(x(k+1))+βkd(k)

當(dāng)j=k時(shí)，由⑧′,⑥式得：(11)注意：共軛梯度法非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第47頁!二、算法流程圖x(1),ε>0d(1)=-▽f(x(1)),k=1k=k+1k=1||▽f(x(k))||<ε?Stop.x(k)—解解minf(x(k)+λd(k))s.t.λ>0得λkx(k+1)=x(k)+λkd(k)

k=n?x(1)=x(n+1)d(1)=-▽f(x(1)),k=1求βkd(k+1)=-▽f(x(k+1))+βkd(k)yNyN重新開始非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第48頁!3、擬Newton方程：記：s(k)=x(k+1)-x(k),y(k)=▽f(x(k+1))-▽f(x(k))

當(dāng)f為二次函數(shù)時(shí)：f(x)=1∕2xTBx+cTx+b

▽f=Bx+c

有y(k)=Bs(k)

或s(k)=B-1y(k)

稱Hy=S或y=BS為擬Newton方程。顯然當(dāng)H正定時(shí),B-1=H.4、”近似”：對(duì)于f(x)的二階Taylor展式，舍去高階項(xiàng)，有y(k)≈▽2f(x(k))s(k)

或s(k)≈(▽2f

(x(k)))-1y(k)用矩陣B(k)或H(K)分別取代▽2f(x(k))或者(▽2f

(x(k)))-1使擬Newton方程成立，可看作是對(duì)▽2f(x(k))或(▽2f

(x(k)))-1的一種近似。此種近似H或B不唯一。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第49頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第50頁!計(jì)算過程：非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第51頁!約束極值問題

其中，x=(x1,x2,…

xn)T，f(x),gi(x),hj(x)為x的實(shí)值函數(shù)。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第52頁!基本概念與性質(zhì)由于可化為與討論約束條件時(shí)只討論不等式約束若x*微小變化，則約束條件沒有被破壞若x*有變化，則約束條件可能被破壞非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第53頁!若方向P在X0滿足

f(X0+λP)-f(X0)<0gi(X0+λP)>=0則P是X0的可行下降方向。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第54頁!K-T條件回顧高等數(shù)學(xué)中所學(xué)的條件極值：?jiǎn)栴}：求minf(x,y)S.t.ф(x,y)=0

引入Lagrange乘子λ

Lagrange函數(shù)L(x,y;λ)=f(x,y)+λф(x,y)非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第55頁!定理1對(duì)于若x*是局部最優(yōu)解,則非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第56頁!4、定理1的特例1非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第57頁!6、定理1的改進(jìn)：對(duì)于若x*是局部最優(yōu)解,則互補(bǔ)松緊條件非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第58頁!例：寫出K-T條件;求出相應(yīng)的K-T點(diǎn);判斷K-T點(diǎn)是不是問題的最優(yōu)解解：由于全部函數(shù)都是連續(xù)可微的，所以應(yīng)用以下K-T條件非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第59頁!利用互補(bǔ)松緊條件，可以求出K-T點(diǎn)：利用定理2，由于全部函數(shù)都連續(xù)可微，并且f和g都是凸函數(shù)，h是線性函數(shù)，所以K-T點(diǎn)就是整體最優(yōu)解。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第60頁!模型

非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第61頁!可行方向法迭代過程中所采用的搜索方向?yàn)榭尚蟹较?，所產(chǎn)生的迭代點(diǎn)始終在可行域內(nèi)，目標(biāo)函數(shù)值單調(diào)下降。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第62頁!懲罰函數(shù)法思想：利用問題中的約束函數(shù)做出適當(dāng)?shù)膸в袇?shù)的懲罰函數(shù)，然后在原來的目標(biāo)函數(shù)上加上懲罰函數(shù)構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把(MP)問題的求解轉(zhuǎn)換為求解一系列無約束非線性規(guī)劃問題。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第63頁!計(jì)算步驟非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第64頁!障礙函數(shù)法適合于不等式約束的最優(yōu)化問題其中都是連續(xù)函數(shù)，將模型的定義域記為非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第65頁!由于很小，則函數(shù)取值接近于f(x)，所以原問題可以歸結(jié)為如下規(guī)劃問題的近似解：

非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第66頁!例：某公司經(jīng)營(yíng)兩種設(shè)備，種設(shè)備每件售價(jià)30元，第二種設(shè)備每件售價(jià)為450元，根據(jù)統(tǒng)計(jì)，售出一件種設(shè)備所需營(yíng)業(yè)時(shí)間平均為0.5小時(shí)，第二種設(shè)備為（2＋0.25x2）小時(shí)，其中x2是第二種設(shè)備的售出數(shù)量，已知該公司在這段時(shí)間內(nèi)的總營(yíng)業(yè)時(shí)間為800小時(shí)，試決定使其營(yíng)業(yè)額最大的營(yíng)業(yè)計(jì)劃。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第67頁!AB圖解法可以給人以直觀概念，當(dāng)只有兩個(gè)自變量時(shí)，非線性規(guī)劃也像線性規(guī)劃一樣，可以利用圖解法。非線性規(guī)劃的圖解問題非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第68頁!非線性規(guī)劃的解的特點(diǎn)線性規(guī)劃：最優(yōu)解只能在其可行域的邊界上達(dá)到，特別是在可行域的頂點(diǎn)上達(dá)到；非線性規(guī)劃：可能在其可行域中的任意一點(diǎn)達(dá)到。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第69頁!局部極值定義非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第70頁!定理1：極值存在的必要條件非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第71頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第72頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第73頁!凸集、凸函數(shù)是研究非線性規(guī)劃問題所不可缺少的內(nèi)容，有關(guān)凸集的概念參見線性規(guī)劃部分，這里主要介紹凸函數(shù)的概念。1.3凸函數(shù)和凹函數(shù)非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第74頁!凸函數(shù)的性質(zhì)非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第75頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第76頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第77頁!

我們知道，一般來說，函數(shù)的局部極值并一定就是全局極值，而解非線性規(guī)劃時(shí)，所求最優(yōu)解必須是目標(biāo)函數(shù)在某個(gè)可行域上的全部極值。但對(duì)于一類所給凸規(guī)劃來說，下面將看到，其局部最優(yōu)解必定是全局最優(yōu)解。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第78頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第79頁!A非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第80頁!

所謂迭代法，就是從已知點(diǎn)X(0)出發(fā)，按照某種規(guī)則（即算法），求出比X(0)更好的解X(1)

，(若極小化問題，f(X(0))<f(X(1))),再按照此規(guī)則求出比X(1)

更好的點(diǎn)X(2)

，…如此重復(fù)這個(gè)過程，便產(chǎn)生一個(gè)點(diǎn)列{X(k)}，在一定條件下，下降迭代算法產(chǎn)生的點(diǎn)列收斂于原問題的解。即稱該點(diǎn)列{X(k)}收斂于X*.

由于算法產(chǎn)生的點(diǎn)列使目標(biāo)函數(shù)值逐步減小，稱這一算法為下降算法?；蚍蔷€性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第81頁!

一般地認(rèn)為，具有超線性收斂或二階收斂速度的算法是比較快速的算法。對(duì)于不同的問題，要根據(jù)具體情況來選擇算法，因?yàn)槲覀兪孪炔⒉恢雷顑?yōu)解，迭代到什么時(shí)候停止呢？常用的準(zhǔn)則是：非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第82頁!△可行方向：設(shè)∈S，d∈Rn,d≠0,若存在，使，稱d為點(diǎn)的可行方向。

同時(shí)滿足上述兩個(gè)性質(zhì)的方向稱下降可行方向。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第83頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第84頁!定理：設(shè)Ф：R→R

在[α，β]上單峰，α≤λ＜μ≤β

。那么

1°若Ф(λ)≥Ф(μ)，則Ф(ρ)≥Ф(μ)，ρ

∈[α，λ]；如左下圖

2°若Ф(λ)＜Ф(μ)，則Ф(ρ)≥Ф(λ)，ρ

∈[μ，β]；如右下圖§2一維搜索

α

λ

μ

β

αλμβ非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第85頁!

通過上面的討論，我們知道，只要在區(qū)間[a,b]內(nèi)取兩個(gè)不同的點(diǎn)，并算出這兩點(diǎn)的函數(shù)值，加以比較，就能把搜索區(qū)間[a,b]縮小成[a,b1]或[a1,b]。如果繼續(xù)縮小區(qū)間[a,b1](或[a1,b])，就需要在區(qū)間[a,b1](或[a1,b])內(nèi)取一點(diǎn)b2，并計(jì)算出f(b2)的值，并與f(a1)比較。若f(a1)<f(b2)，則x*[a,b2]f(a1)>f(b2)，則x*[a1,b1]非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第86頁!

因此，現(xiàn)在我們關(guān)心的是：進(jìn)行n次搜索后，能把區(qū)間[a,b]縮小到什么程度？或者說，計(jì)算n次函數(shù)值以后能把多長(zhǎng)的區(qū)間縮小成長(zhǎng)度為1的區(qū)間？用Fn表示計(jì)算n個(gè)函數(shù)值能縮短為單位區(qū)間的最大原區(qū)間長(zhǎng)度，顯然有

這是因?yàn)橹辽僖?jì)算兩次函數(shù)值才能縮短區(qū)間，只計(jì)算零次或一次函數(shù)值是不能縮短區(qū)間長(zhǎng)度的，故只有區(qū)間長(zhǎng)度本身等于1時(shí)才行?，F(xiàn)考慮計(jì)算函數(shù)值兩次的情形。我們把計(jì)算函數(shù)值的點(diǎn)稱為試算點(diǎn)或試點(diǎn)。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第87頁!利用公式可計(jì)算出Fn的值如下：n01234567891011Fn1123581321345589144這里的Fn就是通常所說的斐波那契數(shù)。由以上討論知，計(jì)算n次函數(shù)值所能獲得的最大縮短率（縮短后的長(zhǎng)度與原區(qū)間長(zhǎng)度的比）為1/Fn。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第88頁!分?jǐn)?shù)法求近似極小點(diǎn)的步驟（1）給出精度，求出使Fn>(b-a)/的最小整數(shù)n，由Fn=Fn-1+Fn-2，定出兩個(gè)試點(diǎn)x1=a+(b-a)Fn-2/Fn，x1’=a+(b-a)Fn-1/Fn。（2）計(jì)算f(x1)與f(x1’):若f(x1)<f(x1’)，取a=a1,x1’=b1

并令x2=a1+(b1-a1)Fn-3/Fn-1x2’=x1。若f(x1)>f(x1’)，取x1=a1,b=b1

并令x2=x1’x2’=a1+(b1-a1)Fn-2/Fn-1。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第89頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第90頁!

由上節(jié)討論知，用分?jǐn)?shù)法以n個(gè)試點(diǎn)來縮短某一區(qū)間時(shí)，區(qū)間長(zhǎng)度的次縮短率為Fn-1/Fn，其后各次分別為：Fn-2/Fn-1，F(xiàn)n-3/Fn-2，…，F(xiàn)1/F2，現(xiàn)將以上數(shù)列分為奇數(shù)項(xiàng)和偶數(shù)項(xiàng)，可以證明，這兩個(gè)數(shù)量收斂于同一個(gè)極限2.20.618法（黃金分割法）以不變的區(qū)間縮短率0.618代替分?jǐn)?shù)法每次不同的縮短率，就得到黃金分割法（0.618法）。它可以看成是分?jǐn)?shù)法的近似，實(shí)現(xiàn)起來比較容易，效果也好。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第91頁!例：為了提高某種化工產(chǎn)品的質(zhì)量指標(biāo)，需要在制作過程中加入某種原料，已知其最佳加入量在1000克到2000克之間的某一點(diǎn)，現(xiàn)在通過實(shí)驗(yàn)的方法找到該點(diǎn)。按0.618法來獲取該點(diǎn)。先做次試驗(yàn)，其加入量為1000＋0.382(2000－1000)=1382g再做第二次試驗(yàn)，加入量為1000＋0.618(2000－1000)=1618g比較這兩次的試驗(yàn)結(jié)果。1000(1)1382(2)16182000如果第(2)點(diǎn)較第(1)點(diǎn)效果好，則去掉1000至1382這段，然后在留下的一段中再找出第(2)點(diǎn)的對(duì)稱點(diǎn)，做第三次試驗(yàn)，其加入量為1382＋0.618(2000－1382)=1764g非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第92頁!例：用黃金分割法求函數(shù)非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第93頁!上面我們所討論的方法，只是對(duì)一些點(diǎn)的函數(shù)值的大小進(jìn)行比較，而函數(shù)本身并沒有得到充分利用，至于函數(shù)的一些解析性質(zhì)，更是毫無利用，下面介紹的牛頓法當(dāng)函數(shù)性質(zhì)具有較好的解析性質(zhì)時(shí)，計(jì)算效果要比分?jǐn)?shù)法、0.618法更好?，F(xiàn)在仍設(shè)f(x)在[a,b]上僅有一個(gè)極小點(diǎn)的單峰函數(shù)，且具有二階導(dǎo)數(shù)。我們知道，如果函數(shù)f(x)在x*處取極小值，則必有f′(x)=0，因此求此函數(shù)極小點(diǎn)，只需求出f′(x)在(a,b)內(nèi)的零點(diǎn)即可。附:牛頓法（Newton）（切線法）非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第94頁!Newton法算法框圖初始x1,ε1,ε2>0k=1︱f′(xk)︱<ε1?停；解xk

yNf″(xk)>0?N停，失敗Yxk

+1=xk-f′(xk)／f″(xk)|xk

+1-xk|<ε2

YNk=k+1非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第95頁!例：求minf(x)=arctantdt

解：f′(x)=arctanx,f″(x)=1／(1+x2)

迭代公式：xk

+1=xk-(1+x2)arctanxk

取x1=1，計(jì)算結(jié)果：

k

xk

f′(xk)1／f″(xk)110.785422-0.5708-0.51871.325830.1169-0.11641.01374-0.001095-0.001095x4≈x*=0

取x1=2，計(jì)算結(jié)果如下：

k

xk

f′(xk)1／f″(xk)121.107152-3.5357-1.295213.50313.95不收斂。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第96頁!1、插值法概念

假定我們給定的問題是在某一確定區(qū)間內(nèi)尋求函數(shù)的極小點(diǎn)的位置，但是沒有函數(shù)表達(dá)式，只有若干試驗(yàn)點(diǎn)處的函數(shù)值。我們可以根據(jù)這些函數(shù)值，構(gòu)成一個(gè)與原目標(biāo)函數(shù)相接近的低次插值多項(xiàng)式，用該多項(xiàng)式的最優(yōu)解作為原函數(shù)最優(yōu)解的近似解，這種方法是用低次插值多項(xiàng)式逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)的近似求解方法，稱為插值方法或函數(shù)逼近法。上面的牛頓法需要計(jì)算f(x)的一階導(dǎo)數(shù)、二階導(dǎo)數(shù)，當(dāng)f(x)很復(fù)雜時(shí)，計(jì)算起來相當(dāng)困難。拋物線法是一種多項(xiàng)式逼近，即用一個(gè)二次多項(xiàng)式p(x)來逼近所給的函數(shù)f(x)，并用p(x)的極小點(diǎn)來近似f(x)的極小點(diǎn)，在整個(gè)計(jì)算過程中，只需要計(jì)算f(x)的值。其基本思想就是用二次三項(xiàng)式來逼近目標(biāo)函數(shù)。附:拋物線法（插值法）非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第97頁!

計(jì)算函數(shù)值f

1=f(x1)、f

2=

f(x2)、f

3=f(x3)

過函數(shù)曲線上的三點(diǎn)P1(x1,f

1)、P2(x2,f2)、P3(x3,f

3)

作二次插值多項(xiàng)式

p(x)=Ax2+Bx+C

它應(yīng)滿足條件

p(x1)=Ax12+Bx1+C1=f

1

p(x2)=Ax22+Bx2+C=f

2

p(x3)=Ax32+Bx3+C=f

3

解方程組，得待定系數(shù)A、B、C分別為

非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第98頁!

令插值函數(shù)p(x)的一階導(dǎo)數(shù)為0，即

p′(x)=2Ax+B=0

得p(x)極小點(diǎn)為

xp*=B/2A

代入A、B得

則

令非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第99頁!

5、區(qū)間的縮短為求得滿足收斂精度要求的最優(yōu)點(diǎn)，往往需要多次進(jìn)行插值計(jì)算，搜索區(qū)間不斷縮短，使xp*不斷逼近原函數(shù)的極小點(diǎn)x*。次區(qū)間縮短的方法是，計(jì)算xp*點(diǎn)的函數(shù)值fp*，比較fp*與f2，取其中較小者所對(duì)應(yīng)的點(diǎn)作為新的x2，以此點(diǎn)的左右兩鄰點(diǎn)作為新的x1和x3，得到縮短后的新區(qū)間[x1，x3]，如圖所示。新區(qū)間x1=ax2x3=bx*xP*x1x2x3非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第100頁!入口xp*>x2?f2*>fP*?f2<fP*?x1xp*f1

fP*x3x2f3

f2x2xp*f2

fP*x1x2f1

f2x2xp*f2

fP*x3xp*f3

fP*出口YYYNNNabcd區(qū)間縮短流程圖非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第101頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第102頁!x1x2x3x4h02h0h04h0非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第103頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第104頁!無約束最優(yōu)化方法本節(jié)討論n元函數(shù)的無約束非線性規(guī)劃問題：求解此類模型(UMP)的方法稱為無約束最優(yōu)化方法。無約束最優(yōu)化方法通常有兩類：解析法：要使用導(dǎo)數(shù)的方法；直接法：無須考慮函數(shù)是否可導(dǎo)，直接使用函數(shù)值。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第105頁!定理3定理4非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第106頁!最速下降法又稱為梯度法，由Cauchy于1847年給出。最速下降法解決的是具有連續(xù)可微的目標(biāo)函數(shù)的UMP問題。最速下降法的基本思想：從當(dāng)前點(diǎn)xk出發(fā)尋找使得目標(biāo)函數(shù)下降最快的方向，即負(fù)梯度方向。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第107頁!例解：非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第108頁!共軛梯度法一、共軛梯度法的方向：

設(shè)f(x)=(1/2)xTGx+bTx+cGn×n對(duì)稱正定，b∈Rn,從最速下降方向開始，構(gòu)造一組共軛方向：設(shè)初始點(diǎn)x(1),取d(1)=-▽f(x(1))……①(最速下降方向)

設(shè)k≥1,已得到k個(gè)相互共軛的方向d(1),d(2),…,d(k),以及，由x(1)開始依次沿上述方向精確一維搜索得到點(diǎn)x(2),…，x(k),x(k+1).即有下式：

x(i+1)=x(i)+αid(i),i=1,2,…,k……②

精確一維搜索保證方向?qū)?shù)為0：▽fT(x(i+1))d(i)=0,i=1,2,…,k……③

在x(i+1)點(diǎn)構(gòu)造新方向d(k+1)為-▽f(x(k+1))與d(1),d(2),…,d(k)的組合：④非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第109頁!j≤k,i<j有▽f(x(j+1))Td(i)=0……⑨由⑥式

由⑨式

▽f(x(j+1))T▽f(x(i))=0i<j≤k……⑩(由④式)根據(jù)⑧及⑥得：j=1,2,…,k-1-▽f(x(k+1))T[▽f(x(j+1))

-▽f(x(j))]+βj(k)d(j)Ty(j)=0共軛梯度法非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第110頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第111頁!變尺度法一、變尺度法的基本思路：(f)minf(x),f:Rn→R1、基本思想：

用對(duì)稱正定矩陣H(k)近似▽2f(x(k))的逆,而H(k)的產(chǎn)生從給定H(1)開始逐步修整得到。2、算法框圖：x(1),H(1)對(duì)稱ε>0,k=1d(k)=-H(k)▽f(x(k))一維搜索得λkx(k+1)=x(k)+λkd(k)||x(k+1)-x(k)||<ε?