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

第四章

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

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

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

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

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

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

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

(1)

，得第一輪的第一個迭代點x1

=x0

+(1)

(1)(1)

e

，1

1然后以x1

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

(1)

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

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

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

、…、

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

0Sk=x

k-x

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

S2

3

nS

k

S

k

Skn維目標(biāo)函數(shù)完成n環(huán)的迭代過程稱為一輪。從這一輪的終點出發(fā)沿新生方向搜索所得到的極小點，作為下一輪迭代的始點。這樣就形成了算法的循環(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)為個方向的最優(yōu)步長。若在第k環(huán)的優(yōu)化搜索過程中出現(xiàn)1(k)=0，則方向Sk表示為S2(k)、S3(k)、???、Sn(k)的線性組合，以后的各次搜索將在降維的空間進(jìn)行，無法得到n維空間的函數(shù)極小值，計算將失敗。如圖所示為一個三維優(yōu)化問題的示例，設(shè)第一環(huán)中1=0

，則新生方向與e2

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

為初始點，搜索方向為S1(k)、S2(k)、???、Sn(k)，產(chǎn)生的新方向為Sk

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

n+1(k)各點的函數(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)影射點(F3)函數(shù)下降量△爾算法的方向淘汰為了構(gòu)造第k+1環(huán)基本方向組，采用如下判別式：按照以下兩種情況處理：1、上式中至少一個不等式成立，則第k+1環(huán)的基本方1

2

n向仍用老方向組S

(k)、S

(k)、???、S

(k)。k+1環(huá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)的初始點取0x

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

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

x(K)-x

(k)

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

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

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

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

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

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

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

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

，(k)其中g(shù)(k)是函數(shù)F(x)在迭代點x(k)處的梯度一般采用一維搜索的最優(yōu)步長，即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此式表明，相鄰的兩個迭代點的梯度是彼此正交的。也即在梯度的迭代過程中，相鄰的搜索方向相互垂直。梯度法向極小點的逼近路徑是鋸齒形路線，越接近極小點，鋸齒越細(xì)，前進(jìn)速度越慢。這是因為梯度是函數(shù)的局部性質(zhì)，從局部上看，在該點附近函數(shù)的下降最快，但從總體上看則走了許多彎路，因此函數(shù)值的下降并不快。二、迭代終止條件？若滿足輸出最優(yōu)解采用梯度準(zhǔn)則：||

g(k)

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

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

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

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

(k)g(k)

,令k=k+1

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

x(0)計算：g(k)k=k+1沿g(k)方向一維搜索，求最優(yōu)步長(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ù)已知初始點迭代精度ε=0.005解：函數(shù)的梯度第一次迭代：以為起點沿一方向作一維搜索得第一個迭代點繼續(xù)第二次迭代到第五次迭代結(jié)束時，有故迭代可終止，最優(yōu)解為迭代數(shù)據(jù)表見課本表4.2共軛梯度法共軛梯度法是共軛方向法的一種，因為該方法中每一個共軛向量都是依賴于迭代點處的負(fù)梯度而構(gòu)造出來的，所以稱作共軛梯度法。一、共軛梯度法的搜索方向共軛梯度法的搜索方向采用梯度法基礎(chǔ)上的共軛方向，如圖所示，目標(biāo)函數(shù)F(x)在迭代點xk+1處的負(fù)梯度為-f(xk+1)，該方向與前一搜索方向Sk互為正交，在此基礎(chǔ)上構(gòu)造一種具有較高收斂速度的算法，該算法的搜索方向要滿足以下兩個條件：（1）以xk+1點出發(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）選初始點x0和收斂精度

。（2）令k=0，計算S0

=

-

f(x0)

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

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

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)

+計算：

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

f(x0)x0=xk+1Nk

n

？YSk+1

=

-f(xk+1)

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

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

(x)為設(shè)x(k+1)為(x)極小點，根據(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

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

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

(k+1)

=

x

(k)

-

(k)

H

-1gk

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

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

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

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

點處沿

方向移位搜索求得最優(yōu)步長故新迭代點為該點的梯度迭代即可結(jié)束由于目標(biāo)函數(shù)是二次正定函數(shù)，故迭代一次即達(dá)到最優(yōu)點三、阻尼牛頓法的特點優(yōu)點：由于阻尼牛頓法每次迭代都在牛頓方向進(jìn)行一維搜索，避免了迭代后函數(shù)值上升的現(xiàn)象，從而保持了牛頓法的二次收斂性，而對初始點的選擇沒有苛刻的要求。缺點：1、對目標(biāo)函數(shù)要求苛刻，要求函數(shù)具有連續(xù)的一、二階導(dǎo)數(shù)；為保證函數(shù)的穩(wěn)定下降，海賽矩陣必須正定；為求逆陣要求海賽矩陣非奇異。2、計算復(fù)雜且計算量大，存儲量大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)分析比較這兩種方法可知：梯度法的搜索方向為-g(k)，只需計算函數(shù)的一階偏導(dǎo)數(shù)，計算量小，當(dāng)?shù)c遠(yuǎn)離最優(yōu)點時，函數(shù)值下降很快，但當(dāng)?shù)c接近最優(yōu)點時收斂速度極慢。牛頓法的搜索方向為-H

-1

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

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

n階對稱矩陣，它是隨迭代點的位置的變化而變化的。若Ak

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

=H

-1

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

gk

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

=

x(k)

-

(k)Ak

gkDFP法構(gòu)造矩陣序列的產(chǎn)生構(gòu)造矩陣是隨迭代過程的推進(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)。在點

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

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

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

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

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

，使確定下一個迭代點，若⑷計算

的梯度

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

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