第四章 無(wú)約束優(yōu)化方法

第四章

無(wú)約束優(yōu)化方法坐標(biāo)輪換法鮑威爾法梯度法牛頓法DFP變尺度法BFGS變尺度法無(wú)約束優(yōu)化方法的評(píng)價(jià)準(zhǔn)則及選用

無(wú)約束優(yōu)化方法是優(yōu)化技術(shù)中基本的也是非常重要的內(nèi)容。無(wú)約束優(yōu)化問(wèn)題的數(shù)學(xué)模型求上述問(wèn)題最優(yōu)解（x*,F*）的方法，稱為無(wú)約束優(yōu)化方法

無(wú)約束優(yōu)化方法，不僅可以直接求無(wú)約束優(yōu)化設(shè)計(jì)問(wèn)題的最優(yōu)解，而且通過(guò)對(duì)無(wú)約束優(yōu)化方法的研究給約束優(yōu)

化方法建立明確的概念、提供良好的基礎(chǔ)·某些優(yōu)化設(shè)計(jì)方法就是先把約束優(yōu)化設(shè)計(jì)問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題后，

再直接用無(wú)約束優(yōu)化方法求解。無(wú)約束優(yōu)化理論研究開(kāi)展得較早，構(gòu)成的優(yōu)化方法巳很多，也比較成熟，新的方法仍在陸續(xù)出現(xiàn)。本章的內(nèi)容與目的是討論幾個(gè)常用無(wú)約束優(yōu)化方法的基本思想、方法構(gòu)成、迭代步驟以及終止準(zhǔn)則等方面問(wèn)題。無(wú)約束優(yōu)化方法總體分成兩大類型:解析法或稱間接法、直接搜索法或簡(jiǎn)稱直接法；在n維無(wú)約束優(yōu)化方法的算法中，用函數(shù)的一階、二價(jià)導(dǎo)數(shù)進(jìn)行求解的算法，稱為解析法;對(duì)于n維優(yōu)化問(wèn)題，如果只利用函數(shù)值求最優(yōu)值的解法，稱為直接搜索法；解析法的收斂速率較高，直接法的可靠性較高。

本章介紹的坐標(biāo)輪換法和鮑威爾法屬于直接法；梯度法、共軛梯度法、牛頓法和變尺度法屬于解析法無(wú)約束優(yōu)化方法算法的基本過(guò)程是:從選定的某初始點(diǎn)x(k)出發(fā)，沿著以一定規(guī)律產(chǎn)生的搜索方向S(k),取適當(dāng)?shù)牟介L(zhǎng)a(k),逐次搜尋函數(shù)值下降的新迭代點(diǎn)x(k+1),使之逐步逼近最優(yōu)點(diǎn)x*。可以把初始點(diǎn)x(k)、搜索方向S(k)、迭代步長(zhǎng)a(k)稱為優(yōu)化方法算法的三要素。其中以搜索方向S(k)更為突出和重要，它從根本上決定著一個(gè)算法的成敗、收斂速率的快慢等。所以，一個(gè)算法的搜索方向成為該優(yōu)化方法的基本標(biāo)志，分析、確定搜索方向S(k)是研究?jī)?yōu)化方法的最根本的任務(wù)之一。坐標(biāo)輪換法坐標(biāo)輪換法屬于直接法，既可以用于無(wú)約束優(yōu)化問(wèn)題的求解，又可以經(jīng)過(guò)適當(dāng)處理用于約束優(yōu)化問(wèn)題求解。坐標(biāo)輪換法是每次搜索只允許一個(gè)變量變化，其余變量保持不變，即沿坐標(biāo)方向輪流進(jìn)行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問(wèn)題輪流地轉(zhuǎn)化成單變量（其余變量視為常量）的優(yōu)化問(wèn)題，因此又稱這種方法為變量輪換法。此種方法只需目標(biāo)函數(shù)的數(shù)值信息而不需要目標(biāo)函數(shù)的導(dǎo)數(shù)。一、坐標(biāo)輪換法的迭代過(guò)程二次函數(shù)為例。任取一初始點(diǎn)x(0)作為第一輪的始點(diǎn)x0

