約束變尺度法Newton法最突出的優(yōu)點(diǎn)是收斂速度快，在這一點(diǎn)上其它算法無(wú)法比擬的。因此，建議凡是Hesse矩陣比較容易求出的問(wèn)題，盡可能使用Newton法求解。但是，Newton法也有一個(gè)嚴(yán)重缺陷，就是每次迭代都要計(jì)算目標(biāo)函數(shù)的Hesse矩陣和它的逆矩陣，當(dāng)問(wèn)題的維數(shù)較大時(shí)，計(jì)算量迅速增加，從而就抵消了Newton法的優(yōu)點(diǎn)。為此，人們開(kāi)始尋找一種算法既可以保持Newton法收斂速度快的優(yōu)點(diǎn)，又可以擺脫關(guān)于Hesse矩陣的計(jì)算，這就是變尺度算法。變尺度法是一種非常好的方法，其中DFP算法和BFGS算法?？梢哉f(shuō)，直到目前為止，在不用Hesse矩陣的方法中是最好的算法。一、擬Newton法為了吸收Newton法收斂速度快的優(yōu)點(diǎn)，同時(shí)避免Newton法每次迭代都要計(jì)算目標(biāo)函數(shù)的Hesse矩陣和它的逆矩陣，人們提出了具有超線性收斂的擬Newton法。擬Newton法的基本原理在Newton法中的基本迭代公式Xk廠XktkPk其中tk-1Pk...P2f(Xk)］八f(Xk)令Gk八2f(xq，gk八f(Xk)于是有1X"i=Xk—Gk_gk，k=0,1,2,...其中X0是初始點(diǎn)，gk和Gk分別是目標(biāo)函數(shù)f(X)在點(diǎn)Xk的梯度和Hesse矩陣.為了消除這個(gè)迭代公式中的Hesse逆矩陣G-1k，可用某種近似矩陣Hk=Hk(Xk)來(lái)替換它，即構(gòu)造一矩陣序列｛Hk｝去逼近Hesse逆矩陣序列｛G-1k｝，此時(shí)Xk1%-Hkgk事實(shí)上，式中Pk=-Hkgk無(wú)非是確定了第k次迭代的搜索方向.為了取得更大的靈活性，考慮更一般的迭代公式XkAA~XA_tkHkgk其中步長(zhǎng)tk通過(guò)從Xk出發(fā)沿Pk=-Hkgk作直線搜索來(lái)確定?此式代表很廣的一類迭代公式?例如，當(dāng)Hk=l(單位矩陣)時(shí)，它變?yōu)樽钏傧陆捣ǖ牡?。附加條件為了使Hk確實(shí)與G-1k近似并有容易計(jì)算的特點(diǎn),必須對(duì)Hk附加某些條件：⑴)為保證迭代公式具有下降性質(zhì)，要求｛Hk｝中的每一個(gè)矩陣都是對(duì)稱正定的.因?yàn)槭顾阉鞣较騊k=-Hkgk是下降方向，只要g!pk—^lHkgk::0(2))求Hk之間的迭代具有簡(jiǎn)單形式.可設(shè)為最簡(jiǎn)單的形式：Hki二HkEk其中Ek稱為校正矩陣，此式稱為校正公式.⑶{Hk}必須滿足擬Newton條件.擬Newton法的算法構(gòu)造已知目標(biāo)函數(shù)f(X)及其梯度g(X),終止限Step1選定初始點(diǎn)X0;計(jì)算f0=f(X0),g0=g(X0),選定初始矩陣H0,要求H0對(duì)稱正定(例如情H0=l)，置k=0.Step2計(jì)算搜索方向PkHkgk-Step3作直線搜索Xk1lS(Xk,Pk).計(jì)算f(XkQg(x),S=XX,ygI昇'k*=f'”k41=g'kdl"k*—k'"k=k*=gkStep4判別終止準(zhǔn)則是否滿足.若滿足，則Xk+1就是所求的極小點(diǎn)，否則轉(zhuǎn)Step5.Step5計(jì)算Hk出二Hk+Ek.Step6k=k+1,轉(zhuǎn)Step2.其中校正矩陣Ek可由確定的公式來(lái)計(jì)算.不同的公式對(duì)應(yīng)不同的擬Newton算法.擬Newton算法的流程圖CSB選定，對(duì)稱正定陣，置k=0i7fo=（X））g=i（X））|Um,X：=ls（X,Fk）fk*f（人/加乜心爪二心-人，《二^忻（結(jié)束k=k+1二、DFP變尺度法DFP算法首先由Davidon1959年提出，1963年,Fletcher和Powell作了改進(jìn)，形成DFP算法.D,F,P是這三位學(xué)者名字的字頭這種算法是無(wú)約束最優(yōu)化方法最有效的方法之一.（一）DFP算法的基本原理考慮校正公式：Hk1二和：山小MM其中Uk,Vk是待定n維向量，ak,Bk是待定常數(shù).這時(shí)，校正矩陣是Ek「kU山t:NkVj根據(jù)擬Newton條件ckUkUTBVkVkr)yA:kUkUTyk:kVkVkyk=Sk-Hkyk滿足這個(gè)方程的Uk,Vk有無(wú)窮多種取法，其中的一種：二kukukyk=sk1^^kTy'""'kyk注意到UTyk和VJyk都是數(shù)量，不妨取Uk=3,Vk=Hkyk可取「/(S'),-「1/(y：")k廿k廿Hk官thHkykykHkEy』kyk這就是DFP校正公式DFP算法的算法構(gòu)造已知目標(biāo)函數(shù)f(X)及其梯度g(X)，問(wèn)題的維數(shù)n,終止限&Step1選定初始點(diǎn).計(jì)算f°二fWg°=g(X°)Step2置H°",PO_g°,k=0Step3作直線搜索Xk1=ls(Xk，PQ計(jì)算fk1=f(XkJ,gk1=g(Xk1)Step4Step4判別終止準(zhǔn)則滿足否.Step5Step6Step5Step6計(jì)算2=X"—Xkyk=gkA_gk若k=n貝U置X0=Xk+|,f0=fkdt，g0=gH1Hki「HkSHki「HkSTy/yTHk%,R1八h1gk1置k=k+1，轉(zhuǎn)Step3.(三)DFP算法的流程圖開(kāi)始』置H=Lk=0R)=g)三、BFGS變尺度法另一個(gè)有效和著名的變尺度算法是Broyden,Fletcher(1970),Goldfarb(1969)和Shanno(1970)共同研究的結(jié)果，因而叫做BFGSt.(一)BFGS算法的基本原理考慮校正公式Hk廠%琴-吐仇.品)氏心)嘰yJQyAyk其中，校正矩陣為Sk校正矩陣為Wk二Tk

yq

HkYkTkky"(yTSk)(y"kyk)Wk(yTSk)(y"kyk)WkWTykSkykHkykB為實(shí)數(shù)參數(shù),每取一個(gè)實(shí)數(shù)就對(duì)應(yīng)一種擬Newton算法.當(dāng)取B=0時(shí)就是DFP校正公式令：=i/(Skyk)得著名的DFGSS正公式-HkykSk_-HkykSk_skykHkDFGS算法迭代步驟已知目標(biāo)函數(shù)f(X)及其梯度g(X)，問(wèn)題的維數(shù)n,終止限.Step1選取初始點(diǎn)X0,初始矩陣H0=l,給定終止限&>0.Step2||，停止輸出X0;否則.Step3構(gòu)造初始BFGS方向，取Step4進(jìn)行一維搜索，求tk，使得Xk1=lS(Xk,PJXk1=Xk出Step5||&，停止輸出Xk+1;否則.Step6檢驗(yàn)迭代次數(shù)，若k+仁口,令X0=Xn轉(zhuǎn)(3);否則.Step7構(gòu)造BFGS方向，用BFGS公式H"Hk+舄卜舲翻柿kST-SkyT【

計(jì)算，取,令Hk1,R1=-hkJ*i），k=k1轉(zhuǎn)step4（三）DFGS!法的流程圖計(jì)算fX)C結(jié)束勺取(尊)5(人記0|吏fisXoP）^t一+iNn〉沿二一HkdYf(X")k=k+1C結(jié)束〉沿二一HkdYf(X")四、變尺度法的算法分析Newton法每次迭代都要計(jì)算目標(biāo)函數(shù)的Hesse矩陣和它的逆矩陣，當(dāng)問(wèn)題的維數(shù)較大時(shí)，計(jì)算量迅速增加，從而就抵消了Newton法收斂速度快的優(yōu)點(diǎn)。而變尺度算法則可以保持Newton法收斂速度快的優(yōu)點(diǎn)，又可以擺脫關(guān)于Hesse矩陣的計(jì)算。變尺度法中的二個(gè)重