經(jīng)典最優(yōu)化方法

1、第九章經(jīng)典最優(yōu)化方法9.1最優(yōu)化的基本概念 TOC o 1-5 h z 最優(yōu)化方法是一門(mén)古老而又年青的學(xué)科。這門(mén)學(xué)科的源頭可以追溯到17世紀(jì)法國(guó)數(shù)學(xué)家拉格朗日關(guān)于一個(gè)函數(shù)在一組等式約束條件下的極值問(wèn)題（求解多元函數(shù)極值的Lagrange乘數(shù)法）。19世紀(jì)柯西引入了最速下降法求解非線性規(guī)劃 問(wèn)題。直到20世紀(jì)三、四十年代最優(yōu)化理論的研究才出現(xiàn)了重大進(jìn)展，1939年前蘇聯(lián)的康托洛維奇提出了解決產(chǎn)品下料和運(yùn)輸問(wèn)題的線性規(guī)劃方法；1947年美國(guó)的丹奇格提出了求解線性規(guī)劃的單純形法， 極大地推動(dòng)了線性規(guī)劃理論的發(fā) 展。非線性規(guī)劃理論的開(kāi)創(chuàng)性工作是在 1951年由庫(kù)恩和塔克完成的，他們給出 了非線性規(guī)劃的

2、最優(yōu)性條件。隨著計(jì)算機(jī)技術(shù)的發(fā)展，各種最優(yōu)化算法應(yīng)運(yùn)而生。 比較著名的有DFP和BFGS無(wú)約束變尺度法、HP廣義乘子法和 WHP約束變尺 度法。最優(yōu)化問(wèn)題本質(zhì)是一個(gè)求極值問(wèn)題，幾乎所有類型的優(yōu)化問(wèn)題都可概括為如 下模型：給定一個(gè)集合（可行集）和該集合上的一個(gè)函數(shù)（目標(biāo)函數(shù)），要計(jì)算此函數(shù)在集合上的極值。通常，人們按照可行集的性質(zhì)對(duì)優(yōu)化問(wèn)題分類：如果可 行集中的元素是有限的，則歸結(jié)為“組合優(yōu)化”或“網(wǎng)絡(luò)規(guī)劃”，如圖論中最短路、最小費(fèi)用最大流等；如果可行集是有限維空間中的一個(gè)連續(xù)子集，則歸結(jié)為“線性或非線性規(guī)劃”；如果可行集中的元素是依賴時(shí)間的決策序列，則歸結(jié)為 “動(dòng)態(tài)規(guī)劃”；如果可行集是無(wú)窮維空

3、間中的連續(xù)子集，則歸結(jié)為“最優(yōu)控制”。線性規(guī)劃與非線性規(guī)劃是最優(yōu)化方法中最基本、最重要的兩類問(wèn)題。一般來(lái)說(shuō)，各優(yōu)化分支有其相應(yīng)的應(yīng)用領(lǐng)域。線性規(guī)劃、網(wǎng)絡(luò)規(guī)劃、動(dòng)態(tài)規(guī) 劃通常用于管理與決策科學(xué)；最優(yōu)控制常用于控制工程；非線性規(guī)劃更多地用于 工程優(yōu)化設(shè)計(jì)。前面提到的算法是最優(yōu)化的基本方法， 它們簡(jiǎn)單易行，對(duì)于性態(tài)優(yōu)良的一般 函數(shù)，優(yōu)化效果較好。但這些經(jīng)典的方法是以傳統(tǒng)微積分為基礎(chǔ)的，不可避免地 帶有某種局限性，主要表現(xiàn)為：大多數(shù)傳統(tǒng)優(yōu)化方法僅能計(jì)算目標(biāo)函數(shù)的局部 最優(yōu)點(diǎn)，不能保證找到全局最優(yōu)解。對(duì)于多峰值函數(shù)，這些方法往往由于過(guò)分追 求“下降”而陷于局部最優(yōu)解；許多傳統(tǒng)優(yōu)化方法對(duì)目標(biāo)函數(shù)的光滑性、

