第三章 無(wú)約束最優(yōu)化方法本章開(kāi)始討論無(wú)約束優(yōu)化問(wèn)題

（3.1）

的計(jì)算方法。所介紹的幾個(gè)算法基本上都屬于下降算法。前面已經(jīng)講過(guò)了步長(zhǎng)的求法，記憶未搜索。所以現(xiàn)在構(gòu)造算法的關(guān)鍵在于如何選取搜索方向。根據(jù)選取搜說(shuō)方向是否使用目標(biāo)函數(shù)的導(dǎo)數(shù)，可將無(wú)約束優(yōu)化算法分為兩類(lèi)：一類(lèi)稱(chēng)為解析法，本章將介紹最速下降法，Newton法，共軛梯度法和擬Newton法，它們都使用目標(biāo)函數(shù)的導(dǎo)數(shù)；另一類(lèi)稱(chēng)為直接法，不使用導(dǎo)數(shù)。本章將介紹Powell的方向加速法。在介紹具體的算法之前，我們先來(lái)討論問(wèn)題（3.1）的極小點(diǎn)所應(yīng)具有的特征，即所謂的最優(yōu)性條件。§3.1

無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)性條件本節(jié)將給出問(wèn)題（3.1）的局部極小點(diǎn)的一階、二階必要條件和二階充分條件，這是一個(gè)古典極值問(wèn)題，在微積分學(xué)中已經(jīng)有所研究，那里給出了定義在幾何空間上的實(shí)函數(shù)極值存在的條件，這一節(jié)只是把已有理論在n維歐氏空間中加以推廣。定理

3.1.1（一階必要條件）若

為

的局部極小點(diǎn)，且在

的某領(lǐng)域內(nèi)

具有一階連續(xù)偏導(dǎo)數(shù)，則

=

=0。證明：若使

＜0.

由微分學(xué)中值定理，存在≠0，則存在方向

∈

（例如

=－

）使得成立。由于

在

的某領(lǐng)域內(nèi)連續(xù)，故存在

＞0使有，有

＜0。所以，對(duì)＜

。這與從定理的證明中可以看出，是

的局部極小點(diǎn)矛盾。=0并不能區(qū)分出極小點(diǎn)、極大點(diǎn)或鞍點(diǎn)。要區(qū)分必須進(jìn)一步考察

的二階導(dǎo)數(shù)，即考察

的Hesse矩陣§3.1

無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)性條件定理

3.1.2（二階充分條件）若在

的某領(lǐng)域內(nèi)

有二階連續(xù)偏導(dǎo)數(shù)，且

=0，=

正定，則

為問(wèn)題（3.1）的嚴(yán)格局部極小點(diǎn)。定理

3.1.3（二階必要條件）若

為

的局部極小點(diǎn)，且在

的某領(lǐng)域內(nèi)

有二階連續(xù)偏導(dǎo)數(shù)，則

=0，

半正定。定理

3.1.4設(shè)

在

上是凸函數(shù)，且有一階連續(xù)偏導(dǎo)數(shù)，則

為的整體極小點(diǎn)的充分必要條件是

=0。證明略?！?.1

無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)性條件§3.2

最速下降法對(duì)于無(wú)約束最優(yōu)化問(wèn)題，前面提到過(guò)，我們主要考慮下降算法。為了求其最優(yōu)解，人們總希望從某點(diǎn)出發(fā)，選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向，以利于盡快達(dá)到極小點(diǎn)。正是基于這樣一種愿望，早在1847年法國(guó)數(shù)學(xué)家Cauchy提出了最速下降法。這是求無(wú)約束極值的最早的數(shù)值方法?，F(xiàn)在一個(gè)很自然的問(wèn)題是，沿怎樣的方向

，

下降最快？由Taylor公式，由于

，其中

為

與當(dāng)

，

固定時(shí)，

=1使

取最小值，從而的夾角，下降最多，即當(dāng)

=0時(shí)，

下降最快，此時(shí)

=

。因此，下降最快，我們稱(chēng)之為最速下降方負(fù)梯度方向使目標(biāo)函數(shù)向。§3.2.1

最速下降法最速下降法迭代公式是計(jì)算步驟如下：給定初點(diǎn)

，允許誤差

＞0，令k=0。計(jì)算搜索方向，（3）若

，則由一維搜索步長(zhǎng)（4）令，停止；否則令，使得，k=k+1，轉(zhuǎn)步驟（2）。，設(shè)初始點(diǎn)為。例

3.2.1