(1),先沿第一坐標(biāo)軸的方向e1作一維搜索，用一維優(yōu)化方法確定最優(yōu)步1長(zhǎng)

(1)

，得第一輪的第一個(gè)迭代點(diǎn)x1

=x0

+(1)

(1)(1)

e

，1

1然后以x1

(1)為新起點(diǎn)，沿第二坐標(biāo)軸的方向e2作一維2搜索，確定步長(zhǎng)

(1)

，得第一輪的第二個(gè)迭代點(diǎn)2

1x

(1)

=x

(1)

+(1)

e1

2第二輪迭代，需要x

(2)x0

2(1)1

0x

(2)

=

x

(2)

+1(2)

e1x

(2)

=x

(2)

+(2)

e2

1

2

2依次類推，不斷迭代，目標(biāo)函數(shù)值不斷下降，最后逼近該目標(biāo)函數(shù)的最優(yōu)點(diǎn)。二、終止準(zhǔn)則可以采用點(diǎn)距準(zhǔn)則注意：若采用點(diǎn)距準(zhǔn)則或函數(shù)值準(zhǔn)則，其中采用的點(diǎn)應(yīng)該是一輪迭代的始點(diǎn)和終點(diǎn)，而不是某搜索方向的前后迭代點(diǎn)。坐標(biāo)輪換法的計(jì)算步驟⑴任選初始點(diǎn)，置n個(gè)坐標(biāo)軸方向矢量為單位作為第一輪的起點(diǎn)坐標(biāo)矢量：⑵按照下面迭代公式進(jìn)行迭代計(jì)算k為迭代輪數(shù)的序號(hào)，取k=1，2，……；i為該輪中一維搜索的序號(hào)，取i=1，2，……n步長(zhǎng)α一般通過(guò)一維優(yōu)化方法求出其最優(yōu)步長(zhǎng)。⑶按下式判斷是否中止迭代如滿足，迭代中止，并輸出最優(yōu)解最優(yōu)解否則，令k←k+1返回步驟（2）例題4.1

用坐標(biāo)輪換法求目標(biāo)函數(shù)的無(wú)約束最優(yōu)解。給定初始點(diǎn)，精度要求ε=0.1解：做第一輪迭代計(jì)算沿e1方向進(jìn)行一維搜索式中，為第一輪的起始點(diǎn)，取按最優(yōu)步長(zhǎng)原則確定最優(yōu)步長(zhǎng)α1，即極小化此問(wèn)題可由某種一維優(yōu)化方法求出α1。這里，我們暫且用微分學(xué)求導(dǎo)解出，令其一階導(dǎo)數(shù)為零以

為新起點(diǎn)，沿e2方向一維搜索以最優(yōu)步長(zhǎng)原則確定α2，即為極小化對(duì)于第一輪按終止條件檢驗(yàn)繼續(xù)進(jìn)行第2輪迭代計(jì)算，各輪計(jì)算結(jié)果見(jiàn)課本表4.1。計(jì)算5輪后，有故近似優(yōu)化解為標(biāo)輪換法的流程圖-+-+小結(jié)坐標(biāo)輪換法程序簡(jiǎn)單，易于掌握。但是計(jì)算效率比較低，尤其是當(dāng)優(yōu)化問(wèn)題的維數(shù)較高時(shí)更為嚴(yán)重。一般把此種方法應(yīng)用于維數(shù)小于10的低維優(yōu)化問(wèn)題。對(duì)于目標(biāo)函數(shù)存在“脊線”的情況，在脊線的尖點(diǎn)處沒(méi)有一個(gè)坐標(biāo)方向可以使函數(shù)值下降，只有在銳角所包含的范圍搜索才可以達(dá)到函數(shù)值下降的目的，故坐標(biāo)輪換法對(duì)此類函數(shù)會(huì)失效。x2x1脊線鮑威爾方法鮑威爾方法是直接搜索法中一個(gè)十分有效的算法。該算法是沿著逐步產(chǎn)生的共軛方向進(jìn)行搜索的，因此本質(zhì)上是一種共軛方向法。一、鮑威爾基本算法如圖所示，以三維二次目標(biāo)函數(shù)的無(wú)約束優(yōu)化問(wèn)題為例。鮑威爾基本算法的搜索過(guò)程鮑威爾基本算法的步驟：第一環(huán)基本方向組取單位坐標(biāo)矢量系e1、e2、e3