4、凹凸 性等有較高的要求，對(duì)于離散型函數(shù)、隨機(jī)型函數(shù)基本上無(wú)能為力。二十世紀(jì)六、七十年代以來(lái)，人們將人工智能技術(shù)和生物進(jìn)化機(jī)理引入最優(yōu) 化方法，逐漸形成了一批完全不同于傳統(tǒng)優(yōu)化方法、令人耳目一新的現(xiàn)代優(yōu)化方法。如模擬退火、神經(jīng)網(wǎng)絡(luò)、進(jìn)化計(jì)算、模糊邏輯等，其中進(jìn)化計(jì)算中的遺傳算 法以其良好的全局搜索性成為現(xiàn)代優(yōu)化算法中最受關(guān)注的算法之一，已被廣泛應(yīng)用于函數(shù)優(yōu)化、組合優(yōu)化、自動(dòng)控制、生產(chǎn)調(diào)度、圖像與信號(hào)處理、機(jī)器人和人 工生命等領(lǐng)域。9.1.1預(yù)備知識(shí)1、梯度f(wàn)f f定義9.1對(duì)n?？晌⒑瘮?shù)f(X )=f(x1,x2；-,xn ),向量|三,旦，旦稱為f |_CXl 改2CXn在X處的梯度，記為Vf

5、(X )或gradf (X ), 稱為梯度算子或Hamilton算子。從幾何上講，Vf(X )的方向是f在X處上升最快的方向，Vf(X )的模是f在X處上升最快的速率。若Vf(X)=0,則函數(shù)曲面在X處的切平面是水平的。2、二階導(dǎo)數(shù)矩陣定義9.2設(shè)n元函數(shù)f(X )= f(xi,x2，xn)具有二階連續(xù)偏導(dǎo)數(shù)，則f的所有二 階偏導(dǎo)數(shù)構(gòu)成的矩陣f， f12-Gnl，f21f22f2n一-Jn1fn2f nn 一稱為f在X處的二階導(dǎo)數(shù)矩陣或海色(Hessain)矩陣，記為V2f(X )。顯然，V2f(X是一個(gè)對(duì)稱矩陣。在幾何上，V2f(X 放映了函數(shù)曲面的彎曲方向。若 V2f(X 0 (正定),

6、則函數(shù)曲面向上彎曲(凹)；若V2f(X)0 (負(fù)定)，則函數(shù)曲面向下彎曲(凸)例9.1設(shè)A為n階對(duì)稱矩陣，b、X為n元列向量，c為標(biāo)量，對(duì)二次函數(shù)1 f X =-XtAX bTX c求梯度 fX卜Hessain矩陣V1 2f(X卜解：可將算子、理解為對(duì)向量函數(shù)的一階、二階導(dǎo)數(shù)，易得v f X = AX b 2 f X = A3、n元函數(shù)的二階Taylor展式一元函數(shù)的Taylor展式：f (Xo)2 f(n)(X0)nf (X0：X) = f(X0) f (x0). ：x X ：XRn2!n!其中Rn =f(n1)(X0iX) (n 1)!二元函數(shù)的Taylor展式：,6 cf (X。+ Ax

7、, y0 十 Ay) = f (X0,y0)+!x +Ay f(x, y) l 改 例) TOC o 1-5 h z 1,3d 21fd3、+ 一 義+ Ayf d，y)+ + ！ Ax+Ayf(X0,y0) + Rn2! I 改cy)n! I 笈為,n 11 e. 一 一 . 一一.其中 Rn = 義一十 Ayf (x0 +e4x, y0 十BAy), 0 0 1(n+1)!、 ex硒)二元函數(shù)的二階Taylor展式：f(x0,y0).開(kāi)(x0,y0)f (X0 1-x, y0 1二y); f (X0, y0) -二x y：:x：:yA fl2 一、Be,、l2 一、c2 一、J Lx f

8、1(丁)十(Ax gy )0 f(X0,y0)十 Sy gx % f(X0,y0)+ Sy )2 f2 R22!、cXa勾cycxcyJ若引入矩陣記號(hào)X = (x, y T , X0 =僅0, y，&X = X - X0,TE ,、仿f(X0)訝(X0) i _2b=fX0 戶 r,2 ,A=v2f(X0) = ex勾)-2 _二 f(X0)n 2ex*f(X0)cycx, 2 _二 f(X0):x:y；：2f(X0)2yT1 T=f X0 bT X - XTA X R2元函數(shù)的二階Taylor展式與二元函數(shù)的二階Taylor展式形式類似。4、凸集與凸函數(shù)定義9.3設(shè)S u Rn ,若S中任兩