用最速下降法求解解：，顯然，目標(biāo)函數(shù)是正定二次函數(shù)，有唯一的極小點(diǎn)

?？梢宰C明，如果

是正定二次函數(shù)，則由精確一維搜索確定步長(zhǎng)滿(mǎn)足

，故，對(duì)正定二次目標(biāo)函數(shù)，算法3.2.1的迭代公式如下由于

，所以由上式可得類(lèi)似地計(jì)算下去，并可用歸納法證明，算法3.2.1產(chǎn)生如下點(diǎn)列顯然，

，可見(jiàn)對(duì)所給目標(biāo)函數(shù)，算法是整體收斂的，收斂速度是線(xiàn)性的。§3.2.1

最速下降法o由所給點(diǎn)列描繪在下圖中，從圖上可以看出，兩個(gè)相鄰的搜索方向是正交的。§3.2.1

最速下降法§3.2.2

收斂性最速下降法的優(yōu)點(diǎn)是算法簡(jiǎn)單，每次迭代計(jì)算量小，占用內(nèi)存量小，即使從一個(gè)不好的初始點(diǎn)出發(fā)，往往也能收斂到局部極小點(diǎn)，但他有一個(gè)嚴(yán)重缺點(diǎn)就是收斂速度慢。沿負(fù)梯度方向函數(shù)值下降很快的說(shuō)法，容易使人們產(chǎn)生一種錯(cuò)覺(jué)，認(rèn)為這一定是最理想的搜索方向，沿該方向搜索時(shí)收斂速度應(yīng)該很快，然而事實(shí)證明，梯度法的收斂速度并不快。特別是對(duì)于等值線(xiàn)（面）具有狹長(zhǎng)深谷形狀的函數(shù)，收斂速度更慢。其原因是由于每次迭代后下一次搜索方向

總是與前一次方向

相互垂直，如此繼續(xù)下去就產(chǎn)生所謂的鋸齒現(xiàn)象（如右圖所示）。即從直觀(guān)上看，在遠(yuǎn)離極小點(diǎn)的地方每次迭代可能使目標(biāo)函數(shù)有較大的下降，但是在接近極小點(diǎn)的地方，由于鋸齒現(xiàn)象，從而導(dǎo)致每次迭代進(jìn)行距離縮短，因而收斂速度不快?！?.3

Newton法上節(jié)講過(guò)，最速下降法因迭代路線(xiàn)呈鋸齒形，故收斂速度慢，僅是線(xiàn)性的。其實(shí)，最速下降法的本質(zhì)是用線(xiàn)性函數(shù)去近似目標(biāo)函數(shù)。因此，要想得到快速算法，需要考慮目標(biāo)函數(shù)的高階逼近。如果目標(biāo)函數(shù)在上具有連續(xù)的二階偏導(dǎo)數(shù)，其Hesse矩陣

了簡(jiǎn)便起見(jiàn)，記正定并且可以表達(dá)成為顯式（今后為），那么可以使用下述的Newton法。這種方法一旦好用，收斂速度是很快的。它是一維搜索Newton切線(xiàn)法的推廣。§3.3.1Newton法設(shè)

為

的極小點(diǎn)的一個(gè)近似，將

在

附近作Taylor展開(kāi)，有其中一極小點(diǎn)，將它取為正定，則

有唯。由一階必要條，若的下一次近似=0，即件知，

應(yīng)滿(mǎn)足令

（3.11），其中應(yīng)滿(mǎn)足方程組（3.12）稱(chēng)為Newton方程，從中解出（3.12），并帶入（3.11）得

（3.13）我們稱(chēng)（3.11）、（3.12）為Newton迭代公式，有時(shí)也稱(chēng)(3.13)為Newton迭代公式。根據(jù)上面的推導(dǎo)，我們得到如下算法:已知目標(biāo)函數(shù)

及其梯度

，Hesse矩陣

，終止限

。；置k=0。選定初始點(diǎn)

；計(jì)算計(jì)算

。由方程

解出

。計(jì)算。（5）判別終止準(zhǔn)則是否滿(mǎn)足：如滿(mǎn)足，則打印最優(yōu)解（

）結(jié)束；否則，置k=k+1，轉(zhuǎn)（2）?！?.3.1

Newton法例

3.3.1

用Newton法求解，初始點(diǎn)取為解：梯度為，Hesse矩陣為，。由迭代公式得例

3.3.2

問(wèn)題具有極小點(diǎn)。，用Newton法求解此問(wèn)題，則得到迭代點(diǎn)如下所示：若取初始點(diǎn)為k0123456§3.3.1