、…、

en，沿這些方向依次作一維搜索，然后將始末兩點(diǎn)相連作為新生方向，n

0Sk=x

k-x

k再沿新生方向作一維搜索，完成第一環(huán)的迭代。以后每環(huán)的基本方向組是將上環(huán)的第一個(gè)方向淘汰，上環(huán)的新生方向補(bǔ)入本環(huán)的最后而構(gòu)成?！?/p>

S2

3

nS

k

S

k

Skn維目標(biāo)函數(shù)完成n環(huán)的迭代過(guò)程稱為一輪。從這一輪的終點(diǎn)出發(fā)沿新生方向搜索所得到的極小點(diǎn)，作為下一輪迭代的始點(diǎn)。這樣就形成了算法的循環(huán)。鮑威爾基本算法的缺陷：可能在某一環(huán)迭代中出現(xiàn)基本方向組為線性相關(guān)的矢量系的情況。如第k環(huán)中，產(chǎn)生新的方向：Sk=xnk-x0k=1(k)S1(k)+

2(k)S2(k)

+

?

?

?

+

n(k)Sn(k)式中，S1(k)、S2(k)、???、Sn(k)為第k環(huán)基本方向組矢量，1(k)、2(k)、???、n(k)為個(gè)方向的最優(yōu)步長(zhǎng)。若在第k環(huán)的優(yōu)化搜索過(guò)程中出現(xiàn)1(k)=0，則方向Sk表示為S2(k)、S3(k)、???、Sn(k)的線性組合，以后的各次搜索將在降維的空間進(jìn)行，無(wú)法得到n維空間的函數(shù)極小值，計(jì)算將失敗。如圖所示為一個(gè)三維優(yōu)化問(wèn)題的示例，設(shè)第一環(huán)中1=0

，則新生方向與e2

、e3共面，隨后的各環(huán)方向組中，各矢量必在該平面內(nèi)，使搜索局限于二維空間，不能得到最優(yōu)解。鮑威爾基本算法的退化x1x31=02e23e3S1x2二、鮑威爾修正算法在某環(huán)已經(jīng)取得的n+1各方向中，選取n個(gè)線性無(wú)關(guān)的并且共軛程度盡可能高的方向作為下一環(huán)的基本方向組鮑威爾修正算法的搜索方向的構(gòu)造：在第k環(huán)的搜索中，x0k

為初始點(diǎn)，搜索方向?yàn)镾1(k)、S2(k)、???、Sn(k)，產(chǎn)生的新方向?yàn)镾k

，此方向的極小點(diǎn)為x(k)。點(diǎn)xn+1(k)=2xn(k)-x0(k)，為x0(k)對(duì)xn(k)的映射點(diǎn)。計(jì)算x0(k)、x1(k)、???、xn(k)、x(k)、x

n+1(k)各點(diǎn)的函數(shù)值，記作：0

2nF1=F(x

(k))

F

=F(x

(k))F3=F(x(k))=

F(x

(k))

-F(xn+1

m

m-1(k))是第k環(huán)方向組中，依次沿各方向搜索函數(shù)值下降最大值，即Sm(k)方向函數(shù)下降最大。(F2)(F1)影射點(diǎn)(F3)函數(shù)下降量△爾算法的方向淘汰為了構(gòu)造第k+1環(huán)基本方向組，采用如下判別式：按照以下兩種情況處理：1、上式中至少一個(gè)不等式成立，則第k+1環(huán)的基本方1

2

n向仍用老方向組S

(k)、S

(k)、???、S

(k)。k+1環(huán)的初始點(diǎn)取0

nx

(k+1)=x