9、點(diǎn)的連線都屬于S ,即對(duì)任意Xi、X2 w S , 士勻有AXi十(1九)X2 w S (0九1),則稱S為一個(gè)凸集。定義9.4設(shè)f(X)為定義在凸集S上的函數(shù)，若對(duì)任意 Xi、X2WS,均有 fXi +(1九)X2】E?f(Xi )+(1)Jf(X2 ) (0”1),則稱 f(X)為 S 上的凸函 數(shù)。若上式改為嚴(yán)格不等式，則稱 f (X)為S上的嚴(yán)格凸函數(shù)。定理9.1 (一階判別條件)一階可微函數(shù)f(X)在凸集S上為凸函數(shù)的充要條件是：對(duì)任意XXzS, 均有 f(X2 心 f (Xi 汁不T f(Xi IX2 -Xi )。定理9.2 (二階判別條件)二階連續(xù)可微函數(shù)f(X)在凸集S上為凸函

10、數(shù)的充要條件是：對(duì)任意XWS, 2f(X泮正定。f(X)為嚴(yán)格凸函數(shù)的充要條件是V2f(X )正定。9.1.2最優(yōu)化的基本概念最優(yōu)化問(wèn)題的數(shù)學(xué)模型為min f (x) = f (xi,x2，Xn)s.t. gi(x) = gi(Xi，X2，Xn)之0 (i =i,2，m)f (Xi, X2，Xn)稱為目標(biāo)函數(shù)，gi(xi,x2，xn)稱為約束函數(shù)。當(dāng)f(Xi，X2，Xn)和gi(Xi,X2，Xn)均為線性時(shí)，稱之為線性規(guī)劃(LP)；當(dāng) f(Xi,X2，XnD gi(Xi,X2，Xn)至少有一個(gè)為非線性時(shí)，稱之為非線性規(guī)劃 (NLP)o對(duì)非線性規(guī)劃，如果變量x的取值范圍沒(méi)有限制，稱之為無(wú)條件極值

11、或無(wú)約 束最優(yōu)化，否則稱之為條件極值或約束最優(yōu)化。求解最優(yōu)化問(wèn)題最常用的方法是迭代法。迭代法的基本思想是：從最優(yōu)點(diǎn)的一個(gè)初始值X。出發(fā)，按一定迭代法則產(chǎn)生點(diǎn)序列xk(k=i,2,)，使目標(biāo)函數(shù)值f(xk游步減小。當(dāng)序列 小是有限點(diǎn) 列時(shí)，其最后一點(diǎn)即為最優(yōu)解；當(dāng) 是無(wú)窮點(diǎn)列時(shí)，其極限點(diǎn)x*即為最優(yōu)解。對(duì)于迭代法有下列四個(gè)問(wèn)題：如何由Xk產(chǎn)生Xk由，即迭代格式或算法結(jié)構(gòu)；迭代何時(shí)中止，即停止準(zhǔn)則或最優(yōu)性條件；迭代產(chǎn)生的序列是否收斂于最優(yōu)解x,即收斂性問(wèn)題;收斂算法的收斂速度問(wèn)題。1、最優(yōu)性條件由微積分知識(shí)不難得出下列最優(yōu)性條件。定理9.3 （一階必要條件）設(shè)f（X ）可微，若X* w Rn為f

12、（X ）的一個(gè)極小點(diǎn)，則 fX* ）=0。本定理的幾何意義是，函數(shù)在 X*處取極小值的必要條件是該函數(shù)曲面在X處的切平面是水平的；梯度為零的點(diǎn)可能是極小或極大點(diǎn)，也可能是鞍點(diǎn)即既非極小也非極大的 點(diǎn)。定理9.4 （二階充要條件）設(shè)f（X廠階連續(xù)可微，若Vf（X*）=0,且X*處的二階導(dǎo)數(shù)矩陣V2f（X*）正 定，則X*為極小點(diǎn)。本定理的幾何意乂是，X為極小點(diǎn)的充要條件是函數(shù)曲面在 X處有水平切 平面且向上彎曲。定理9.5 （凸函數(shù)的最優(yōu)性條件）設(shè)f（X的二階連續(xù)可微白凸函數(shù)，且 Vf（X*）=0,則X*為全局極小點(diǎn)。2、算法結(jié)構(gòu)根據(jù)最優(yōu)條件，從理論上講，可以先解非線性方程組Vf（X）=0,然后

13、再判定其解的二階導(dǎo)數(shù)矩陣V2f（X足否正定，即可求出函數(shù)的最優(yōu)解。但由于解非 線性方程組和判定矩陣是否正定是極為復(fù)雜和困難的，其難度甚至已超過(guò)優(yōu)化問(wèn)題本身。因此，上述想法在實(shí)際上是不可行的。最優(yōu)化中大多采用逐步下降算法，其基本思想是：根據(jù)當(dāng)前解選擇一個(gè)適當(dāng) 的下降方向，沿此方向下降到一個(gè)合適位置從而得到新解，然后判斷新解是否為 最優(yōu)解；若是，則停止，否則重復(fù)上述過(guò)程。經(jīng)過(guò)有限次迭代后，在一定條件下 即可得出近似最優(yōu)解。下降算法的迭代格式為：X“=Xk+tkPk,其中Xk是第k次迭代點(diǎn)，Pk是 第k次迭代方向，tk （tk之0）是第k次迭代步長(zhǎng)。顯然，用迭代法求解無(wú)約束最優(yōu)化問(wèn)題的關(guān)鍵是：構(gòu)造迭

14、代方向Pk和確定迭代步長(zhǎng)tk。確定迭代步長(zhǎng)tk可通過(guò)一維搜索方法進(jìn)行，而選擇不同的方法構(gòu)造 迭代方向Pk,將會(huì)得到不同的算法。根據(jù)一階Taylor展式f Xk 1 = f Xk tkPk = f Xk tU Tf Xk Pk o（tk）f Xk tkPk - f Xk = tTf Xk Pk T tk . tk可見(jiàn)，如果VTf (Xk )Pk 0,使得當(dāng)0tk t時(shí)上式右端小于零, 從而f (Xk +tkPk ) f(Xk ),即Pk為下降方向的條件是其與梯度方向成鈍角。3、收斂性與收斂速度一個(gè)算法是否收斂，往往同初始點(diǎn) xo的選取有關(guān)。如果只有當(dāng)xo充分接近 最優(yōu)解x*時(shí)，由算法產(chǎn)生的點(diǎn)列才

15、收斂于 x*,則該算法稱為具有局部收斂性的 算法。如果對(duì)于任意的初始點(diǎn) xo ,由算法產(chǎn)生的點(diǎn)列都收斂于最優(yōu)解 x ,則這 個(gè)算法稱為具有全局收斂性的算法。由于一般情況下最優(yōu)解x是未知的，所以嚴(yán)格來(lái)說(shuō)只有具有全局收斂性的算法才是有實(shí)用意義的。令人遺憾的是大多數(shù)經(jīng) 典優(yōu)化算法都是局部?jī)?yōu)化算法，全局優(yōu)化的理論和算法遠(yuǎn)不及局部?jī)?yōu)化那么成 熟，至今為止還沒(méi)有得到類似于局部極小點(diǎn)那樣的解析條件，即沒(méi)有肯定的方法能判斷一個(gè)局部極小點(diǎn)是否為全局極小點(diǎn)，現(xiàn)有的一些全局優(yōu)化算法也只能在一 定程度上避免迭代終止于一個(gè)非全局的局部極小點(diǎn)。定義9.5設(shè)點(diǎn)列xj收斂于x* ,且對(duì)實(shí)數(shù)P* ,有l(wèi)im卜L , xkx*P

16、0 P(c),則得到a,b，否則a=c,c = b,轉(zhuǎn)。2、直接法的基本原理假設(shè)f(x)為單峰函數(shù)，即f(x)有唯一的極小點(diǎn)x*,且搜索區(qū)間b,b】已知。因?yàn)閒在*)內(nèi)單減，在(x*,b)內(nèi)單增，故若在b,b內(nèi)任取二點(diǎn)5 P ,則僅有如下兩種情形:f。) 2)這就是著名的Fibonacci序列。綜上所述，計(jì)算n個(gè)函數(shù)值可獲得的區(qū)間最大縮短率為i/Fn。對(duì)于問(wèn)題2,既然n個(gè)試點(diǎn)的最大縮短率為i/Fn ,要想把匕,bl的長(zhǎng)度縮短為 原來(lái)的名倍，名稱為縮短的相對(duì)精度，只要試點(diǎn)數(shù)n滿足i/Fn Me即可，試點(diǎn)的具 體位置可以根據(jù)每次的縮短率確定。3、Fibonacci法和 0.618 法若按上述方法選