Newton法從上述例子，我們看到用Newton法求解，只經(jīng)一輪迭代就得到最優(yōu)解。這一結(jié)果并不是偶然的，因?yàn)閺腘ewton方向的構(gòu)造我們知道，對(duì)于正定二次函數(shù)，Newton方向就是指向其極小點(diǎn)的方向。因此，用Newton法解目標(biāo)函數(shù)為正定二次函數(shù)的無(wú)約束最優(yōu)化問(wèn)題，只需一次迭代就可得到最優(yōu)解。對(duì)于目標(biāo)函數(shù)是非二次函數(shù)的非約束最優(yōu)化問(wèn)題，一般地說(shuō)，用Newton法通過(guò)有限輪迭代并不能保證可求得最優(yōu)解。但由于目

標(biāo)函數(shù)在最優(yōu)解附近能近似于二次函數(shù)，因此當(dāng)先取接近于最優(yōu)解的初始點(diǎn)使用Newton法求解時(shí)，其收斂速度一般是較快的。事實(shí)

上，可以證明在初始點(diǎn)里最優(yōu)解不遠(yuǎn)的條件下，Newton法是二次

收斂的。但是當(dāng)初始點(diǎn)選的離最優(yōu)解太遠(yuǎn)時(shí)，Newton法并不一定

是收斂的方法，甚至連其下降性也很難保證?！?.3.1

Newton法§3.3.2

Newton法的優(yōu)缺點(diǎn)Newton法有很快的收斂速度，但它只是局部收斂的。對(duì)Newton法的優(yōu)缺點(diǎn)的討論是發(fā)展有效算法的關(guān)鍵，為此，我們把它們列于下。優(yōu)點(diǎn)：（1）如果

正定且初始點(diǎn)合適，算法是二階收斂的。（2）對(duì)正定二次函數(shù)，迭代一次就可得到極小點(diǎn)。缺點(diǎn)：（1）對(duì)多數(shù)問(wèn)題算法不是整體收斂的。，該方非正定），在每次迭代中需要計(jì)算

。每次迭代需要求解線(xiàn)性方程組，程組有可能是奇異或病態(tài)的（有時(shí)可能不是下降方向。（4）收斂于鞍點(diǎn)或極大點(diǎn)的可能性并不小?！?.3.3

Newton法的改進(jìn)為了克服Newton法的缺點(diǎn)，人們保留選取Newton方向作為搜索方向，采用一維搜索確定最優(yōu)步長(zhǎng)，由此產(chǎn)生的算法稱(chēng)為修正Newton法（或阻力Newton法）。其迭代步驟如下：（1）選取初始點(diǎn)（2）計(jì)算

，若（3）構(gòu)造Newton方向。計(jì)算，取，令k=0。停止迭代，輸出

，否則轉(zhuǎn)（3）。。。（4）進(jìn)行一維搜索。求令，使得，k=k+1，轉(zhuǎn)（2）。修正Newton法克服了Newton法的缺點(diǎn)。特別是，當(dāng)?shù)c(diǎn)接近于最優(yōu)解時(shí)，此法具有收斂速度快的優(yōu)點(diǎn)，對(duì)初始點(diǎn)的選擇要求不嚴(yán)。但是，修正Newton法仍需要計(jì)算目標(biāo)函數(shù)的Hesse矩陣和逆矩陣，所以計(jì)算量和存貯量均很大。另外，當(dāng)目標(biāo)函數(shù)的Hesse矩陣在某點(diǎn)出現(xiàn)奇異時(shí)，迭代將無(wú)法進(jìn)行，因此修正Newton法仍有局限性?！?.4

共軛方向法和共軛梯度法對(duì)于n元正定二次目標(biāo)函數(shù)，從任意初始點(diǎn)出發(fā)，如果經(jīng)過(guò)有限次迭代就可得到極小點(diǎn)，那么這種算法稱(chēng)為具有二次終止性。下面將要介紹的共軛方向法，就是建立在二次模型基礎(chǔ)上，并且具有二次終止性。這類(lèi)算法的效果介于最速下降法和Newton法之間，既能克服最速下降法的慢收斂性，又避免了Newton法的計(jì)算量大和具有局部收斂性的缺點(diǎn)，因而是比較有效的算法。值得指出的是，共軛方向法中的共軛梯度法，由于其存貯量小，可用來(lái)求解大規(guī)模（n較大）無(wú)約束優(yōu)化問(wèn)題。§3.4.1共軛方向法定義3.4.1