(k)F

<F2

30n+1x

(k+1)=x

(k)F2

F32、兩式均不成立，則淘汰函數(shù)值下降最大的方向，并用第k環(huán)的新生方向補(bǔ)入k+1環(huán)基本方向組的最后，即k+1環(huán)的方向組為S

(k)、S

(k)、???、S1

2

m-1m+1

n(k)、S

(k)

?

?

?

、

S

(k)

、Sn+1(k)。k+1環(huán)的初始點(diǎn)取0x

(k+1)=x(k)n+1x(K)是第k環(huán)沿S

(K)方向搜索的極小點(diǎn)。鮑威爾算法的終止條件：0||

x(K)-x

(k)

||三修正算法的迭代步驟及流程圖Powell算法的步驟如下：⑴任選初始迭代點(diǎn)，選定迭代精度ε，取初始基本方向組為單位坐標(biāo)矢量系其中，i=1，2……n（下同）。然后令k=1（環(huán)數(shù)）開(kāi)始下面的迭代⑵沿

諸方向依次進(jìn)行n次一微搜索，確定各步長(zhǎng)使i=1，2……n得到點(diǎn)陣構(gòu)成新生方向沿

方向進(jìn)行一維搜索求得優(yōu)化步長(zhǎng)

，得⑶判斷是否滿足迭代終止條件。如滿足則可結(jié)束迭代，最優(yōu)解為停止計(jì)算。否則，繼續(xù)進(jìn)行下步。⑷計(jì)算各迭代點(diǎn)的函數(shù)值最大者，并找出相鄰點(diǎn)函數(shù)值差（1≤m≤n）及與之相對(duì)應(yīng)的兩個(gè)點(diǎn)的連線方向。和，并以

表示兩點(diǎn)⑸確定映射點(diǎn)并計(jì)算函數(shù)值檢驗(yàn)鮑威爾條件若至少其中之一成立轉(zhuǎn)下步，否則轉(zhuǎn)步驟⑺⑹置k+1環(huán)的基本方向組和起始點(diǎn)為（即取老方向組）當(dāng)F2＜F3當(dāng)F2≥F3令k←k+1，返回步驟⑵⑺置k+1環(huán)的方向組和起始點(diǎn)為令k←k+1，返回步驟⑵例題4.2試用鮑威爾修正算法求目標(biāo)函數(shù)的最優(yōu)解。已知初始點(diǎn)，迭代精度ε=0.001解：第一環(huán)迭代計(jì)算沿第一坐標(biāo)方向e1進(jìn)行一維搜索α1=2以

為起點(diǎn)，改沿第二坐標(biāo)軸方向e2進(jìn)行一維搜索α2=0.5構(gòu)成新方向沿S1方向進(jìn)行以為搜索得極小點(diǎn)與極小值計(jì)算點(diǎn)距需進(jìn)行第二環(huán)迭代計(jì)算第二環(huán)迭代計(jì)算首先確定上環(huán)中的最大函數(shù)下降量及其相應(yīng)方向映射點(diǎn)及其函數(shù)值檢查鮑威爾條件于是可知鮑威爾條件兩式均不成立。第二環(huán)取基本方向組和起始點(diǎn)為沿e2方向作一維搜索得以

為起點(diǎn)沿S1方向一維搜索得構(gòu)成新生方向沿S2方向一維搜索得檢查迭代終止條件需再作第三環(huán)迭代計(jì)算。根據(jù)具體情況來(lái)分析，S1，S2實(shí)際上為共軛方向，見(jiàn)下圖。本題又是二次函數(shù)，有共軛方向的二次收斂性，上面結(jié)果就是問(wèn)題的最優(yōu)解?？梢灶A(yù)料，如果做第三環(huán)迭代，則一定各一維搜索的步長(zhǎng)為零，必有故得最優(yōu)解梯度法優(yōu)化設(shè)計(jì)是追求目標(biāo)函數(shù)值最小，因此，自然可以設(shè)想從某點(diǎn)出發(fā)，其搜索方向取該點(diǎn)的負(fù)梯度方向，使函數(shù)值在該點(diǎn)附近下降最快。這種方法也稱為最速下降法。一、基本原理梯度法的迭代公式為：x(k+1)=x(k)-

