機械優(yōu)化設(shè)計太原科技大學(xué)張學(xué)良機械優(yōu)化設(shè)計太原科技大學(xué)1第五章無約束優(yōu)化的間接搜索法

間搜索法是指搜索方向S(k)的構(gòu)建利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)信息的無約束優(yōu)化方法，如梯度法、牛頓法、共軛梯度法、變尺度法。

X(k+1)=X(k)+(k)

S(k)

(k=0,1,2,…)第五章無約束優(yōu)化的間接搜索法間搜索法是指2基本思想

§5.1

梯度法（最速下降法、負(fù)梯度法）利用負(fù)梯度方向作為迭代計算的搜索方向，即S(k)=－▽f(X(k))或S(k)=－▽f(X(k))/||▽f(X(k))||迭代計算公式

X(k+1)=X(k)+(k)[－▽f(X(k))]或X(k+1)=X(k)+(k)[－▽f(X(k))]基本思想§5.1梯度法（最速下降法、負(fù)梯度法3

舉例：

用梯度法求目標(biāo)函數(shù)f(X)=x12+4x22的無約束最優(yōu)解。初始點X1(0)=

[00

]T

，X2(0)=

[22

]T。舉例：用梯度法求目標(biāo)函數(shù)4基本思想和基本算法

§5.2

牛頓法在點X(k)的鄰域內(nèi)，用一個二次函數(shù)(X)來近似代替原目標(biāo)函數(shù)，并以

(X

)的極小點作為原目標(biāo)函數(shù)的極小點的近似值，若不滿足收斂精度要求，則將該近似極小點作為下一次迭代的初始點。如此反復(fù)迭代，直到所求的近似極小點滿足收斂精度要求為止。基本思想和基本算法§5.2牛頓法5

f(X)

f(X(k))+T

f(X(k))

(X-

X(k))+0.5(X-

X(k))T2

f(X(k))

(X-

X(k))=

(X)

(X)的極小點應(yīng)滿足：

(X)=0即f(X(k))+2

f(X(k))

(X-

X(k))=02

f(X(k))

(X-

X(k))=-

f(X(k))當(dāng)2

f(X(k))

正定且有逆陣時，上式兩邊同時左乘[2

f(X(k))

]-1，得X

=X(k)

-[2

f(X(k))

]-1

f(X(k))f(X)f(X(k))+6牛頓法的迭代公式為X(k+1)=X(k)

-[2

f(X(k))

]-1

f(X(k))

X(k+1)=X(k)+(k)

S(k)牛頓方向：S(k)=-[2

f(X(k))

]-1

f(X(k))迭代步長：(k)=1修正牛頓法（又稱阻尼牛頓法）的迭代公式為X(k+1)=X(k)

-

(k)[2

f(X(k))

]-1

f(X(k))阻尼因子：(k)

牛頓法的迭代公式為X(k+1)=X(k)7計算步驟及算法框圖

1）

任選初始點X(0)，給定收斂精度>0，k=0；

2）

計算X(k)點的梯度f(X(k))及其模；

3）檢驗終止條件：||f(X(k))||≤？

若滿足，則輸出最優(yōu)解：X*

=X(k)，

f*

=f(X*)，并終止迭代計算；否則，繼續(xù)下一步迭代計算；計算步驟及算法框圖1）任選初始點8

4）計算X(k)點的海賽矩陣2

f(X(k))及其逆矩陣[2

f(X(k))]-1

5）沿牛頓方向S(k)=-[2

f(X(k))

]-1

f(X(k))進行一維搜索，求最佳步長(k)；

6）令X(k+1)=X(k)+(k)

S(k)，并令kk+1，轉(zhuǎn)2），重復(fù)上述迭代計算過程。4）計算X(k)點的海賽矩陣2f(X(k))9舉例：

用牛頓法求目標(biāo)函數(shù)f(X)=x12+4x22的無約束最優(yōu)解。初始點X1(0)=

[00

]T

，X2(0)=

[22

]T。解：

f(X)=

[2x18x2

]T2

f(X)=008[2

f(X)]-1=0.5000.125f(X1(0))=

[00

]Tf(X2(0))=

[416

]TX1(1)=X1(0)-[2f(X1(0))]-1

