《约束变尺度法》由会员分享，可在线阅读，更多相关《约束变尺度法（12页珍藏版）》请在金锄头文库上搜索。
1、约束变尺度法Newt on法最突出的优点是收敛速度快，在这一点上其它算法无法比拟的。因 此，建议凡是Hesse矩阵比较容易求出的问题，尽可能使用Newton法求解。但 是，Newt on法也有一个严重缺陷，就是每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了 Newton 法的优点。为此，人们开始寻找一种算法既可以保持Newton法收敛速度快的优点， 又可以摆脱关于Hesse矩阵的计算，这就是变尺度算法。变尺度法是一种非常好的方法，其中DFP算法和BFGS算法。可以说，直到目前为 止，在不用Hesse矩阵的方法中是最好的算法。一、拟 New
2、ton法为了吸收Newton法收敛速度快的优点，同时避免Newton法每次迭代都要计算 目标函数的Hesse矩阵和它的逆矩阵，人们提出了具有超线性收敛的拟Newt on 法。(一) 拟Newton法的基本原理在Newton法中的基本迭代公式Xk 厂 Xk tkPk其中tk-1 Pk.P2f(Xk)八 f (Xk)令Gk八2 f ( xq，gk 八 f(Xk)于是有 1Xi=Xk Gk_gk，k =0,1,2,.其中X0是初始点，gk和Gk分别是目标函数f (X )在点Xk的梯度和Hesse矩阵.为了消除这个迭代公式中的Hesse逆矩阵G-1k，可用某种近似矩阵Hk=Hk(Xk)来替换它，即构造
3、一矩阵序列Hk去逼近Hesse逆矩阵序列G-1k，此时Xk1 % -Hkgk事实上，式中Pk= -Hk gk无非是确定了第k次迭代的搜索方向.为了取得更大的灵活性，考虑更一般的迭代公式XkAA XA_tkHkgk其中步长tk通过从Xk出发沿Pk= -Hk gk作直线搜索来确定此式代表很广的一类迭代公式例如，当Hk=l (单位矩阵)时，它变为最速下降法的迭代公式。附加条件为了使Hk确实与G-1k近似并有容易计算的特点,必须对Hk附加某些条件：)为保证迭代公式具有下降性质，要求Hk中的每一个矩阵都是对称正定的.因为使搜索方向Pk= -Hk gk是下降方向，只要g!pk lHkgk : 0(2)求H
4、k之间的迭代具有简单形式.可设为最简单的形式：Hki二 HkEk其中Ek称为校正矩阵，此式称为校正公式.Hk必须满足拟Newton条件.(二) 拟Newton法的算法构造已知目标函数f (X )及其梯度g(X ),终止限Step 1选定初始点X0;计算f0=f(X0),g0=g(X0), 选定初始矩阵H0,要求H0对称正定(例如情H0=l)，置k=0.Step 2计算搜索方向PkHkgk-Step 3 作直线搜索 Xk1 lS(Xk, Pk).计算 f (XkQ g (x ), S = X X , y gI 昇 k* = f ”k41 = g kdlk* k k = k* = gkStep 4
5、判别终止准则是否满足.若满足，则Xk+1就是所求的极小点，否则转Step 5.Step 5 计算 Hk 出二 Hk + Ek.Step 6 k=k+1,转 Step 2 .其中校正矩阵Ek可由确定的公式来计算.不同的公式对应不同的拟Newton算法.(三) 拟Newton算法的流程图CSB选定，对称正定阵，置k=0i7fo=（X） g=i（X）|Um ,X： =ls（X , Fk）fk*f （人/加乜心爪二心-人，二忻（结束k=k+1二、DFP变尺度法DFP算法首先由Davidon 1959年提出，1963年,Fletcher和Powell作了改进，形成DFP算法.D,F,P是这三位学者名字的
6、字头这种算法是无约束最优化方法最 有效的方法之一.（一）DFP算法的基本原理考虑校正公式：Hk 1二和：山小MM其中Uk,Vk是待定n维向量，a k, B k是待定常数.这时，校正矩阵是EkkU 山 t : NkVj根据拟Newton条件 c kUkUT BVkVkr)yA:kU kU T yk : kV kV k yk = Sk - H k y k满足这个方程的Uk,Vk有无穷多种取法，其中的一种：二 ku ku kyk = sk1 kT yk yk注意到UTyk和VJyk都是数量，不妨取 Uk =3,Vk =Hkyk可取/(S),-1 /(y：)k廿Hk官thH kykykH kEykyk
7、这就是DFP校正公式DFP算法的算法构造已知目标函数f (X )及其梯度g(X )，问题的维数n,终止限&Step 1选定初始点.计算f二fWg = g(X )Step 2 置 H ,PO _g,k=0Step 3 作直线搜索 Xk 1 = ls(Xk，PQ计算 fk 1 =f(XkJ,gk 1=g(Xk 1)Step 4判别终止准则满足否.Step 5Step 6计算 2 = X Xkyk =gkA _gk若 k=n 贝 U 置 X0 = Xk+|,f0 = fkdt，g0 = gH1HkiHk STy/ yTHEkHkk % , R 1 八 h 1gk 1 置 k=k+1，转 Step 3
8、.(三)DFP算法的流程图开始置 H=Lk=0R)=g)三、BFGS变尺度法另一个有效和著名的变尺度算法是Broyden, Fletcher(1970),Goldfarb(1969)和 Shanno(1970)共同研究的结果，因而叫做 BFGSt.(一)BFGS算法的基本原理考虑校正公式Hk厂%琴-吐仇.品)氏心)叽yJQ yAyk其中，校正矩阵为SkWk 二 TkyqHkYkT k k y (yTSk)(ykyk)WkWTykSkEk二穿Hk化久Hk.:yk H kykB为实数参数,每取一个实数就对应一种拟Newton算法.当取B =0时就是DFP校正公式令：=i /( Skyk)得著名的D
9、FGSS正公式-H kykSk_ skykH k* 饕 SkST(二) DFGS算法迭代步骤已知目标函数f (X )及其梯度g (X )，问题的维数n,终止限.Step 1选取初始点X0,初始矩阵H0=l,给定终止限& 0.Step 2|，停止输出X0;否则.Step 3构造初始BFGS方向，取Step 4进行一维搜索，求tk，使得Xk 1 = lS(Xk, PJ Xk 1 = Xk出Step 5|&，停止输出Xk+1;否则.Step 6检验迭代次数，若k+仁口,令X0=Xn转(3);否则.Step 7构造BFGS方向，用BFGS公式HHk+舄卜舲翻柿kST-SkyT【计算，取,令Hk 1,
10、R1 = -hk J* i），k = k 1 转 step 4（三）DFGS!法的流程图计算f X)C结束勺取(尊)5 (人记0|吏 fisXoP）t一+iNn 沿二一HkdYf(X)k = k+1四、变尺度法的算法分析Newton法每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵，当问题的 维数较大时，计算量迅速增加，从而就抵消了Newton法收敛速度快的优点。而变尺度算法则可以保持Newton法收敛速度快的优点，又可以摆脱关于Hesse矩阵的计算。变尺度法中的二个重要算法DFP算法和BFGS算法迭代过程相同，区别 仅在于校正矩阵Ek选取不同，对于DFP法，由于一维搜索的不精确和计算误差的积累可能导致某一轮的Hk奇异，而BFGS法对一维搜索的精度要求不高，并且由它 产生的Hk不易变为奇异矩阵.BFGS法比DFP法更具有好的数值稳定性，它比DFP法更具有实用性