共軛向量設(shè)G為n階正定矩陣，=0，i，j=1，2，……k，i≠j為n維向量組，如果則稱(chēng)向量組關(guān)于G共軛。=0，即是正交的，所以共如果G=I，則化為軛概念是正交概念的推廣。定理3.4.1設(shè)G為n階正定矩陣，非零向量組量組線(xiàn)性無(wú)關(guān)。推論1設(shè)G為n階正定矩陣，非零向量組關(guān)于G共軛，則此向關(guān)于G共軛，則此向量組構(gòu)成n維向量空間

的一組基。推論2設(shè)G為n階正定矩陣，非零向量組關(guān)于G共軛，則v=0。關(guān)于G共軛。若向量v與定義3.4.2設(shè)n維向量組，稱(chēng)向量集合線(xiàn)性無(wú)關(guān)，為由點(diǎn)

與生成的k維超平面。引理3.4.2設(shè)為連續(xù)可微的嚴(yán)格凸函數(shù)，又為一組線(xiàn)性無(wú)，則

是

在

與上的唯一極小點(diǎn)的充分必要條件是

=0，關(guān)的n維向量，所生成的k維超平面i=1，2，……，k定理3.4.3設(shè)G為n階正定矩陣，向量組由任意初始點(diǎn)關(guān)于G共軛，對(duì)正定二開(kāi)始，依次進(jìn)行k次精確，i=1，2，……，k=0，i=1，2，……，k次函數(shù)一維搜索則（i）（ii）

是二次函數(shù)在k維超平面

上的極小點(diǎn)。§3.4.1共軛方向法一般地，在n維空間中可以找出n個(gè)互相共軛的方向，對(duì)于n元正定二次函數(shù)，從任意初始點(diǎn)出發(fā)，順次沿這n個(gè)共軛方向最多作n次直線(xiàn)搜索就可以求得目標(biāo)函數(shù)的極小點(diǎn)。這就是共軛方向法的算法形成的基本思想。二次函數(shù)的共軛方向法的迭代步驟：已知具有正定矩陣G的二次目標(biāo)函數(shù)

和終止限

。給定初始點(diǎn)

及下降方向

，置k=0。作精確一維搜索

，求步長(zhǎng)

。令

。（4）若

，則（5）取共軛方向

使得，停；否則，轉(zhuǎn)步驟（5）。=0，i=0，1，……，k（6）令k=k+1，轉(zhuǎn)步驟（2）?！?.4.1

共軛方向法§3.4.2

共軛梯度法如果在共軛方向法中初始的共軛向量恰好取為初始點(diǎn)

處的負(fù)梯度

，而以下各共軛方向

由第k迭代點(diǎn)

處的負(fù)梯度與已經(jīng)得到的共軛向量

的線(xiàn)性組合來(lái)確定，那么就構(gòu)成了一種具體的共軛方向法。因?yàn)槊恳粋€(gè)共軛向量都是依賴(lài)于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來(lái)的，所以稱(chēng)為共軛梯度法。設(shè)從任意點(diǎn)當(dāng)搜索得到點(diǎn)處的負(fù)梯度方向，k=0，1，……n+2來(lái)產(chǎn)生搜索方向。為了選擇

（k=0，1，……，n-2）是所產(chǎn)生的和（

k=0，1，……，n-2）是G共軛，以于是有右乘上式的兩端，因?yàn)橐?/p>

和

是G共軛，應(yīng)有故由上式得=0，綜上所述，可以生成n個(gè)方向§3.4.2共軛梯度法出發(fā)，第一個(gè)搜索方向取為后，設(shè)以下按§3.4.2

共軛梯度法上式含有目標(biāo)函數(shù)系數(shù)矩陣，這對(duì)于目標(biāo)函數(shù)是非二次函數(shù)的問(wèn)題是不方便的。通過(guò)簡(jiǎn)化，一般可以利用目標(biāo)函數(shù)的梯度信息，來(lái)產(chǎn)生n個(gè)共軛方向由此得共軛梯度法?！?.4.2

FR共軛梯度法是Fletcher和Reeves在1964年得到的，故稱(chēng)Fletcher－Reeves公式，簡(jiǎn)稱(chēng)FR公式。對(duì)于一般函數(shù)，將FR公式與

，

結(jié)合產(chǎn)生搜索方向，即得如下的FR共軛梯度法：給定初始點(diǎn)

，k=1，給定控制誤差

。計(jì)算若

，則