(k)g(k)f(x(k))

，(k)其中g(shù)(k)是函數(shù)F(x)在迭代點(diǎn)x(k)處的梯度一般采用一維搜索的最優(yōu)步長(zhǎng)，即f(x(k+1))=f(x(k)-

(k)g(k))=min

f(x(k)-(k)g(k))=min(

)據(jù)一元函數(shù)極值條件和多元復(fù)合函數(shù)求導(dǎo)公式，得’(

)=

-(

f(x(k)-(k)g(k)))T

g(k)

=0即(f(x(k+1)))T

g(k)

=0?或(g(k+1))Tg(k)=0此式表明，相鄰的兩個(gè)迭代點(diǎn)的梯度是彼此正交的。也即在梯度的迭代過(guò)程中，相鄰的搜索方向相互垂直。梯度法向極小點(diǎn)的逼近路徑是鋸齒形路線，越接近極小點(diǎn)，鋸齒越細(xì)，前進(jìn)速度越慢。這是因?yàn)樘荻仁呛瘮?shù)的局部性質(zhì)，從局部上看，在該點(diǎn)附近函數(shù)的下降最快，但從總體上看則走了許多彎路，因此函數(shù)值的下降并不快。二、迭代終止條件？若滿足輸出最優(yōu)解采用梯度準(zhǔn)則：||

g(k)

||三、迭代步驟任選初始迭代點(diǎn)x(0)，選收斂精度

。確定x(k)點(diǎn)的梯度（開(kāi)始k=0)判斷是否滿足終止條件||

g(k)||結(jié)束計(jì)算。否則轉(zhuǎn)下步。（4）從x(k)點(diǎn)出發(fā)，沿-g(k)方向作一維搜索求最優(yōu)步長(zhǎng)(k)。得下一迭代點(diǎn)

x(k+1)=x(k)-

(k)g(k)

,令k=k+1

返回步驟(2)。四、梯度法流程圖出口入口給定：x(0)，k=0x(k)=

x(0)計(jì)算：g(k)k=k+1沿g(k)方向一維搜索，求最優(yōu)步長(zhǎng)(k)。x(k+1)=

x(k)-

(k)

g(k)/