17、取試點(diǎn)，則對(duì)當(dāng)前搜索區(qū)間ak,bk,& = bk - Fk./ Fk (bk -ak ), B =ak + Fk/Fk(bk - ak )若在搜索區(qū)間內(nèi)取n個(gè)點(diǎn)，則各次縮短率分別為Fn/Fn，F(xiàn)njFn,，E開(kāi)2, 其中Fn為Fibonacci序列。這種方法稱為 Fibonacci法。從理論上講，F(xiàn)ibonacci法是縮短搜索區(qū)間的最優(yōu)方法，但實(shí)際計(jì)算時(shí)要用 到Fibonacci數(shù)列，而且每次縮短率不同，這就增加了計(jì)算上的困難。為了計(jì)算 上的方便，通常采用等速縮短的方法?？s短率取為Fn jFn的極限丁 =0.618,此方法稱為0.618法。若當(dāng)前搜索區(qū)間為&k,bk，則口5Mbk-ak), a

18、 =ak +Mbk ak )。顯然，取N個(gè)點(diǎn)后，縮短率為tn，,若要求相對(duì)精度為則N = In Win .+1。0.618法的計(jì)算步驟如下：求f(x)在區(qū)間la,b】上的最小值，相對(duì)精度為 名。給定 匕記工=0.618, N = ln/lnE】+1, k = 0, ak = a, bk = b ；u=bki(bk ak) f1=f(ot), P=ak*Ybkak) 2 = (3),若32,轉(zhuǎn)， 否則轉(zhuǎn)；ak+ =ak，bi =邑 P =, f2 = f1，a =bk書(shū)Mbk書(shū) ak由)3 = f 3),轉(zhuǎn)；ak+=a, bkt=bk,a=B, f1 = f2, P=ak 書(shū)+ ”bk 書(shū)ak