停；否則令。由精確一維搜索確定步長(zhǎng)令，滿(mǎn)足轉(zhuǎn)步驟（2）。用FR共軛梯度法求解。例3.4.1取初始點(diǎn)解：，故取，從

出發(fā)，沿

作一維搜因索，即求的極小點(diǎn)，得步長(zhǎng)。于是得到。由FR公式得故。從出發(fā)，沿作一維搜索，求的極小點(diǎn)，解之得，于是。此時(shí)，故?！?.4.2

FR共軛梯度法Polak-Ribiere-Polyak公式：注意到

=0，故

。此式是Polak和Ribiere以及Polyak分別于1969年提出的，故稱(chēng)Polak-Ribiere-Polyak公式，簡(jiǎn)稱(chēng)PRP公式。，在FR共軛梯度法步驟（3）中用PRP公式代替FR公式，就得PRP共軛梯度法。對(duì)于正定二次函數(shù)，F(xiàn)R共軛梯度法與PRP共軛梯度法等價(jià)。但是對(duì)于一般函數(shù)，二者是不同的，并且由于目標(biāo)函數(shù)的Hesse陣不是常數(shù)矩陣，因而迭代過(guò)程中所產(chǎn)生的方向不再是共軛方向了。不過(guò)兩個(gè)算法所產(chǎn)生的搜索方向都滿(mǎn)足故二者都是下降算法。從一些實(shí)際計(jì)算的結(jié)果發(fā)現(xiàn)，PRP算法一般優(yōu)于FR算法?！?.4.2

PRP共軛梯度法現(xiàn)在考慮對(duì)共軛梯度法進(jìn)行改進(jìn)。我們知道，在最優(yōu)解附近，目標(biāo)函數(shù)與一個(gè)正定二次函數(shù)很接近。因此，當(dāng)?shù)c(diǎn)進(jìn)入目標(biāo)函數(shù)逼近正定二次函數(shù)的區(qū)域后，如

果我們能及時(shí)產(chǎn)生接近于共軛方向的搜索方向，則就能較迅速地收斂到最優(yōu)解。然而，對(duì)于PRP和FR算法來(lái)說(shuō)，如果初始方向不取負(fù)梯度方向，則即使應(yīng)用于二次函數(shù)，也往往不能產(chǎn)生n個(gè)共軛方向（參看習(xí)題3.11）。因此，我們?cè)O(shè)想，當(dāng)在現(xiàn)行迭代點(diǎn)目標(biāo)函數(shù)與正定二次函數(shù)很接近時(shí)，重新取負(fù)梯度方向?yàn)樗阉鞣较?，那么后面幾次迭代，將產(chǎn)生近似的共軛方向，從而提高了算法的效率?；谏鲜鱿敕?，對(duì)共軛梯度法進(jìn)行如下修改：每迭代n或n+1次，就重新取負(fù)梯度方向?yàn)樗阉鞣较?，這樣得到的算法，稱(chēng)為n步重新開(kāi)始的共軛梯度法?！?.4.3

n步重新開(kāi)始的共軛梯度法n步重新開(kāi)始的PRP共軛梯度法：，k=1，給定控制誤差

。，若

，則

，停；否則，給定初始點(diǎn)計(jì)算轉(zhuǎn)步驟（3）。若k是n+1的倍數(shù)，則

。否則，令由精確一維搜索確定步長(zhǎng)

，令

轉(zhuǎn)步驟（2）。如果在步驟（3）中，用FR公式代替PRP公式，則得到n步重新開(kāi)始的FR共軛梯度法?！?.4.3

n步重新開(kāi)始的共軛梯度法前面介紹了Newton法，它的突出優(yōu)點(diǎn)是收斂很快。但是，運(yùn)用Newton法需要計(jì)算二階偏導(dǎo)

數(shù)，而且目標(biāo)函數(shù)的Hesse矩陣可能非正定，為了克服Newton法的缺點(diǎn)，人們提出了擬Newton法。它的基本思想是用不包含二階導(dǎo)數(shù)的矩陣近似

Newton法中的Hesse矩陣的逆矩陣。由于構(gòu)造近

似矩陣的方法不同，因而出現(xiàn)不同的擬Newton法。經(jīng)理論證明和實(shí)踐檢驗(yàn)，擬Newton法已經(jīng)成為一類(lèi)公認(rèn)的比較有效的算法?！?.5

擬Newton法§3.5.1

擬Newton法的基本思想最速下降法和阻尼Newton法的迭代公式可以統(tǒng)一表示為，其中