||g(k)||N？||g(k)||Yx*=x(k)f*=f(x(k))的最優(yōu)解。例題4.3用梯度法求目標(biāo)函數(shù)已知初始點(diǎn)迭代精度ε=0.005解：函數(shù)的梯度第一次迭代：以為起點(diǎn)沿一方向作一維搜索得第一個(gè)迭代點(diǎn)繼續(xù)第二次迭代到第五次迭代結(jié)束時(shí)，有故迭代可終止，最優(yōu)解為迭代數(shù)據(jù)表見(jiàn)課本表4.2共軛梯度法共軛梯度法是共軛方向法的一種，因?yàn)樵摲椒ㄖ忻恳粋€(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來(lái)的，所以稱作共軛梯度法。一、共軛梯度法的搜索方向共軛梯度法的搜索方向采用梯度法基礎(chǔ)上的共軛方向，如圖所示，目標(biāo)函數(shù)F(x)在迭代點(diǎn)xk+1處的負(fù)梯度為-f(xk+1)，該方向與前一搜索方向Sk互為正交，在此基礎(chǔ)上構(gòu)造一種具有較高收斂速度的算法，該算法的搜索方向要滿足以下兩個(gè)條件：（1）以xk+1點(diǎn)出發(fā)的搜索方向

Sk+1是-

f(xk+1)與Sk的線性組合。即xkx*xk+1-

f(xk+1)Sk+1Skf(xk+1)

+Sk+1

=

-

kSk（2）以與為基底的子空間中，矢量與相共軛，即滿足[Sk+1]T

G

Sk

=0二、

k的確定確定方法自學(xué)，不作要求。記住三、共軛梯度法的算法（1）選初始點(diǎn)x0和收斂精度

。（2）令k=0，計(jì)算S0

=

-

f(x0)

。(k)，得（3）沿Sk方向進(jìn)行一維搜索求x(k+1)=x(k)+

(k)S(k)（4）計(jì)算

f(xk+1)

，若||

f(xk+1)||，則終止迭代，取x*=xk+1；否則進(jìn)行下一步。（5）檢查搜索次數(shù)，若k=n，則令x0=xk+1，轉(zhuǎn)（2），否則，進(jìn)行下一步。（6）構(gòu)造新的共軛方向f(xk+1)

+Sk+1

=

-

kSk令k=k+1，轉(zhuǎn)（3）四、共軛梯度法流程圖||

f(xk+1)

||？出口求(k)S(k)(k)

，x(k+1)=

x(k)

+計(jì)算：

f(xk+1)x*=xk+1f(x*)=f(xk+1)YN入口給定：x(0)，k=0，計(jì)算：-

f(x0)x0=xk+1Nk

n

？YSk+1

=

-f(xk+1)

+kSkK=K+1五、共軛梯度法的特點(diǎn)共軛梯度法屬于解析法，其算法需求一階導(dǎo)數(shù)，所用公式及算法簡(jiǎn)單，所需存儲(chǔ)量少。該方法以正定二次函數(shù)的共軛方向理論為基礎(chǔ)，對(duì)二次型函數(shù)可以經(jīng)過(guò)有限步達(dá)到極小點(diǎn)，所以具有二次收斂性。但是對(duì)于非二次型函數(shù)，以及在實(shí)際計(jì)算中由于計(jì)算機(jī)舍入誤差的影響，雖然經(jīng)過(guò)n次迭代，仍不能達(dá)到極小點(diǎn)，則通常以重置負(fù)梯度方向開(kāi)始，搜索直至達(dá)到預(yù)定精度，其收斂速度也是較快的。六、例題牛頓法牛頓法是求無(wú)約束最優(yōu)解的一種古典解析算法。牛頓法可以分為原始牛頓法和阻尼牛頓法兩種。實(shí)際中應(yīng)用較多的是阻尼牛頓法。原始牛頓法一、原始牛頓法的基本思想在第k次迭代的迭代點(diǎn)x(k)鄰域內(nèi)，用一個(gè)二次函數(shù)去近似代替原目標(biāo)函數(shù)F(x)，然后求出該二次函數(shù)的極小點(diǎn)作為對(duì)原目標(biāo)函數(shù)求優(yōu)的下一個(gè)迭代點(diǎn)，依次類推，通過(guò)多次重復(fù)迭代，使迭代點(diǎn)逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)。如圖所示。0(x)1(x)F(x)x0x2

x1x*二、原始牛頓法的迭代公式設(shè)目標(biāo)函數(shù)F(x)具有連續(xù)的一、二階導(dǎo)數(shù)，在x(k)點(diǎn)鄰域內(nèi)取F(x)的二次泰勒多項(xiàng)式作近似式，即取逼近函數(shù)

(x)為設(shè)x(k+1)為(x)極小點(diǎn)，根據(jù)極值的必要條件，應(yīng)有(x(k+1))=0，即(x)=

gk+

Hk

x=0又x=

x

(k+1)

-

x

(k)得x

(k+1)=x

(k)-H

-1gk

kk

k即牛頓法迭代公式，方向-H

-1g

稱為牛頓方向三、原始牛頓法的特點(diǎn)若用原始牛頓法求某二次目標(biāo)函數(shù)的最優(yōu)解，則構(gòu)造的逼近函數(shù)與原目標(biāo)函數(shù)是完全相同的二次式，其等值線完全重合，故從任一點(diǎn)出發(fā)，一定可以一次達(dá)到目標(biāo)函數(shù)的極小點(diǎn)。牛頓法是具有二次收斂性的算法。其優(yōu)點(diǎn)是：對(duì)于二次正定函數(shù)，迭代一次即可以得到最優(yōu)解，對(duì)于非二次函數(shù)，若函數(shù)二次性較強(qiáng)或迭代點(diǎn)已經(jīng)進(jìn)入最優(yōu)點(diǎn)的較小鄰域，則收斂速度也很快。原始牛頓法的缺點(diǎn)是：由于迭代點(diǎn)的位置是按照極值條件確定的，并未沿函數(shù)值下降方向搜索，因此，對(duì)于非二次函數(shù)，有時(shí)會(huì)使函數(shù)值上升，即f(xk+1)>