19、書(shū))f2 = f(0),轉(zhuǎn)； 若kN ,置卜=卜+1,轉(zhuǎn)，否則轉(zhuǎn)；取取優(yōu)點(diǎn)x =(ak +bk 丫2 ,取優(yōu)值為f(x )。注：Fibonacci法和0.618法僅適用于單峰函數(shù)；若初始搜索區(qū)間kb】未知,要用進(jìn)退算法先確定。例9.2用0.618法求單峰函數(shù)f (x) =x2 sinx在區(qū)間b,1】?jī)?nèi)的極小值。9.2.2插值法多項(xiàng)式是逼近函數(shù)的一種常用工具。在搜索區(qū)間上，我們可以利用在若干點(diǎn) 處的函數(shù)值來(lái)構(gòu)成低次插值多項(xiàng)式， 用它作為函數(shù)的近似表達(dá)式，并用這個(gè)多項(xiàng) 式的極小點(diǎn)作為原函數(shù)極小點(diǎn)的近似，而低次多項(xiàng)式的極小點(diǎn)是比較容易計(jì)算 的。常用的插值多項(xiàng)式為二次或三次，一般說(shuō)來(lái)三次插值公式的收斂

20、性較好， 但 在導(dǎo)數(shù)不便計(jì)算時(shí)，二次插值多項(xiàng)式也是常用的一種方法。1、二次插值方法設(shè)函數(shù)f (x)在點(diǎn)Xi X2 X3處的值分別為fl, f2, f3 ,利用這三點(diǎn)作二次插 值公式p(x) =a0+ax+a2x2,很容易得到它的極小點(diǎn)為1 x2 - x2 fi x32 -x2 f2 x； -xf f3 x 二-2 x2 -x3 f1 -，x3 _x f2 _ X -x2 f3若xi,x2,x3三點(diǎn)等距，相鄰兩點(diǎn)距離為 Ax,則fl - f3 xx = x22 fi - 2 f2 f32、三次插值方法在二次插值方法中，極小點(diǎn)x*不一定在區(qū)間(xi,x3 )中，即插值可能為外插， 這就使得二次插值

21、方法的誤差可能較大，不易控制。因?yàn)橐话闱闆r下f (x)在搜索區(qū)間Nb】上滿足f (a) 0, f (b) a 0 ,所以若利 用f(x)在a,b兩點(diǎn)的函數(shù)值f(a), f(b)以及一階導(dǎo)數(shù)數(shù)f(a), f(b)作三次插值多 項(xiàng)式，則插值法為內(nèi)插，精度較高。經(jīng)過(guò)計(jì)算，可得三次插值多項(xiàng)式的極小點(diǎn)為u -v - f 八 (b a)f (b) - f (a) 2uu = v2 - f (a) f (b)v = w - f (a) - f (b)w=3f(b)a) b - a9.3共軻梯度法最速下降法Cauchy于1947年提出的最速下降法是求無(wú)約束極值最早的數(shù)值方法， 其基 本思想是：從迭代點(diǎn)出發(fā)，沿

22、目標(biāo)函數(shù)值的負(fù)梯度方向進(jìn)行一維搜索，求出新的迭代點(diǎn)，直到找到局部極小點(diǎn)或滿足精度要求。 1、最速下降法的計(jì)算步驟給定初始點(diǎn)Xo、控制誤差& ,置k = 0 ;計(jì)算梯度Vf (Xk),若Wf(Xk)| 0,從而兒j = 0 ,即P0, Pi,，Pk線性無(wú)關(guān)。2、n元正定二次函數(shù)的共腕梯度法對(duì)n元的正定二次函數(shù)有下面兩個(gè)重要定理。定理9.8對(duì)n元正定二次函數(shù)f (X) =1xtAX +bTX +c ,2設(shè)P01Pi,，Pk(k En)關(guān)于A兩兩共腕。從任意初始點(diǎn)X。出發(fā)，依次沿方向P0, Pi,，Pk二執(zhí)行一維搜索到XkX0P0 XiPl X2Xk-Pk, Xk012 k Ik則Vf(Xk)垂直于

