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

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

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

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

由這兩個例子可以看出，這兩個例子在高等數(shù)學中代表了兩類不同類型的極值問題。例1是無條件極值；例2是有條件極值。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第4頁!ABDC非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第5頁!1.2極值問題線性規(guī)劃：目標函數(shù)是線性函數(shù)，可行域為凸集，求出的最優(yōu)解就是整個可行域上的全局最優(yōu)解。非線性規(guī)劃：有時求出的解是一部分可行域上的極值點，但并不一定是整個可行域上的全局最優(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ù)圖形上任意兩點的連線處處不在這個函數(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頁!設算法產(chǎn)生的點列{x(k)},收斂到解X*,且X(k)≠X*，k，若存在>0,及一個與迭代次數(shù)k無關的常數(shù)q>0，使1.線性收斂：當＝1,q>0時稱為線性收斂速度。2.超線性收斂：當1<<2,q>0，或＝1,q＝0時，稱為超線性收斂速度3.二階收斂：當=2

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

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

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

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

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

xn-1=xn-1’=(an-2+bn-2)/2這時無法比較函數(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頁!再比較次與第三次的試驗結果。1000(1)1382(2)16182000(3)1764如果仍然是第(2)點較第(3)點效果好，則去掉1764至2000這一段，然后在留下的一段中再找出第(4)點的對稱點，做第四次試驗，其加入量為1382＋0.618(1764－1382)=1528g1000(1)1382(2)16182000(3)1764(4)1528如果仍然是第(4)點較第(2)點效果好，則去掉1618至1764這一段，對留下的1382至1618這一段中繼續(xù)試驗下去就能找到最優(yōu)點，這樣可以用最少的試驗次數(shù)找到最佳加入量。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第29頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第30頁!對f

在xk

點展開：

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

取二次式（略去高階項）：

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

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

得xk

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

取xk

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

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

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

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

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

當滿足給定精度時，計算終止，并令

x*xP*(k),f*

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

當j=k時，由⑧′,⑥式得：(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))

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

▽f=Bx+c

有y(k)=Bs(k)

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

稱Hy=S或y=BS為擬Newton方程。顯然當H正定時,B-1=H.4、”近似”：對于f(x)的二階Taylor展式，舍去高階項，有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方程成立，可看作是對▽2f(x(k))或(▽2f

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

其中，x=(x1,x2,…

xn)T，f(x),gi(x),hj(x)為x的實值函數(shù)。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第52頁!基本概念與性質(zhì)由于可化為與討論約束條件時只討論不等式約束若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ù)學中所學的條件極值：問題：求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對于若x*是局部最優(yōu)解,則非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第56頁!4、定理1的特例1非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第57頁!6、定理1的改進：對于若x*是局部最優(yōu)解,則互補松緊條件非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第58頁!例：寫出K-T條件;求出相應的K-T點;判斷K-T點是不是問題的最優(yōu)解解：由于全部函數(shù)都是連續(xù)可微的，所以應用以下K-T條件非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第59頁!利用互補松緊條件，可以求出K-T點：利用定理2，由于全部函數(shù)都連續(xù)可微，并且f和g都是凸函數(shù)，h是線性函數(shù)，所以K-T點就是整體最優(yōu)解。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第60頁!模型

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

非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第66頁!例：某公司經(jīng)營兩種設備，種設備每件售價30元，第二種設備每件售價為450元，根據(jù)統(tǒng)計，售出一件種設備所需營業(yè)時間平均為0.5小時，第二種設備為（2＋0.25x2）小時，其中x2是第二種設備的售出數(shù)量，已知該公司在這段時間內(nèi)的總營業(yè)時間為800小時，試決定使其營業(yè)額最大的營業(yè)計劃。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第67頁!AB圖解法可以給人以直觀概念，當只有兩個自變量時，非線性規(guī)劃也像線性規(guī)劃一樣，可以利用圖解法。非線性規(guī)劃的圖解問題非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第68頁!非線性規(guī)劃的解的特點線性規(guī)劃：最優(yōu)解只能在其可行域的邊界上達到，特別是在可行域的頂點上達到；非線性規(guī)劃：可能在其可行域中的任意一點達到。非線性規(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ī)劃部分，這里主要介紹凸函數(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ī)劃時，所求最優(yōu)解必須是目標函數(shù)在某個可行域上的全部極值。但對于一類所給凸規(guī)劃來說，下面將看到，其局部最優(yōu)解必定是全局最優(yōu)解。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第78頁!非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第79頁!A非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第80頁!

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

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

更好的點X(2)

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

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

一般地認為，具有超線性收斂或二階收斂速度的算法是比較快速的算法。對于不同的問題，要根據(jù)具體情況來選擇算法，因為我們事先并不知道最優(yōu)解，迭代到什么時候停止呢？常用的準則是：非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第82頁!△可行方向：設∈S，d∈Rn,d≠0,若存在，使，稱d為點的可行方向。

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

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

。那么

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

∈[α，λ]；如左下圖

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

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

α

λ

μ

β

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

通過上面的討論，我們知道，只要在區(qū)間[a,b]內(nèi)取兩個不同的點，并算出這兩點的函數(shù)值，加以比較，就能把搜索區(qū)間[a,b]縮小成[a,b1]或[a1,b]。如果繼續(xù)縮小區(qū)間[a,b1](或[a1,b])，就需要在區(qū)間[a,b1](或[a1,b])內(nèi)取一點b2，并計算出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)在我們關心的是：進行n次搜索后，能把區(qū)間[a,b]縮小到什么程度？或者說，計算n次函數(shù)值以后能把多長的區(qū)間縮小成長度為1的區(qū)間？用Fn表示計算n個函數(shù)值能縮短為單位區(qū)間的最大原區(qū)間長度，顯然有

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

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，計算結果如下：

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

計算函數(shù)值f

1=f(x1)、f

2=

f(x2)、f

3=f(x3)

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

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

3)

作二次插值多項式

p(x)=Ax2+Bx+C

它應滿足條件

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)的一階導數(shù)為0，即

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

得p(x)極小點為

xp*=B/2A

代入A、B得

則

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

5、區(qū)間的縮短為求得滿足收斂精度要求的最優(yōu)點，往往需要多次進行插值計算，搜索區(qū)間不斷縮短，使xp*不斷逼近原函數(shù)的極小點x*。次區(qū)間縮短的方法是，計算xp*點的函數(shù)值fp*，比較fp*與f2，取其中較小者所對應的點作為新的x2，以此點的左右兩鄰點作為新的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)化方法通常有兩類：解析法：要使用導數(shù)的方法；直接法：無須考慮函數(shù)是否可導，直接使用函數(shù)值。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第105頁!定理3定理4非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第106頁!最速下降法又稱為梯度法，由Cauchy于1847年給出。最速下降法解決的是具有連續(xù)可微的目標函數(shù)的UMP問題。最速下降法的基本思想：從當前點xk出發(fā)尋找使得目標函數(shù)下降最快的方向，即負梯度方向。非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第107頁!例解：非線性規(guī)劃—無約束問題共130頁，您現(xiàn)在瀏覽的是第108頁!共軛梯度法一、共軛梯度法的方向：

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

設k≥1,已得到k個相互共軛的方向d(1),d(2),…,d(k),以及，由x(1)開始依次沿上述方向精確一維搜索得到點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)點構造新方向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、基本思想：

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