約束變尺度法

最優(yōu)化理論與方法最優(yōu)化理論與方法PAGEPAGE10約束變尺度法Newton法最突出的優(yōu)點是收斂速度快，在這一點上其它算法無法比擬的。因此，建議凡是Hesse矩陣比較容易求出的問題，盡可能使用Newton法求解。但是，Newton法也有一個嚴重缺陷，就是每次迭代都要計算目標函數(shù)的 矩陣和它的逆矩陣，當問題的維數(shù)較大時，計算量迅速增加，從而就抵消了Newton法的優(yōu)點。為此，人們開始尋找一種算法既可以保持Newton法收斂速度快的優(yōu)點，又可以擺脫關(guān)于Hesse矩陣的計算，這就是變尺度算法。DFPBFGSHesse矩陣的方法中是最好的算法。一、擬Newton 法為了吸收Newton法收斂速度快的優(yōu)點，同時避免Newton法每次迭代都要計算目標函數(shù)的Hesse矩陣和它的逆矩陣，人們提出了具有超線性收斂的擬Newton法。(一)擬Newton法的基本原理Newton

Xk

XktkPk其中tk-1Pk…P2f(Xk)］f(Xk)令Gk八2f(Xk)，gk 八f(Xk)于是有X =X—X =X—G k^i k k— k

k=0,1,2,…X0是初始點，gkGkf(X)XkHesse.HesseG-1k可用某種近似矩陣Hk=Hk(Xk)來替換它,即構(gòu)造一矩陣序列｛Hk｝去逼近Hesse逆矩陣序列｛G-1k｝，此時Xk1^Xk-Hkgk事實上，Pk=-Hkgkk次迭代的搜索方向.更大的靈活性，考慮更一般的迭代公式Xk^^~X^_tkHkgktk通過從XkPk=-Hkgk作直線搜索來確定?代公式?例如,Hk=l(單位矩陣)時，它變?yōu)樽钏傧陆捣ǖ牡?。附加條件為了使Hk確實與G-1k近似并有容易計算的特點,必須對Hk附加某些條件：要求｛Hk｝中的每一個矩陣都是對稱正定的Pk=-Hkgk是下降方向只要g!pk—glHkgk::0⑵)求Hk之間的迭代具有簡單形式.可設(shè)為最簡單的形式：Hki二HkEk其中Ek稱為校正矩陣，此式稱為校正公式.⑶｛Hk｝必須滿足擬Newton條件.(二)擬Newton法的算法構(gòu)造已知目標函數(shù)f(X)及其梯度g(X),終止限Step1Step1選定初始點X0;計算f0=f(X0),g0=g(X0),H0,H0對稱正定(例如,H0=l)，置k=0.Step2PkHkkStep2PkHkkg.Step3Xk1lS(Xk,Pk).計算fk*=f(XkQgk41=g kd1(X),S=Xk*—k k= k*=gkX,ygStep4判別終止準則是否滿足.若滿足Xk+1就是所求的極小點,Step5.Step5HkHk+Ek.Step6k=k+1,轉(zhuǎn)Step2.(三)擬Newton算法的流程圖選定，對稱正定陣，置k=0I1 7選定，對稱正定陣，置k=0fo=（x））g=i（x））XkXk^=ls(X,Fk)fk*f(人/加乜心爪二心-人,《=弘=9<kk=k+1

（結(jié)束'二、DFP變尺度法DFP算法首先由Davidon1959年提出，1963年,Fletcher和Powell作了改進，DFP算法.D,F,P有效的方法之一.（一）DFP算法的基本原理考慮校正公式：k1H 二和：山小MMk1其中Uk,Vk是待定n維向量，ak,Bk是待定常數(shù).這時,校正矩陣是Ek「kU山T根據(jù)擬Newton條件

： NkVjckkT■kkr）y^ Hk:kUkUTyk：kV

kV

yk=Sk-Hkyk滿足這個方程的Uk,Vk有無窮多種取法，其中的一種:二kUkUkk=k 1kkkTy^-kk注意到

UTyk和 VJyk都是數(shù)量,不妨取Uk=3,Vk=Hkyk可取「/(S'), -「1/(y：Hkyk)k卄HkTH

HkykykHkSkykykHkyk這就是DFP校正公式DFP算法的算法構(gòu)造f(Xg(Xn,終止限Step1選定初始點.計算ffWg°=g(X)Step2置°",P。…,k=0k k1 kStep3作直線搜索 Xk1=ls(Xk,Pk)計算fk1=f(XJ,k k1 kStep4 判別終止準則滿足否.若k= 貝U置X f ,Step5 n 若k= 貝U置X f ,計算 Step6 2=Xk^— k =gk^計算 H yyHk k k kHk1「HkSTy/yTH k% ,R1八H1gk1置k=k+1,轉(zhuǎn)Step3.(三)DFP算法的流程圖開始』置H=Lk=0R)=g)三、BFGS 變尺度法另一個有效和著名的變尺度算法是Broyden,Goldfarb(1969)Shanno(1970)共同研究的結(jié)果，BFGSt.(一)BFGS算法的基本原理考慮校正公式Hk廠％琴-吐仇.品)氏心)嘰yJQy^yk其中，SSkWkykSkTk校正矩陣為HkykTkky HkykEk_HkHk：(yTSk)(yTHkyk)WkWTykSkykHkykB為實數(shù)參數(shù),每取一個實數(shù)就對應一種擬Newton算法.當取B=0時就是DFP校正公式k :=1/(Sy)DFGSSk *■鑒kT

-Hkyk

Sk_SkHkS(二)DFGS算法迭代步驟已知目標函數(shù)f(X)及其梯度g(X),問題的維數(shù)n,終止限.Step1選取初始點X0,初始矩陣H0=l,給定終止限&>0.Step2 || ，停止輸出X0;否則Step3BFGS方向取Step4進行一維搜索tk,使得Xkk1=ls(XXkk1

,PJFk1=Xk't,PJFStep5 || &,Xk+1;否則Step6檢驗迭代次數(shù)k+n,X0=Xn轉(zhuǎn)(3);否則.Step7構(gòu)造BFGS方向，用BFGS公式H"Hk+為卜舲翻柿kST-SkyT【計算,取,令Hk1