23、前面所有的搜索方向，即p： Vf(Xk)=0(j =0,1，k-1)。12 證：由 Xk = Xk4+7.kPkJ. = Xk _2 +，-k _2 Pk /+2-kJ.PkJ.-= X j .1，1 j 1 Pj 1- k N Pk N kPk(j = 0 1，k - 0得、f(Xk) =AXk b =AX1 jiAPj.1一 k/PkN ，kAPkb二, f (X j 1 ) , 1 j .1Ap j 1 :1 kN APkN kAPk_1用P；左乘上式，根據(jù)定理2.1, p； 9f(Xj書(shū))=0,再由本定理?xiàng)l件P： APj 4=p： APj *=. = P；APk,=0,故 P； W(X

24、k)=0(j = 0,1，k1)。定理9.9對(duì)n元正定二次函數(shù)1;f (X) = X；AX +b；X +c ,2設(shè)P0, P1,，Pn關(guān)于A兩兩共腕。從任意初始點(diǎn)X。出發(fā)，依次沿P0, P1,，Pn執(zhí) 行一維搜索到Xn,則Xn即為極小點(diǎn)。證:由定理9.7, P0R,，Pn線性無(wú)關(guān)，即P0，P1,，Pn可作為Rn的一組基， 由定理 9.8, P； 9f(Xn)=0(j =0,1，n-1),從而 Wf(Xn)=0。又A正定，f(X)為凸函數(shù)，由定理9.5, Xn為惟一全局極小點(diǎn)。仿照P0與P1的關(guān)系，我們構(gòu)造下列搜索方向P0 = -*(X 0 )。Pk = -f(Xk 計(jì)akPk(k =1,2,，

25、n1)_P；aAVf(Xk)ak -“PkAPk工據(jù)此可證明下列定理。定理9.10對(duì)n元正定二次函數(shù)f(x)=1/2X；AX +b；X +c ,從任意初始點(diǎn)X0出發(fā)，依次按上述搜索方向經(jīng)n次迭代下降至Xn,即X0 PT X1 -PT X2Xn-PnT Xn則Xn即為極小點(diǎn)。證：只須用歸納法證明上述P0, P1，Pg關(guān)于A兩兩共腕，再利用定理2.4即可 證明本定理。如果一個(gè)算法能用有限步求出二次函數(shù)的極小點(diǎn)(從理論上說(shuō))，則稱這個(gè)算法具有二階收斂性或有限步收斂性。3、一般函數(shù)的共腕梯度法對(duì)于一般函數(shù)，已無(wú)正定矩陣A和共腕的概念，因此我們必須尋求一種與上述共腕方向表達(dá)式等價(jià)的形式，其中不含有矩陣A

26、 0131由 Xk=Xk*tkPk，行 Apj = A - (X k X k_i ) tk J1，1 I=kAXk +b) (AXkb )=Bf(Xk )-Vf(XkL N，tk J.tk 1從而akf Xk kf Xk Jf Xkp：kf Xk Jf XkJ又 f Xk=akPk_2- Pk J,Pk1-f X k = Pk_2、f X k = Pk_2 f Xk_1=0故Lf Xkf Xk Jf XkI - Xk 2 JTf Xk Xk|f Xk 2Tf Xk)akPk _2 - Pk f Xk 2Pk 1 f f X k -、f X k Jk-Pk J f X k J=一一 5 f X