f(xk)，而使計(jì)算失敗。阻尼牛頓法(k)對(duì)原始牛頓法的改進(jìn)為解決原始牛頓法的不足，加入搜索步長(zhǎng)因此，迭代公式變?yōu)椋簒

(k+1)

=

x

(k)

-

(k)

H

-1gk

k這就是阻尼牛頓法的迭代公式，最優(yōu)步長(zhǎng)(k)也稱為阻尼因子，是沿牛頓方向一維搜索得到的最優(yōu)步長(zhǎng)。ε牛頓法算法步驟⑴任選初始點(diǎn)，給定精度ε，置k←0⑵計(jì)算

點(diǎn)的梯度矢量及其模⑶檢驗(yàn)迭代終止條件如滿足，則輸出最優(yōu)解否則，轉(zhuǎn)下步⑷計(jì)算

點(diǎn)處的海塞矩陣i，j=1，2……n并求其逆矩陣⑸確定牛頓方向方向上的最優(yōu)步并沿牛頓方向作一維搜索，求出在長(zhǎng)⑹計(jì)算第k+1個(gè)迭代點(diǎn)置k←k+1，返回步驟⑵頓法的算法流程圖+-例題4.5

用牛頓法求函數(shù)的最優(yōu)解。初始點(diǎn)，解：函數(shù)的梯度和海賽矩陣及其逆在

點(diǎn)處沿

方向移位搜索求得最優(yōu)步長(zhǎng)故新迭代點(diǎn)為該點(diǎn)的梯度迭代即可結(jié)束由于目標(biāo)函數(shù)是二次正定函數(shù)，故迭代一次即達(dá)到最優(yōu)點(diǎn)三、阻尼牛頓法的特點(diǎn)優(yōu)點(diǎn)：由于阻尼牛頓法每次迭代都在牛頓方向進(jìn)行一維搜索，避免了迭代后函數(shù)值上升的現(xiàn)象，從而保持了牛頓法的二次收斂性，而對(duì)初始點(diǎn)的選擇沒(méi)有苛刻的要求。缺點(diǎn)：1、對(duì)目標(biāo)函數(shù)要求苛刻，要求函數(shù)具有連續(xù)的一、二階導(dǎo)數(shù)；為保證函數(shù)的穩(wěn)定下降，海賽矩陣必須正定；為求逆陣要求海賽矩陣非奇異。2、計(jì)算復(fù)雜且計(jì)算量大，存儲(chǔ)量大DFP變尺度法變尺度法也稱擬牛頓法，它是基于牛頓法的思想而又作了重大改進(jìn)的一類方法。我們所介紹的變尺度法是由Davidon于1959年提出又經(jīng)

Fletcher和Powell加以發(fā)展和完善的一種變尺度法，故稱為DFP變尺度法。一、變尺度法的基本思想變尺度法的基本思想與牛頓法和梯度法有密切聯(lián)系。觀察梯度法和牛頓法的迭代公式和kx(k+1)=x(k)-

(k)g(k)x(k+1)=x(k)-

(k)H

-1

g(k)分析比較這兩種方法可知：梯度法的搜索方向?yàn)?g(k)，只需計(jì)算函數(shù)的一階偏導(dǎo)數(shù)，計(jì)算量小，當(dāng)?shù)c(diǎn)遠(yuǎn)離最優(yōu)點(diǎn)時(shí)，函數(shù)值下降很快，但當(dāng)?shù)c(diǎn)接近最優(yōu)點(diǎn)時(shí)收斂速度極慢。牛頓法的搜索方向?yàn)?H

-1