為步長(zhǎng)，

，

為n階對(duì)稱(chēng)矩陣。在上式中，若令

，則是最速下降法；若令

，就是阻尼Newton法。前者具有較好的整體收斂性，但收斂速度太慢；后者雖收斂性差，且需要計(jì)算二階導(dǎo)數(shù)，計(jì)算量大。因此，如果能做到的選取既能逐步逼近

，又不需要計(jì)算二階導(dǎo)數(shù)，那么由此算法就有可能比最速下降法快，又比Newton法計(jì)算簡(jiǎn)單，且整體收斂性好。為了使

確實(shí)能有上述特點(diǎn)，必須對(duì)

附加一些條件：C1：

是對(duì)稱(chēng)正定矩陣。這是為使算法具有下降性質(zhì)。顯然，當(dāng)

正定時(shí)，從而

為下降方向。C2：

由

經(jīng)簡(jiǎn)單形式修正而得，

稱(chēng)為修正公式，其中稱(chēng)為修正矩陣。C3：

滿(mǎn)足所謂的擬Newton方程（后面將推導(dǎo)此方程）。§3.5.1

擬Newton法的基本思想我們希望經(jīng)過(guò)對(duì)任意初始矩陣

的逐步修正能得到

的一個(gè)好的逼近。能做到這點(diǎn)的一個(gè)方法如下：令

，由Taylor公式，有當(dāng)

非奇異時(shí)，有

對(duì)于二次函數(shù)，此式為等式。

因?yàn)槟繕?biāo)函數(shù)在極小點(diǎn)附近的性態(tài)與二次函數(shù)近似，所以一個(gè)合理的想法就是：如果使得

滿(mǎn)足

此式稱(chēng)為擬Newton方程。

那么

就可以較好地近似

。顯然，由于

有

個(gè)未知數(shù)，n個(gè)方程，所以一般有無(wú)窮多個(gè)解，故由擬Newton方程確定的是一族算法，稱(chēng)之為擬Newton法。事實(shí)上有些擬Newton法不具備C1，通常稱(chēng)具備條件C1的擬Newton法為變尺度法。§3.5.2

DFP算法DFP算法是Davidon（1959）提出的，后來(lái)Fletcher和Powell（1963）作了改進(jìn)，形成了Davidon-Fletcher-Powell算法，簡(jiǎn)稱(chēng)DFP算法。它是第一個(gè)被提出的擬Newton法，也是無(wú)約束最優(yōu)化問(wèn)題的最有效的算法之

一，已被廣泛地采用。如前所訴，擬Newton法首先要解決的問(wèn)題是如何構(gòu)造據(jù)陣列

，使其滿(mǎn)足條件C1-C3?？紤]修正矩陣由擬Newton方程有，其中u，v為n維待定向量。，滿(mǎn)足這個(gè)方程的待定向量u和v有無(wú)窮多種取法、一個(gè)明顯的取法是令

和

，而

和

的值由及

確定，利用

的對(duì)稱(chēng)性可導(dǎo)出公式稱(chēng)此公式為DFP修正公式。§3.5.2

DFP算法DFP算法迭代步驟如下：（1）給定初始點(diǎn)

，初始矩陣（通常取單位陣）計(jì)算

，令k=0，給定控制誤差

。令

。由精確一維搜索確定步長(zhǎng)

，。，則

停；（4）令（5）若否則令，（6）由DFP修正公式得。。令k=k+1，轉(zhuǎn)步驟（2）§3.5.2

DFP算法例

3.5.1

用DFP算法求解，取解：（i）求迭代點(diǎn)

，令得

的極小點(diǎn)為，所以，于是，由DFP修正公式有下一個(gè)搜索方向?yàn)椋╥i）求迭代點(diǎn)

，令其極小點(diǎn)為

，于是所以，為正定陣，為嚴(yán)格凸函數(shù)，所以，因Hesse陣為整體極小點(diǎn)。還可以驗(yàn)證，再用一次DFP修正公式，則得§3.5.2

DFP算法由上述計(jì)算過(guò)程知，對(duì)所給的二維正定二次函數(shù)，DFP算法只須迭代兩次，就可得到極小點(diǎn)，因此，是非常有效的。事實(shí)上，對(duì)一般的n維正定二次函數(shù)，DFP算法具有二次終止性。對(duì)于一般函數(shù)，DFP算法的效果也很好，它比最速下降法以及共軛梯度法要有效得多。DFP算法具有下列一些重要的性質(zhì)。（1）對(duì)于正定二次函數(shù)：；；至多經(jīng)過(guò)n次迭代即終止，且保持滿(mǎn)足前面的擬Newton方程產(chǎn)生的搜索方向是共軛方向；（2）對(duì)于一般函數(shù)：保持矩陣