27、k, akPk _2,f X k 1 f X k最終ak“Xk 22 f Xk.綜上所述，對(duì)于一般目標(biāo)函數(shù)，可按下述規(guī)則確定搜索方向:Po = - f XoPk -f XkakPka J Xk 2k y Xk2此方法稱為F-R (Fletcher-Reeves共腕梯度法9.4擬牛頓法牛頓法最速下降法的本質(zhì)是用線性函數(shù)逼近目標(biāo)函數(shù)。因此，要想得到快速算法, 需要考慮用高次函數(shù)逼近。若采用二次多項(xiàng)式逼近，則稱為牛頓法。對(duì)給定點(diǎn)Xk,在這個(gè)點(diǎn)附近將f(X)展為二階Taylor展式，即14-T-1 T 2 -f(X) f(Xk) f(Xk).：XXT 2f(Xk) X2T2I 己 gk = f (Xk

28、), Gk = f(Xk),則Tf (X)定 f (Xk)+ gkH +AX TGkAX =勺(X),如果Gk正定，則中(X)為凸函數(shù)，乎(X)有惟一極小點(diǎn)，滿足勺(X)=0, 即 gk *Gk(X Xk) 0, X = Xk -Ggk。若記Pk =_Ggk, Xk+ = Xk -Ggk,則X=Xk + Pk,稱之為牛頓迭代，Pk稱為牛頓方向。牛頓迭代可以理解為從Xk出發(fā)，沿牛頓方向Pk取步長(zhǎng)兒=1。顯然，對(duì)正 定二次函數(shù)，從任意初始點(diǎn)出發(fā)，牛頓迭代一步即可達(dá)到最小點(diǎn)。理論分析表明，當(dāng)初始點(diǎn)X。離X較近時(shí)，牛頓迭代法能以二階速度收斂到 X*。但當(dāng)X。離X*較遠(yuǎn)時(shí)，牛頓迭代可能不收斂，甚至迭代過(guò)

29、程無(wú)法進(jìn)行，原 因如下：當(dāng)Gk為奇異陣時(shí)，G無(wú)意義，迭代無(wú)法進(jìn)行；即使Gk非奇異，但G不一定正定，從而不能保證gTPk =-gTGjgk 0,即 牛頓方向Pk不一定是下降方向；即使Gk正定，止匕時(shí)Pk =-Ggk是下降方向，但牛頓迭代取步長(zhǎng) 除=1 ,也不 能保證 f (Xk + Pk ) f (Xk )。其實(shí)，即便牛頓迭代可以正常進(jìn)行且收斂，因?yàn)樗诿看蔚鷷r(shí)要計(jì)算 Hesse 矩陣及其逆，從而得出迭代方向 Pk ,這使得每次迭代的計(jì)算量太大，大大降低 了牛頓迭代的實(shí)用性。9.4.2變尺度法(擬牛頓法)牛頓法主要缺點(diǎn)是要計(jì)算Hesse矩陣及其逆。一個(gè)很自然的想法是不直接計(jì) 算Hesse矩陣G

30、k,也不計(jì)算其逆矩陣G，而設(shè)法構(gòu)造另一個(gè)矩陣來(lái)直接逼近 GJ,這一類算法稱為變尺度法或擬牛頓法， 其中以DFP算法和BFGS算法最為 著名。在所有無(wú)約束最優(yōu)化方法中，若綜合考察收斂速度、計(jì)算量、適用范圍等 算法性能，變尺度法是最出色的。變尺度法的基本思想是在 Xk書(shū)處，按某種規(guī)則產(chǎn)生一個(gè)對(duì)稱正定矩陣 Hi, 用Pk+=-Hk+gk書(shū)作為Xk書(shū)處的搜索方向。顯然，取Hk由= i,gM時(shí)，分別為最 速下降方向和牛頓方向。1、擬Newton條件15由 Taylor展式 gk =gk用 +Gk+(Xk Xk+) + o(Xk Xk.),行 g k gk + +Gk/Xk XkG , gk 4gk Gk