f(X1(0))=[00

]T-0.5000.125[00

]=[00

]T舉例：用牛頓法求目標(biāo)函數(shù)解：f(X)=[2x10X2(1)=X2(0)-[2f(X2(0))]-1

f(X2(0))=[22

]T-0.5000.125[416

]=[00

]T可見，X2(1)=X1(0)=[00

]T就是目標(biāo)函數(shù)的理論極小點，僅僅迭代了一次，與初始點的選擇無關(guān)。由于一般函數(shù)在極小點附近呈現(xiàn)出較強的二次性，所以牛頓法在極小點附近收斂速度較快。但無論是牛頓法還是修正牛頓法在每次迭代計算時都要計算目標(biāo)函數(shù)的海賽X2(1)=X2(0)-[2f(X2(0))]-111矩陣及其逆陣，因此計算工作量很大，特別是矩陣求逆，當(dāng)維數(shù)高時工作量更大，且當(dāng)海賽矩陣為奇異陣時，其逆陣不存在，無法使用牛頓法，所以在實際使用中受到一定限制。另外，從計算機存儲方面考慮，牛頓法所需要的存儲量是很大的。若能設(shè)法構(gòu)造一個矩陣來逼近海賽矩陣的逆陣而避免計算海賽矩陣及其逆陣，這樣的方法統(tǒng)稱為擬牛頓法。如只用梯度信息但比梯度法快的共軛梯度法，以及針對牛頓法提出的變尺度法等。矩陣及其逆陣，因此計算工作量很大，特別是矩陣求逆，當(dāng)維數(shù)高時12基本思想§5.3

共軛梯度法共軛梯度法屬于共軛方向法中的一種方法。它是利用目標(biāo)函數(shù)在迭代點X(k)的梯度來構(gòu)造共軛搜索方向的，具有二次收斂性。共軛梯度法搜索的第一步沿負(fù)梯度方向，以后各步沿與上次搜索方向相共軛的方向進行搜索。共軛梯度法的關(guān)鍵是如何在迭代過程中不斷生成共軛搜索方向基本思想§5.3共軛梯度法共軛梯度法13共軛梯度法共軛搜索方向的生成考慮二次函數(shù)

f(X)=0.5XTH

X

+BT

X+C

從X(k)出發(fā)，沿H的某一共軛方向S(k)作一維搜索得到X(k+1)，即X(k+1)

－X(k)=(k)

S(k)（1）將f(X)在X(k)和X(k+1)兩點處的梯度表示并記作g(k)=

▽f(X(k))=H

X(k)

+B（2）g(k+1)=

▽f(X(k+1))=H

X(k+1）

+B（3）共軛梯度法共軛搜索方向的生成考慮二次函數(shù)從14（3）-（2）得g(k+1)－g(k)=H

(

X(k+1)

－X(k))=(k)

H

S(k)（4）（4）式兩邊同時左乘[S(j)]T，有[S(j)]T[g(k+1)－g(k)]=(k)

[S(j)]TH

S(k)=0若S(j)和S(k)關(guān)于H共軛，則有[S(j)]THS(k)=0即[S(j)]T[g(k+1)－g(k)]=0（5）式（5）就是共軛方向與梯度之間的關(guān)系。它表明沿方向S(k)進行一維搜索，其終點X(k+1)與始點X(k)梯度之差(g(k+1)－g(k))與S(k)的共軛（3）-（2）得g(k+1)－g(k)=H(15方向S(j)與正交。共軛梯度法就是利用這個性質(zhì)做到不必計算矩陣H就能求得共軛方向的。1）設(shè)初始點X(0)，第一個搜索方向S(0)取X(0)點的負(fù)梯度方向-g(0)。即S(0)=-g(0)沿S(0)進行一維搜索，得X(1)

=X(0)+(0)

S(0)，并計算X(1)點的梯度g(1)。那么，g(1)與S(0)有什么關(guān)系呢？X(0)g(1)-g(0)X(1)二者正交，即[g(1)]TS(0)=0或[S(0)]Tg(1)

=0因此，S(0)與g(1)構(gòu)成平面正交系。方向S(j)與正交。共軛梯度法就是利用這個性質(zhì)做到不必計算矩162）在S(0)與g(1)構(gòu)成的平面正交系中求S(0)的共軛方向S(1)，以此作為下一步迭代計算的搜索方向。取S(1)為S(0)與g(1)的線性組合，即

S(1)=-g(1)+(0)S(0)

其中，(0)為待定常數(shù)，可以利用共軛方向與梯度之間的關(guān)系求得。由[S(1)]T[g(1)－g(0)]=0有[-g(1)+(0)S(0)]T[g(1)－g(0)]=0展開，得-[g(1)]Tg(1)+[g(1)]Tg(0)+(0)[S(0)]Tg(1)-(0)[S(0)]Tg(0)=02）在S(0)與g(1)構(gòu)成的平面正交系中求S(017所以-[g(1)]Tg(1)-(0)[S(0)]Tg(0)=0所以(0)=-[g(1)]Tg(1)/[S(0)]Tg(0)

=

[g(1)]Tg(1)/[g(0)]Tg(0)=

||g(1)||2

/||g(0)||2S(1)=-g(1)+||g(1)||2

/||g(0)||2

S(0)沿S(1)進行一維搜索，得X(2)

=X(1)+(1)

S(1)，并計算X(2)點的梯度g(2)，則有[S(1)]Tg(2)=0所以-[g(1)]Tg(1)-18故有[-g(1)+(0)S(0)]T

g(2)=0

（6）

因為S(0)和S(1)共軛，所以有[S(0)]T[g(2)－g(1)]=0因為[S(0)]T

g(1)=0所以[S(0)]T

g(2)=0即g(2)與g(0)正交。所以[S(0)]T

g(2)=0由式（6）得[g(1)]T

g(2)=0可見，g(0)、g(1)、g(2)構(gòu)成一個空間正交系。故有[-g(1)+(0193）在g(0)、g(1)、g(2)構(gòu)成的空間正交系中求與S(0)及S(1)均共軛的方向S(2)，以此作為下一步迭代計算的搜索方向。仍取S(2)為g(0)、g(1)、g(2)的線性組合，即

S(2)=-g(2)+(1)g(1)+(0)g(0)

其中，(1)、(0)為待定常數(shù)，可以利用共軛方向與梯度之間的關(guān)系求得。[S(2)]T[g(1)－g(0)]=0[S(2)]T[g(2)－g(1)]=03）在g(0)、g(1)、g(2)構(gòu)成的空間正交系20即[-g(2)+(1)g(1)+(0)g(0)]T[g(1)－g(0)]=0[-g(2)+(1)g(1)+(0)g(0)]T[g(2)－g(1)]=0

所以(1)[g(1)]Tg(1)-

(0)[

g(0)]Tg(0)]=0-[g(2)]Tg(2)-

(1)[g(1)]Tg(1)=0

令(1)=-(1)

得(1)=-(1)=

[g(2)]Tg(2)/[g(1)]Tg(1)

=||g(2)||2

/||g(1)||2(0)=

(1)[g(1)]Tg(1)/[g(0)]Tg(0)

=-(1)

(0)即[-g(2)+(1)g(1)+21因此S(2)=-g(2)+(1)g(1)+(0)g(0)

=-g(2)-(1)g(1)-(1)(0)g(0)=-g(2)+(1)[-

g(1)-(0)g(0)]=-g(2)+(1)S(1)故S(2)=-g(2)+||g(2)||2/||g(1)||2S(1)再沿S(2)進行一維搜索，得X(3)

=X(2)+(2)

S(2)，如此繼續(xù)下去，可以求得共軛方向的遞推公式為

S(k+1)=-g(k+1)+||g(k+1)||2/||g(k)||2S(k)(k=0,1,2,…,n-1)因此S(2)=-g(2)+(1)22沿著這些共軛搜索方向一直搜索下去，直到最后迭代點處梯度的模小于給定的允許值為止。若目標(biāo)函數(shù)為非二次函數(shù)，經(jīng)n次搜索還未達到最優(yōu)點時，則以最后得到的點作為初始點，重新計算共軛方向，一直到滿足精度要求為止。共軛梯度法的計算步驟及算法框圖1）給定初始點X(0)及收斂精度>0，k=0；2）取S(0)=－▽f(X(0))；沿著這些共軛搜索方向一直搜索下去，直到最后迭233）X(k+1)

=X(k)+(k)

S(k)(k=0,1,2,…,n)(k)

為一維搜索所得的最佳步長。4）判斷||▽f(X(k+1))||≤?

若滿足，則輸出X

*=

X(k+1)

和f

*=

f(X

*)否則，轉(zhuǎn)下一步；5）判斷k+1=n?

若k+1=n，令X(0)

=

X(k+1)

，轉(zhuǎn)2）；若k+1<n，則計算

(k)=||▽f(X(k+1))||2/||▽f(X(k))||23）X(k+1)=X(k)+(k)S(24

S(k+1)=-▽f(X(k+1))+(k)S(k)并令kk+1，轉(zhuǎn)3）。1）盡管理論上可以證明目標(biāo)函數(shù)為n維正定二次函數(shù)時，共軛梯度法只需要n次迭代就可以達到最優(yōu)點，但由于計算機的舍入誤差，實際計算往往要多進行若干次才能得到滿足精度要求的結(jié)果；而對于一般的目標(biāo)函數(shù)，迭代次數(shù)將更多。關(guān)于共軛梯度法的說明S(k+1)=-▽f(X(k252）由于n維設(shè)計空間中最多只能有n個線性無關(guān)的向量，所以n維優(yōu)化問題的共軛方向最多只有n個。因此，共軛梯度法進行n步搜索后，若仍不滿足精度要求，繼續(xù)產(chǎn)生共軛方向S(n+1)進行迭代搜索是沒有意義的（效果很差），而應(yīng)令X(0)

=

X(n)

，重新開始新一輪的共軛梯度法迭代搜索。實踐證明，這樣處理一般都可以取得較好的效果。2）由于n維設(shè)計空間中最多只能有n個線性無關(guān)的向26舉例：

用共軛梯度法求目標(biāo)函數(shù)f(X)=x12+4x22的無約束最優(yōu)解。初始點X(0)=

[22

]T，=0.01。解：

f(X)=

[2x18x2

]TS(0)=-f(X(0))=

[-4-16

]TX(1)=X(0)-(0)f(X(0))=[22

]T

-(0)[416]T=[2-4(0)2-16(0)]T

f(X(1))

=(2-4(0))2+4(2-16(0))2據(jù)df(X(1))/d(0)=0得(0)=0.13076923X(1)=[1.476923077

-0.09230768

]T

舉例：用共軛梯度法求目標(biāo)函數(shù)解：f(X)=[27f(X(1))=

[2.953846154-0.73846144

]T(0)=||▽f(X(1))||2/||▽f(X(0))||2=0.034082837

S(1)=-▽f(X(1))+(0)S(0)

=-[2.953846154-0.73846144

]T

+0.034082837[-4-16

]T

=[-3.090177510.193136016

]TX(2)=X(1)+(1)S(1)=[1.476923077

-0.09230768

]T

+

(1)[-3.090177510.193136016

]Tf(X(1))=[2.95384615428據(jù)df(X(2))/d(1)=0得(1)=0.477941179X(2)=[6×10-9-2.4×10-8]T

≈[0

0]T

||▽f(X(2))||≈0<=0.01故最優(yōu)解為

X*=X(2)=[0

0]Tf(X*)=0據(jù)df(X(2))/d(1)=0得29DFP變尺度法的基本思想§5.4

變尺度法它是基于牛頓法的思想，并對其做了重要的改進后的一類方法。它不需要計算二階導(dǎo)數(shù)矩陣及其逆陣，又比共軛梯度法有更好的收斂性，對較高維數(shù)的無約束優(yōu)化問題有明顯的優(yōu)越性。梯度法遠(yuǎn)離最優(yōu)點時，對突破函數(shù)的非二次性極為有利（即收斂速度快），但迭代點接近最優(yōu)點時收斂速度慢；而牛頓法則正好相反，它具有二次收斂性，接近最優(yōu)點時DFP變尺度法的基本思想§5.4變尺度法30收斂極快，但它需要計算海賽矩陣及其逆陣，計算工作量比梯度法大為增加。若能構(gòu)造一種算法，它兼有梯度法和牛頓法各自的優(yōu)點，那么這種算法一定比梯度法和牛頓法更有效，于是便產(chǎn)生了變尺度法。梯度法：X(k+1)=X(k)

-

(k)

f(X(k))牛頓法：X(k+1)=X(k)

-

(k)[2

f(X(k))

]-1

f(X(k))變尺度法的迭代公式:X(k+1)=X(k)

-

(k)A(k)

f(X(k))A(k)

為人為構(gòu)造的對稱方陣，稱為構(gòu)造矩陣，它迭代點位置的變化而變化。收斂極快，但它需要計算海賽矩陣及其逆陣，計算工作量比梯度法大31變尺度法的迭代公式:X(k+1)=X(k)

-

(k)A(k)

f(X(k))若在迭代初始時，A(k)

=I，則上式與梯度法的迭代公式相同，可使迭代點遠(yuǎn)離最優(yōu)點時收斂速度加快。以后隨著迭代過程的進行，不斷地修正構(gòu)造矩陣，使它逐步逼近函數(shù)在迭代點X(k)處的海賽矩陣的逆陣[2f(X(k))]-1，這樣當(dāng)?shù)c逼近最優(yōu)點時，迭代搜索方向就趨于牛頓方向，因此收斂速度極快。變尺度法的搜索方向為:S(k)=-A(k)

f(X(k))稱為逆牛頓方向。變尺度法的迭代公式:32構(gòu)造矩陣可看成是搜索過程中的一種尺度變換矩陣，它從一次迭代到另一次迭代是變化的，所以又稱為變尺度矩陣。要實現(xiàn)上述變尺度法的基本思想，關(guān)鍵在于如何產(chǎn)生變尺度矩陣。DFP變尺度法中變尺度矩陣系列的產(chǎn)生∵變尺度矩陣A(k)是隨迭代點X(k)變化而變化，初始變尺度矩陣A(0)需預(yù)先選定，且必須是正定對稱矩陣，一般取A(0)=I。∴A(k)是一個序列，記為{A(k)}（k=0,1,2,…）構(gòu)造矩陣可看成是搜索過程中的一種尺度變換矩陣33假定在迭代過程中已構(gòu)造得到矩陣A(k)，則第(k+1)次迭代所需的變尺度矩陣A(k+1)可用如下簡單形式的迭代公式產(chǎn)生。1）變尺度陣A(k+1)應(yīng)滿足擬牛頓條件A(k+1)=A(k)+A(k)

A(k)為校正矩陣對于一般二次函數(shù)

f(X)=0.5XTH

X

+BT

X+C

其梯度記為g(k)=

▽f(X(k))=H

X(k)

+B（2）g(k+1)=

▽f(X(k+1))=H

X(k+1）

+B（3）假定在迭代過程中已構(gòu)造得到矩陣A(k)，則第34g(k+1)-g(k)=g(k)=H

(

X(k+1)

-X(k))=H

X(k)

若H可逆，則由上式可得

H-1g(k)=

X(k)

為使A(k)序列最終逼近H

-1，則A(k+1)矩陣應(yīng)滿足擬牛頓條件

A(k+1)g(k)=

X(k)2）校正矩陣A(k)的構(gòu)建校正矩陣A(k)只依賴于本次迭代的矢量差

X(k)=X(k+1)

-X(k)和相應(yīng)的梯度差g(k)。g(k+1)-g(k)=g(k)=H(35

將A(k+1)=A(k)+A(k)代入擬牛頓條件，得

（A(k)+A(k)）g(k)=

X(k)展開，得A(k)g(k)+A(k)g(k)=

X(k)在DFP算法中，令A(yù)(k)

=akukukT+bkvkvkTak、bk—待定常數(shù)，uk、vk—n維待定矢量所以，有akukukTg(k)+bkvkvkTg(k)=

X(k)-A(k)g(k)將A(k+1)=A(k)+A(k)36uk、vk的取法有多種，這里令

akukukTg(k)=

X(k)

bkvkvkTg(k)=-A(k)g(k)

akukukTg(k)=

X(k)

bkvkvkTg(k)=-A(k)g(k)∵ukTg(k)、vkTg(k)是數(shù)量，∴令akukTg(k)=1bkvkTg(k)=1

則uk=

X(k)

ak

=1/([

X(k)]Tg(k))vk=-A(k)g(k)bk

=-1/([

g(k)]T[A(k)]Tg(k))uk、vk的取法有多種，這里令akukukTg(37

∵A(k)是正定對稱矩陣多種，這里令

∴[A(k)]T=

A(k)

故bk

=-1/([

g(k)]TA(k)g(k))于是校正矩陣A(k)為A(k)=(

X(k)[

X(k)]T)/([

X(k)]Tg(k))-(A(k)

g(k)[g(k)]TA(k))/([g(k)]TA(k)

g(k))∵A(k)是正定對稱矩陣多種，這里令∴38DFP變尺度法計算步驟及算法框圖1）給定初始點X(0)及收斂精度>0，k=0；2）置k=0，A(0)=I；3）沿搜索方向S(k)=-A(k)

f(X(k))作一維搜索，得X(k+1)=X(k)+(k)

S(k)；4）計算g(k+1)=

▽f(X(k+1))若||g(k+1)||≤，則輸出最優(yōu)解：

X*

=

X(k+1)

f

*

=f(X*)X(k)

否則，轉(zhuǎn)5）；DFP變尺度法計算步驟及算法框圖1）給定初始點395）若k=n，則X(0)

=

X(k+1)，轉(zhuǎn)2）；若k<n，轉(zhuǎn)6）；6）計算

X(k)=X(k+1)

-X(k)g(k)=g(k+1)-g(k)A(k)=(

X(k)[

X(k)]T)/([

X(k)]Tg(k))-(A(k)

g(k)[g(k)]TA(k))/([g(k)]TA(k)

g(k))A(k+1)=A(k)+A(k)

令kk+1，轉(zhuǎn)3）。5）若k=n，則X(0)=X(k+140機械優(yōu)化設(shè)計太原科技大學(xué)張學(xué)良機械優(yōu)化設(shè)計太原科技大學(xué)41第五章無約束優(yōu)化的間接搜索法

間搜索法是指搜索方向S(k)的構(gòu)建利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)信息的無約束優(yōu)化方法，如梯度法、牛頓法、共軛梯度法、變尺度法。

X(k+1)=X(k)+(k)

S(k)

(k=0,1,2,…)第五章無約束優(yōu)化的間接搜索法間搜索法是指42基本思想

§5.1

梯度法（最速下降法、負(fù)梯度法）利用負(fù)梯度方向作為迭代計算的搜索方向，即S(k)=－▽f(X(k))或S(k)=－▽f(X(k))/||▽f(X(k))||迭代計算公式

X(k+1)=X(k)+(k)[－▽f(X(k))]或X(k+1)=X(k)+(k)[－▽f(X(k))]基本思想§5.1梯度法（最速下降法、負(fù)梯度法43

舉例：

用梯度法求目標(biāo)函數(shù)f(X)=x12+4x22的無約束最優(yōu)解。初始點X1(0)=

[00

]T

，X2(0)=

[22

]T。舉例：用梯度法求目標(biāo)函數(shù)44基本思想和基本算法

§5.2

牛頓法在點X(k)的鄰域內(nèi)，用一個二次函數(shù)(X)來近似代替原目標(biāo)函數(shù)，并以

(X

)的極小點作為原目標(biāo)函數(shù)的極小點的近似值，若不滿足收斂精度要求，則將該近似極小點作為下一次迭代的初始點。如此反復(fù)迭代，直到所求的近似極小點滿足收斂精度要求為止。基本思想和基本算法§5.2牛頓法45

f(X)

f(X(k))+T

f(X(k))

(X-

X(k))+0.5(X-

X(k))T2

f(X(k))

(X-

X(k))=

(X)

(X)的極小點應(yīng)滿足：

(X)=0即f(X(k))+2

f(X(k))

(X-

X(k))=02

f(X(k))

(X-

X(k))=-

f(X(k))當(dāng)2

f(X(k))

正定且有逆陣時，上式兩邊同時左乘[2

f(X(k))

]-1，得X

=X(k)

-[2

f(X(k))

]-1

f(X(k))f(X)f(X(k))+46牛頓法的迭代公式為X(k+1)=X(k)

-[2

f(X(k))

]-1

f(X(k))

X(k+1)=X(k)+(k)

S(k)牛頓方向：S(k)=-[2

f(X(k))

]-1

f(X(k))迭代步長：(k)=1修正牛頓法（又稱阻尼牛頓法）的迭代公式為X(k+1)=X(k)

-

(k)[2

f(X(k))

]-1

f(X(k))阻尼因子：(k)

牛頓法的迭代公式為X(k+1)=X(k)47計算步驟及算法框圖

1）

任選初始點X(0)，給定收斂精度>0，k=0；

2）

計算X(k)點的梯度f(X(k))及其模；

3）檢驗終止條件：||f(X(k))||≤？

若滿足，則輸出最優(yōu)解：X*

=X(k)，

f*

=f(X*)，并終止迭代計算；否則，繼續(xù)下一步迭代計算；計算步驟及算法框圖1）任選初始點48

4）計算X(k)點的海賽矩陣2

f(X(k))及其逆矩陣[2

f(X(k))]-1

5）沿牛頓方向S(k)=-[2

f(X(k))

]-1

f(X(k))進行一維搜索，求最佳步長(k)；

6）令X(k+1)=X(k)+(k)

S(k)，并令kk+1，轉(zhuǎn)2），重復(fù)上述迭代計算過程。4）計算X(k)點的海賽矩陣2f(X(k))49舉例：

用牛頓法求目標(biāo)函數(shù)f(X)=x12+4x22的無約束最優(yōu)解。初始點X1(0)=

[00

]T

，X2(0)=

[22

]T。解：

f(X)=

[2x18x2

]T2

f(X)=008[2

f(X)]-1=0.5000.125f(X1(0))=

[00

]Tf(X2(0))=

[416

]TX1(1)=X1(0)-[2f(X1(0))]-1

f(X1(0))=[00

]T-0.5000.125[00

]=[00

]T舉例：用牛頓法求目標(biāo)函數(shù)解：f(X)=[2x50X2(1)=X2(0)-[2f(X2(0))]-1

f(X2(0))=[22

]T-0.5000.125[416

]=[00

]T可見，X2(1)=X1(0)=[00

]T就是目標(biāo)函數(shù)的理論極小點，僅僅迭代了一次，與初始點的選擇無關(guān)。由于一般函數(shù)在極小點附近呈現(xiàn)出較強的二次性，所以牛頓法在極小點附近收斂速度較快。但無論是牛頓法還是修正牛頓法在每次迭代計算時都要計算目標(biāo)函數(shù)的海賽X2(1)=X2(0)-[2f(X2(0))]-151矩陣及其逆陣，因此計算工作量很大，特別是矩陣求逆，當(dāng)維數(shù)高時工作量更大，且當(dāng)海賽矩陣為奇異陣時，其逆陣不存在，無法使用牛頓法，所以在實際使用中受到一定限制。另外，從計算機存儲方面考慮，牛頓法所需要的存儲量是很大的。若能設(shè)法構(gòu)造一個矩陣來逼近海賽矩陣的逆陣而避免計算海賽矩陣及其逆陣，這樣的方法統(tǒng)稱為擬牛頓法。如只用梯度信息但比梯度法快的共軛梯度法，以及針對牛頓法提出的變尺度法等。矩陣及其逆陣，因此計算工作量很大，特別是矩陣求逆，當(dāng)維數(shù)高時52基本思想§5.3

共軛梯度法共軛梯度法屬于共軛方向法中的一種方法。它是利用目標(biāo)函數(shù)在迭代點X(k)的梯度來構(gòu)造共軛搜索方向的，具有二次收斂性。共軛梯度法搜索的第一步沿負(fù)梯度方向，以后各步沿與上次搜索方向相共軛的方向進行搜索。共軛梯度法的關(guān)鍵是如何在迭代過程中不斷生成共軛搜索方向基本思想§5.3共軛梯度法共軛梯度法53共軛梯度法共軛搜索方向的生成考慮二次函數(shù)

f(X)=0.5XTH

X

+BT

X+C

從X(k)出發(fā)，沿H的某一共軛方向S(k)作一維搜索得到X(k+1)，即X(k+1)

－X(k)=(k)

S(k)（1）將f(X)在X(k)和X(k+1)兩點處的梯度表示并記作g(k)=

▽f(X(k))=H

X(k)

+B（2）g(k+1)=

▽f(X(k+1))=H

X(k+1）

+B（3）共軛梯度法共軛搜索方向的生成考慮二次函數(shù)從54（3）-（2）得g(k+1)－g(k)=H

(

X(k+1)

－X(k))=(k)

H

S(k)（4）（4）式兩邊同時左乘[S(j)]T，有[S(j)]T[g(k+1)－g(k)]=(k)

[S(j)]TH

S(k)=0若S(j)和S(k)關(guān)于H共軛，則有[S(j)]THS(k)=0即[S(j)]T[g(k+1)－g(k)]=0（5）式（5）就是共軛方向與梯度之間的關(guān)系。它表明沿方向S(k)進行一維搜索，其終點X(k+1)與始點X(k)梯度之差(g(k+1)－g(k))與S(k)的共軛（3）-（2）得g(k+1)－g(k)=H(55方向S(j)與正交。共軛梯度法就是利用這個性質(zhì)做到不必計算矩陣H就能求得共軛方向的。1）設(shè)初始點X(0)，第一個搜索方向S(0)取X(0)點的負(fù)梯度方向-g(0)。即S(0)=-g(0)沿S(0)進行一維搜索，得X(1)

=X(0)+(0)

S(0)，并計算X(1)點的梯度g(1)。那么，g(1)與S(0)有什么關(guān)系呢？X(0)g(1)-g(0)X(1)二者正交，即[g(1)]TS(0)=0或[S(0)]Tg(1)

=0因此，S(0)與g(1)構(gòu)成平面正交系。方向S(j)與正交。共軛梯度法就是利用這個性質(zhì)做到不必計算矩562）在S(0)與g(1)構(gòu)成的平面正交系中求S(0)的共軛方向S(1)，以此作為下一步迭代計算的搜索方向。取S(1)為S(0)與g(1)的線性組合，即

S(1)=-g(1)+(0)S(0)

其中，(0)為待定常數(shù)，可以利用共軛方向與梯度之間的關(guān)系求得。由[S(1)]T[g(1)－g(0)]=0有[-g(1)+(0)S(0)]T[g(1)－g(0)]=0展開，得-[g(1)]Tg(1)+[g(1)]Tg(0)+(0)[S(0)]Tg(1)-(0)[S(0)]Tg(0)=02）在S(0)與g(1)構(gòu)成的平面正交系中求S(057所以-[g(1)]Tg(1)-(0)[S(0)]Tg(0)=0所以(0)=-[g(1)]Tg(1)/[S(0)]Tg(0)

=

[g(1)]Tg(1)/[g(0)]Tg(0)=

||g(1)||2

/||g(0)||2S(1)=-g(1)+||g(1)||2

/||g(0)||2

S(0)沿S(1)進行一維搜索，得X(2)

=X(1)+(1)

S(1)，并計算X(2)點的梯度g(2)，則有[S(1)]Tg(2)=0所以-[g(1)]Tg(1)-58故有[-g(1)+(0)S(0)]T

g(2)=0

（6）

因為S(0)和S(1)共軛，所以有[S(0)]T[g(2)－g(1)]=0因為[S(0)]T

g(1)=0所以[S(0)]T

g(2)=0即g(2)與g(0)正交。所以[S(0)]T

g(2)=0由式（6）得[g(1)]T

g(2)=0可見，g(0)、g(1)、g(2)構(gòu)成一個空間正交系。故有[-g(1)+(0593）在g(0)、g(1)、g(2)構(gòu)成的空間正交系中求與S(0)及S(1)均共軛的方向S(2)，以此作為下一步迭代計算的搜索方向。仍取S(2)為g(0)、g(1)、g(2)的線性組合，即

S(2)=-g(2)+(1)g(1)+(0)g(0)

其中，(1)、(0)為待定常數(shù)，可以利用共軛方向與梯度之間的關(guān)系求得。[S(2)]T[g(1)－g(0)]=0[S(2)]T[g(2)－g(1)]=03）在g(0)、g(1)、g(2)構(gòu)成的空間正交系60即[-g(2)+(1)g(1)+(0)g(0)]T[g(1)－g(0)]=0[-g(2)+(1)g(1)+(0)g(0)]T[g(2)－g(1)]=0

所以(1)[g(1)]Tg(1)-

(0)[

g(0)]Tg(0)]=0-[g(2)]Tg(2)-

(1)[g(1)]Tg(1)=0

令(1)=-(1)

得(1)=-(1)=

[g(2)]Tg(2)/[g(1)]Tg(1)

=||g(2)||2

/||g(1)||2(0)=

(1)[g(1)]Tg(1)/[g(0)]Tg(0)

=-(1)

(0)即[-g(2)+(1)g(1)+61因此S(2)=-g(2)+(1)g(1)+(0)g(0)

=-g(2)-(1)g(1)-(1)(0)g(0)=-g(2)+(1)[-

g(1)-(0)g(0)]=-g(2)+(1)S(1)故S(2)=-g(2)+||g(2)||2/||g(1)||2S(1)再沿S(2)進行一維搜索，得X(3)

=X(2)+(2)

S(2)，如此繼續(xù)下去，可以求得共軛方向的遞推公式為

S(k+1)=-g(k+1)+||g(k+1)||2/||g(k)||2S(k)(k=0,1,2,…,n-1)因此S(2)=-g(2)+(1)62沿著這些共軛搜索方向一直搜索下去，直到最后迭代點處梯度的模小于給定的允許值為止。若目標(biāo)函數(shù)為非二次函數(shù)，經(jīng)n次搜索還未達到最優(yōu)點時，則以最后得到的點作為初始點，重新計算共軛方向，一直到滿足精度要求為止。共軛梯度法的計算步驟及算法框圖1）給定初始點X(0)及收斂精度>0，k=0；2）取S(0)=－▽f(X(0))；沿著這些共軛搜索方向一直搜索下去，直到最后迭633）X(k+1)

=X(k)+(k)

S(k)(k=0,1,2,…,n)(k)

為一維搜索所得的最佳步長。4）判斷||▽f(X(k+1))||≤?

若滿足，則輸出X

*=

X(k+1)

和f

*=

f(X

*)否則，轉(zhuǎn)下一步；5）判斷k+1=n?

若k+1=n，令X(0)

=

X(k+1)

，轉(zhuǎn)2）；若k+1<n，則計算

(k)=||▽f(X(k+1))||2/||▽f(X(k))||23）X(k+1)=X(k)+(k)S(64

S(k+1)=-▽f(X(k+1))+(k)S(k)并令kk+1，轉(zhuǎn)3）。1）盡管理論上可以證明目標(biāo)函數(shù)為n維正定二次函數(shù)時，共軛梯度法只需要n次迭代就可以達到最優(yōu)點，但由于計算機的舍入誤差，實際計算往往要多進行若干次才能得到滿足精度要求的結(jié)果；而對于一般的目標(biāo)函數(shù)，迭代次數(shù)將更多。關(guān)于共軛梯度法的說明S(k+1)=-▽f(X(k652）由于n維設(shè)計空間中最多只能有n個線性無關(guān)的向量，所以n維優(yōu)化問題的共軛方向最多只有n個。因此，共軛梯度法進行n步搜索后，若仍不滿足精度要求，繼續(xù)產(chǎn)生共軛方向S(n+1)進行迭代搜索是沒有意義的（效果很差），而應(yīng)令X(0)

=

X(n)

，重新開始新一輪的共軛梯度法迭代搜索。實踐證明，這樣處理一般都可以取得較好的效果。2）由于n維設(shè)計空間中最多只能有n個線性無關(guān)的向66舉例：

用共軛梯度法求目標(biāo)函數(shù)f(X)=x12+4x22的無約束最優(yōu)解。初始點X(0)=

[22

]T，=0.01。解：

f(X)=

[2x18x2

]TS(0)=-f(X(0))=

[-4-16

]TX(1)=X(0)-(0)f(X(0))=[22

]T

-(0)[416]T=[2-4(0)2-16(0)]T

f(X(1))

=(2-4(0))2+4(2-16(0))2據(jù)df(X(1))/d(0)=0得(0)=0.13076923X(1)=[1.476923077

-0.09230768

]T

舉例：用共軛梯度法求目標(biāo)函數(shù)解：f(X)=[67f(X(1))=

[2.953846154-0.73846144

]T(0)=||▽f(X(1))||2/||▽f(X(0))||2=0.034082837

S(1)=-▽f(X(1))+(0)S(0)

=-[2.953846154-0.73846144

]T

+0.034082837[-4-16

]T

=[-3.090177510.193136016

]TX(2)=X(1)+(1)S(1)=[1.476923077

-0.09230768

]T

+

(1)[-3.090177510.193136016

]Tf(X(1))=[2.95384615468據(jù)df(X(2))/d(1)=0得(1)=0.477941179X(2)=[6×10-9-2.4×10-8]T

≈[0

0]T

||▽f(X(2))||≈0<=0.01故最優(yōu)解為

X*=X(2)=[0

0]Tf(X*)=0據(jù)df(X(2))/d(1)=0得69DFP變尺度法的基本思想§5.4

變尺度法它是基于牛頓法的思想，并對其做了重要的改進后的一類方法。它不需要計算二階導(dǎo)數(shù)矩陣及其逆陣，又比共軛梯度法有更好的收斂性，對較高維數(shù)的無約束優(yōu)化問題有明顯的優(yōu)越性。梯度法遠(yuǎn)離最優(yōu)點時，對突破函數(shù)的非二次性極為有利（即收斂速度快），但迭代點接近最優(yōu)點時收斂速度慢；而牛頓法則正好相反，它具有二次收斂性，接近最優(yōu)點時DFP變尺度法的基本思想§5.4變尺度法70收斂極快，但它需要計算海賽矩陣及其逆陣，計算工作量比梯度法大為增加。若能構(gòu)造一種算法，它兼有梯度法和牛頓法各自的優(yōu)點，那么這種算法一定比梯度法和牛頓法更有效，于是便產(chǎn)生了變尺度法。梯度法：X(k+1)=X(k)

-

(k)

f(X(k))牛頓法：X(k+1)=X(k)

-

(k)[2

f(X(k))

]-1

f(X(k))變尺度法的迭代公式:X(k+1)=X(k)

-

(k)A(k)

f(X(k))A(k)

為人為構(gòu)造的對稱方陣，稱為構(gòu)造矩陣，它迭代點位置的變化而變化。收斂極快，但它需要計算海賽矩陣及其逆陣，計算工作量比梯度法大71變尺度法的迭代公式:X(k+1)=X(k)

-

(k)A(k)

f(X(k))若在迭代初始時，A(k)

=I，則上式與梯度法的迭代公式相同，可使迭代點遠(yuǎn)離最優(yōu)點時收斂速度加快。以后隨著迭代過程的進行，不斷地修正構(gòu)造矩陣，使它逐步逼近函數(shù)在迭代點X(k)處的海賽矩陣的逆陣[2f(X(k))]-1，這樣當(dāng)?shù)c逼近最優(yōu)點時，迭代搜索方向就趨于牛頓方向，因此收斂速度極快。變尺度法的搜索方向為:S(k)=-A(k)

f(X(k))稱為逆牛頓方向。變尺度法的迭代公式:72構(gòu)造矩陣可看成是搜索過程中的一種尺度變換矩陣，它從一次迭代到另一次迭代是變化的，所以又稱為變尺度矩陣。要實現(xiàn)上述變尺度法的基本思想，關(guān)鍵在于如何產(chǎn)生變尺度矩陣。DFP變尺度法中變尺度矩陣系列的產(chǎn)生∵變尺度矩陣A(k)是隨迭代點X(k)變化而變化，初始變尺度矩陣A(0)需預(yù)先選定，且必須是正定對稱矩陣，一般取A(0)=I。∴A(k)是一個序列，記為{A(k)}（k=0,1,2