的正定性，從而確保了算法的下降性；算法為超線(xiàn)性收斂速度；對(duì)于凸函數(shù)是整體收斂的；每次迭代需要

次乘法運(yùn)算（注意Newton法需要 次）?！?.5.3DFP算法的正定性及二次終止性引理3.5.1設(shè)，H為正定矩陣，且y≠0，s≠0，則

為正定矩陣的充分必要條件是。定理3.5.2（DFP修正公式的正定繼承性）正定，則整個(gè)矩陣列在DFP算法中，如果初始矩陣定的。定理3.5.3將DFP算法用于目標(biāo)函數(shù)都是正。設(shè)初始矩陣

是正定的，產(chǎn)生的迭代點(diǎn)是互異的，并設(shè)產(chǎn)生的搜索方向?yàn)?/p>

，則（i）

（ii）推論（DFP算法的二次終止性）在定理3.5.3的條件下，我們有（i）DFP算法至多迭代n次就可得到極小點(diǎn)，即存在，使。（ii）若，則。證明略?！?.5.4

BFGS算法我們?cè)俳榻B另一個(gè)有效和著名的擬Newton法。由于它是Broyden，F(xiàn)letcher（1970），Goldfarb（1969）和Shanno（1970）共同研究的結(jié)果，因而叫做BFGS法。考慮校正公式：其中

為參數(shù)，可取任何實(shí)數(shù)，而這族公式被成為Broyden族修正公式。容易證明，對(duì)任意

，由上式得到的

滿(mǎn)足擬Newton方程。把DFP算法中涉及DFP修正公式的部分換成上式，就得到了一族擬Newton算法，我們稱(chēng)之為Broyden族擬Newton算法。顯然，當(dāng)取取=0時(shí)，Broyden族給出的修正公式就是DFP修正公式。，得到如下修正公式：這個(gè)公式被稱(chēng)為對(duì)稱(chēng)秩1公式。它不適合用于DFP算法的框架中。然而，它有一個(gè)突出的優(yōu)點(diǎn)，就是往往比別的修正公式逼近

的程度高。當(dāng)取

=1時(shí)，得到一個(gè)新的修正公式：把他替換DFP算法中的DFP修正公式，就得到了著名的BFGS算法。在實(shí)際計(jì)算中，由于舍入誤差的存在以及一維搜索的不精確，DFP算法的效率和受到很大影響，但BFGS算法所受影響要小得多。特別是采用非精確一維搜索時(shí)，DFP算法效率很低，然而B(niǎo)FGS算法卻仍然十分有效。目前BFGS算法被公認(rèn)為最好的擬Newton算法?！?.5.4

BFGS算法§3.6

Powell方向加速法前面幾節(jié)所介紹的算法都要用到目標(biāo)函數(shù)

的一階或二階導(dǎo)數(shù)，但實(shí)際問(wèn)題中所遇到的目標(biāo)函數(shù)有時(shí)很復(fù)雜，其一、二階導(dǎo)數(shù)或是很復(fù)雜或是難以求得，甚至有時(shí)連目標(biāo)函數(shù)的解析表達(dá)式也不知道，只能通過(guò)直接測(cè)量得到某些點(diǎn)上的函數(shù)值。這時(shí)，前面所介紹的解析法就不是用了，而應(yīng)采用不使用導(dǎo)數(shù)的直接法。直接法一般對(duì)目標(biāo)函數(shù)的解析性質(zhì)不做苛刻要求，因而就目標(biāo)函數(shù)的類(lèi)型而言，適用面較廣。但是，正因?yàn)橹苯臃ㄒ话悴焕煤瘮?shù)的解析性質(zhì)，所以收斂速度較慢，同時(shí)計(jì)算量也往往隨問(wèn)題維數(shù)的增加而迅速增大。本節(jié)將介紹直接發(fā)中最有效者之一：Powell方向加速法?！?.6.1

Powell方向加速法定理3.6.1對(duì)于n維正定二次函數(shù)設(shè)

關(guān)于G共軛，

與

為不同的任意兩點(diǎn)，分別從

與

出發(fā)，依次沿

作一維搜索，并設(shè)最后一次搜和

。如果

，則

與。索得到的極小點(diǎn)為關(guān)于G共軛，即