31、JXk .Xk ) 記 Ag k = gk41 _gk, &X k=Xk 中一 Xk,則 AX k G Gkj4gk 0對(duì)于二次函數(shù)，上式精確成立，我們稱 AXk =Gk*Agk為擬Newton條件。Hk.作為Gk；的近似自然應(yīng)該滿足AXk=Hk+Agk。2、DFP變尺度法我們的目標(biāo)是在Xk書(shū)處構(gòu)造滿足擬Newton條件的對(duì)稱正定陣Hk卡,為此假 設(shè)H k已知(Ho可取為任一對(duì)稱正定陣，比如 Ho=I),且Hk卡-Hk=AH-因AH k對(duì)稱，故可令A(yù)Hk十VkVT ,其中Uk,Vk待定。將其代入擬牛頓條件得(Hk +口/： +vM)Agk =AXk ,即(u：%k Uk +”：卜 Vk = A

32、X k H *gk。 為使上式成立，只要選擇uk,vk使得*：聞 Uk = AXkJvTAgk Vk = -Hkigk從(uTAgk Uk =AXk 知，Uk與 AXk共線，故可令 Uk = aAXk ,代入(uTAgk Uk =AXk二一，從而UkUTX k 和二Xk :XkTXk gk類似地可得VkVTHk kgk THkq THk gk最終得到Hk+=Hk +兇畢上-HkAgkTAgk THk ,稱之為DFP公式。Xk 二gk二gk h k kDFP算法計(jì)算步驟：給定初始點(diǎn)X0 ,精度以取H0=I, i=0;計(jì)算梯度gk=Vf(Xk),若|g/ 0o 證：因?yàn)間k#0, Pk = -hk

33、gk是下降方向，故從Xk到Xk+ = Xk + tkPk的迭代步 長(zhǎng)tk a。，并且 pTgk+ =0。16- - X k9 k = X k 1 - Xk (9k 1 _9k) =tkPk(gk.1 -gk)二-tk pk gk -tkgk Hkgk 0(Wk T Hk%k =(gk+ -9k)THk(gk+ -9k)= 9kTHkgk+ +9kTHkgk -29k44THk9k = 9k 書(shū)T Hk9k 書(shū) + gJ H k9k 0定理9.12:如果Ho對(duì)稱正定，則由DFP公式產(chǎn)生的Hk均對(duì)稱正定3、BFGS變尺度法DFP變尺度法是一種非常有效的無(wú)約束最優(yōu)化方法， 自從1959年發(fā)表以來(lái)，

34、大量的計(jì)算實(shí)踐確實(shí)反映了這一點(diǎn)。但到了六十年代后期，一方面從計(jì)算實(shí)踐中 發(fā)現(xiàn)了 DFP算法在數(shù)值穩(wěn)定性方面存在一定的問(wèn)題，同時(shí)在變尺度法理論的研 究上也獲得了顯著的進(jìn)展，陸續(xù)提出了許多變尺度算法。在七十年代初期，從數(shù)量繁多的算法中，人們發(fā)現(xiàn)一個(gè)比DFP算法具有更好數(shù)值穩(wěn)定性的算法，即BFGS算法。與DFP公式的推導(dǎo)過(guò)程類似，可以得到滿足擬牛頓條件的一組 Hk書(shū) Xk Xk T Hk 9k 9k THk H k 1 = H kT_TXk ：9k：9k H k 9kXk ：Xk T - ；：Xk T；：9kHk+ 9 9外)H k &g kT/Xk )%k TOC o 1-5 h z T(&X k

35、 ) 9 kTHkA9k(&Xk ) +-9k Hk%k(%k ) Hk(應(yīng)”也卜-參數(shù)p取不同的值就得到不同的公式。例如，0 =0就得到了 DFP公式，而若取P =1/gXk T%k ,則相應(yīng)的公式就稱為 BFGS公式。BFGS公式也可記為I,右29)1 X 女式陶“ AXkSXkf(X J%I H H k I TT一SxJ% TBFGS公式可以看做DFP公式的改進(jìn)，一般來(lái)說(shuō)，BFGS公式比DFP公式 有更好的數(shù)值穩(wěn)定性。在用Matlab優(yōu)化工具箱時(shí)，要根據(jù)具體問(wèn)題的特點(diǎn)選擇不同的優(yōu)化算法、 優(yōu)化參數(shù)和一維搜索方法。Matlab提供最速下降法、DFP算法、BFGS算法等, 但缺省設(shè)置為BFG

36、S算法。Matlab中的一維搜索采用二次或三次插值。179.5 Powell方向加速法前面介紹的共腕梯度法、牛頓法、變尺度法都需要計(jì)算目標(biāo)函數(shù)的梯度，這 類方法統(tǒng)稱為解析法。在實(shí)際中有許多問(wèn)題的目標(biāo)函數(shù)解析表達(dá)式很復(fù)雜甚至根 本沒(méi)有解析表達(dá)式，計(jì)算其導(dǎo)數(shù)是非常困難的，此時(shí)解析方法是不適用的。為此, 人們提出了一類不需要計(jì)算梯度，僅根據(jù)目標(biāo)函數(shù)值來(lái)尋找最優(yōu)點(diǎn)的方法， 稱之 為直接法。常用的直接法有步長(zhǎng)加速法、旋轉(zhuǎn)方向法、方向加速法等。一般來(lái)說(shuō)，直接 法不像解析法那樣有一套完整、嚴(yán)密的理論體系，它的搜索策略較為模糊。方向加速法中的鮑威爾(Powell)方向加速法有較嚴(yán)密的理論，其搜索效率高于其它 直接法。Powell法先對(duì)正定二次函數(shù)提出一套計(jì)算方案，使得經(jīng)過(guò)若干次一維搜索 后，算法自動(dòng)產(chǎn)生一組共腕方向。然后，將這套方案推廣到一般目標(biāo)函數(shù)。下面先介紹與Powell法相關(guān)的定義和定理。定義9.7將n維空間Rn的一個(gè)子空間V平移到某一點(diǎn)u產(chǎn)生的集合 M = + + xxwV )稱為一個(gè)仿射集。定理9.13對(duì)n維正定二次函數(shù)f(X) =1XTAX +bTX + c ,若di,d2,，dm關(guān)于A 2兩兩共腕，則從任意初始點(diǎn) X。出發(fā)，依次沿d1,d2,，dm執(zhí)行一維搜索到Xm,一 一 2T，一，一則Xm是f (X)在仿射集M =X0 +九jdj九j R K上的極小點(diǎn)。J證：由