g(k)，不僅需要計(jì)算一k階偏導(dǎo)數(shù)，而且要計(jì)算二階偏導(dǎo)數(shù)及其逆陣，計(jì)算量很大，但牛頓法具有二次收斂性，當(dāng)?shù)c(diǎn)接近最優(yōu)點(diǎn)時(shí)，收斂速度很快。若迭代過(guò)程先用梯度法，后用牛頓法并避開(kāi)牛頓法的

海賽矩陣的逆矩陣的煩瑣計(jì)算，則可以得到一種較好的優(yōu)化方法，這就是“變尺度法”產(chǎn)生的基本構(gòu)想為此，綜合梯度法和牛頓法的優(yōu)點(diǎn)，提出變尺度法的基本思想。式中的Ak為構(gòu)造的n

n階對(duì)稱矩陣，它是隨迭代點(diǎn)的位置的變化而變化的。若Ak

=I，上式為梯度法的迭代公式k若Ak

=H

-1

，上式為阻尼牛頓法的迭代公式。變尺度法的搜索方向S(k)=-Ak

gk

，稱為擬牛頓方向。變尺度法的基本迭代公式寫(xiě)為下面的形式：?x(k+1)

=

x(k)

-

(k)Ak

gkDFP法構(gòu)造矩陣序列的產(chǎn)生構(gòu)造矩陣是隨迭代過(guò)程的推進(jìn)而逐次改變的，因而它是一種矩陣序列{Ak}，k=1，2，……選取初始矩陣A0，并以梯度方向快速收斂，通常取單位矩陣E作為初始矩陣，即A0=E。而后的矩陣均是在前一構(gòu)造矩陣的基礎(chǔ)上校正得到，令A(yù)

=A

+△A1

0

0推廣到一般的k+1次構(gòu)造矩陣Ak+1=Ak+△Ak矩陣序列的基本迭代式△Ak稱為校正矩陣擬牛頓條件設(shè)F（x）為一般形式n階的目標(biāo)函數(shù)，并具有連續(xù)的一、二階偏導(dǎo)。在點(diǎn)

處的二次泰勒近似展開(kāi)該近似二次函數(shù)的梯度是式中，，若令，則有上式中

是第k次迭代中前后迭代點(diǎn)的矢量差，稱他為位移矢量，并為簡(jiǎn)化書(shū)寫(xiě)而是前后迭代點(diǎn)的梯度矢量差由以上三式得海賽矩陣與梯度間的關(guān)系式由上式，用第k+1次構(gòu)造矩陣近似代替，則上式通常稱為擬牛頓條件或擬牛頓方程DFP法構(gòu)造矩陣的遞推公式（推導(dǎo)過(guò)程略）Ak+1=Ak+△Ak的確定取決于第k次迭代由上式可以看出，構(gòu)造矩陣中的下列信息：上次的構(gòu)造矩陣Ak，迭代點(diǎn)位移矢量迭代點(diǎn)的梯度增量

，因此，不必作二階導(dǎo)數(shù)矩陣及其求逆的計(jì)算對(duì)DFP法幾個(gè)問(wèn)題的說(shuō)明與討論⑴DFP公式總有確切的解⑵構(gòu)造矩陣的正定性⑶DFP法搜索方向的共軛性⑷關(guān)于算法的穩(wěn)定性DFP算法的迭代步驟步驟⑴任取初始點(diǎn)給出迭代精度ε.計(jì)算初始點(diǎn)精度若

轉(zhuǎn)步驟⑺，及其模否則進(jìn)行下一步。⑵置k←0，取Ak←E⑶計(jì)算迭代方向沿

方向做一維搜索求優(yōu)化步長(zhǎng)

，使確定下一個(gè)迭代點(diǎn)，若⑷計(jì)算

的梯度

及其模則轉(zhuǎn)步驟⑺，否則轉(zhuǎn)下一步⑸計(jì)算位移矢量

和梯度矢量按DFP公式計(jì)算構(gòu)造矩陣⑹置k←k+1。若k<n(n為優(yōu)化問(wèn)題