證明略。這個(gè)定理告訴我們，通過(guò)在不同起點(diǎn)沿同一方向求極小的方法可以產(chǎn)生共軛方向。Powell正是基于這一思想，于1964年提出了所謂的方向加速法。其核心思想是：在迭代過(guò)程的每個(gè)階段都作n+1次一維搜索。首先依次沿給定的n個(gè)線(xiàn)性無(wú)關(guān)的方向

作一維搜索；再沿由這一階段的起點(diǎn)到第n次搜索所得到的點(diǎn)的連線(xiàn)方向p做一次一維搜索，并把這次所得點(diǎn)作為下一階段的起點(diǎn)，下一階段的n個(gè)搜索方向?yàn)?/p>

。§3.6.1

Powell方向加速法Powell原始算法迭代步驟如下：給定控制誤差

>0，初始點(diǎn)

，設(shè)分別為作一維搜索，得步長(zhǎng)n個(gè)坐標(biāo)軸上的單位向量。令依次沿，令，再令令作一維搜索若，則令，停；否則轉(zhuǎn)（6）（6）令，轉(zhuǎn)步驟（2）?！?.6.2

Powell改進(jìn)算法根據(jù)定理3.6.1，對(duì)于正定二次函數(shù)上述算法各階段的出發(fā)點(diǎn)和終止點(diǎn)所確定的向量畢是關(guān)于G共軛的，故至多經(jīng)過(guò)n個(gè)階段的迭代就可以求得極小點(diǎn)。因?yàn)榇怂惴ㄊ窃诘兄鸫紊晒曹椃较?，而共軛方向又是較好的搜索方向，所以稱(chēng)之為方向加速法。但是后來(lái)發(fā)現(xiàn)，有時(shí)用此算法產(chǎn)生的n個(gè)向量可能線(xiàn)性相關(guān)或近似線(xiàn)性相關(guān)，這時(shí)張不成n維空間，所以可能得不到真正的極小點(diǎn)。因此，Powell原始算法并不是很實(shí)用。為了克服上述缺點(diǎn)，Powell對(duì)其原始算法進(jìn)行了改進(jìn)。改進(jìn)后的算法雖不再具有二次終止性，但確實(shí)克服了搜索方向的線(xiàn)性相關(guān)的不利情形。Powell改進(jìn)算法是較有效的直接法之一。§3.6.2

Powell改進(jìn)算法Powell改進(jìn)算法迭代步驟如下：給定控制誤差

>0，初始點(diǎn)

，設(shè)分別為n個(gè)坐標(biāo)軸上的單位向量。令k=1。計(jì)算

，令作一維搜索

，令若k=n，轉(zhuǎn)（4）；若k<n，令k=k+1，轉(zhuǎn)（2）。，則

，停；否則轉(zhuǎn)（5）。，或（4）若（5）令（6）若則搜索方向不變，令，，，。，令轉(zhuǎn)（2）；否則轉(zhuǎn)（7）。令而令作一維搜索轉(zhuǎn)（2）。例如，已知兩維變量函數(shù)f(X)的等高線(xiàn)，內(nèi)圈比外圈函數(shù)低。圖7-3極小化f(X)時(shí)得到的正單純形序列137586421091112x1x2單純形法其思路為，首先取3個(gè)點(diǎn)（n+1=2+1）X(1)，X(2)，X(3)，并

計(jì)算函數(shù)值f(X(1))，f(X(2))，f(X(3))。然后比較大?。ㄟ@三個(gè)點(diǎn)稱(chēng)為初始單純形）。發(fā)現(xiàn)f(X(3))最大，舍去f(X(3))，找出余下兩點(diǎn)X(1)和X(2)的形心點(diǎn)，連結(jié)X(3)與形心點(diǎn)并延

長(zhǎng)找出X(3)關(guān)于形心點(diǎn)的對(duì)稱(chēng)點(diǎn)X(4)，再用X(1)，X(2)和X(4)構(gòu)成新的正多面體，繼續(xù)前述步驟，直到找出極小點(diǎn)為止。上圖描繪了尋找f(X)極小點(diǎn)的正多面體序列。單純形法在迭代過(guò)程中，不保持每步都為正多面體，而是根據(jù)情況改變形狀。其算法步驟如下：設(shè)

X

(k)

=[x

(k)，…，x

(k)，…，x

(k)]T，

i=1，…，n+1i

i1

ij

in是搜索第k階段（k=0，1，…）上n維歐氏空間的第i個(gè)