约束变尺度法

最优化理论与方法1约束变尺度法Newton法最突出的优点是收敛速度快，在这一点上其它算法无法比拟的。因此，建议凡是Hesse矩阵比较容易求出的问题，尽可能使用Newton法求解。但是，Newton法也有一个严重缺陷，就是每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了Newton法的优点。为此，人们开始寻找一种算法既可以保持Newton法收敛速度快的优点，又可以摆脱关于Hesse矩阵的计算，这就是变尺度算法。变尺度法是一种非常好的方法，其中DFP算法和BFGS算法。可以说，直到目前为止，在不用Hesse矩阵的方法中是最好的算法。一、拟Newton法为了吸收Newton法收敛速度快的优点，同时避免Newton法每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵，人们提出了具有超线性收敛的拟Newton法。（一）拟Newton法的基本原理在Newton法中的基本迭代公式kkkkPtXX1，其中1kt，)()]([12kkkXfXfP令)()(2kkkkXfgXfG，最优化理论与方法2于是有，，，，21011kgGXXkkkk其中X0是初始点,gk和Gk分别是目标函数f(X)在点Xk的梯度和Hesse矩阵.为了消除这个迭代公式中的Hesse逆矩阵G-1k,可用某种近似矩阵Hk=Hk(Xk)来替换它,即构造一矩阵序列{Hk}去逼近Hesse逆矩阵序列{G-1k}，此时kkkkgHXX1事实上,式中Pk=-Hkgk无非是确定了第k次迭代的搜索方向.为了取得更大的灵活性,考虑更一般的迭代公式kkkkkgHtXX1其中步长tk通过从Xk出发沿Pk=-Hkgk作直线搜索来确定.此式代表很广的一类迭代公式.例如,当Hk=I(单位矩阵)时,它变为最速下降法的迭代公式。附加条件为了使Hk确实与G-1k近似并有容易计算的特点,必须对Hk附加某些条件:⑴为保证迭代公式具有下降性质,要求{Hk}中的每一个矩阵都是对称正定的.因为使搜索方向Pk=-Hkgk是下降方向,只要0kkTkkTkgHgPg⑵求Hk之间的迭代具有简单形式.可设为最简单的形式:kkkEHH1最优化理论与方法3其中Ek称为校正矩阵,此式称为校正公式.⑶{Hk}必须满足拟Newton条件.（二）拟Newton法的算法构造已知目标函数f(X)及其梯度g(X),终止限。Step1选定初始点X0;计算f0=f(X0),g0=g(X0),选定初始矩阵H0,要求H0对称正定(例如,H0=I)，置k=0.Step2计算搜索方向kkkgHP.Step3作直线搜索),(1kkkPXlsX.计算111111(),(),,kkkkkkkkkkffXggXSXXygg.Step4判别终止准则是否满足.若满足,则Xk+1就是所求的极小点,否则转Step5.Step5计算kkkEHH1.Step6k=k+1,转Step2.其中校正矩阵Ek可由确定的公式来计算.不同的公式对应不同的拟Newton算法.（三）拟Newton算法的流程图最优化理论与方法4kk==kk+1+1ff00==ff((XX00),),gg00==gg((XX00))开始结束选定XX00,对称正定阵HH00,置k=0Xk+1YH准则满足NkkkgHP),(1kkkPXlsX111111(),(),,kkkkkkkkkkffXggXSXXyggkkkEHH1二、DFP变尺度法DFP算法首先由Davidon1959年提出,1963年,Fletcher和Powell作了改进,形成DFP算法.D,F,P是这三位学者名字的字头.这种算法是无约束最优化方法最有效的方法之一.（一）DFP算法的基本原理考虑校正公式:TkkkTkkkkkVVUUHH1其中Uk,Vk是待定n维向量,αk,βk是待定常数.这时,校正矩阵是TkkkTkkkkVVUUE根据拟Newton条件kkkkTkkkTkkkyHSyVVUU)(最优化理论与方法5或kkkkTkkkkTkkkyHSyVVyUU满足这个方程的Uk,Vk有无穷多种取法,其中的一种:TkkkkkUUyS，TkkkkkkVVyHy注意到kTkyU和kTkyV都是数量,kkkkkUSVHy，不妨取，可取1/),1/()TTkkkkkkkSyyHy(得kkTkkTkkkkTkTkkkkyHyHyyHySSSHH1这就是DFP校正公式（二）DFP算法的算法构造已知目标函数f(X)及其梯度g(X),问题的维数n,终止限εStep1选定初始点.计算0000(),()ffXggXStep2置000,,0HIPgk.Step3作直线搜索),(1kkkPXlsX1111()()kkkkffXggX，计算Step4判别终止准则满足否.Step5若k=n,则置010101kkkXXffgg，，Step6计算1kkkSXX,1kkkygg1TTkkkkkkkkTTkkkkkSSHyyHHHSyyHy,111kkkPHg置k=k+1,转Step3.最优化理论与方法6（三）DFP算法的流程图kk==kk+1+1置HH00=I,k=0,PP00=-=-gg00开始选定XX00,ff00==ff((XX00),),gg00==gg((XX00))Xk+1YH准则满足N),(1kkkPXlsX1111(),()kkkkffXggX11,kkkkkkSXXygg1TTkkkkkkkkTTkkkkkSSHyyHHHSyyHy111kkkPHgk=nN结束令X0=Xn+10101kkffgg，Y三、BFGS变尺度法另一个有效和著名的变尺度算法是Broyden,Fletcher(1970),Goldfarb(1969)和Shanno(1970)共同研究的结果,因而叫做BFGS法.（一）BFGS算法的基本原理考虑校正公式TkkkkTkkTkkkTkkTkkkkTkTkkkkWWyHySyyHyHyyHSySSHH))((1其中,最优化理论与方法7kkTkkkkTkkkyHyyHSySW校正矩阵为TkkkkTkkTkkkTkkTkkkkTkTkkkWWyHySyyHyHyyHSySSE))((β为实数参数,每取一个实数就对应一种拟Newton算法.当取β=0时就是DFP校正公式令1/()TkkSy得著名的DFGS校正公式kTkkTkkkTkkkTkkkTkkTkkkHySSyHSSySyHyySHH111（二）DFGS算法迭代步骤已知目标函数f(X)及其梯度g(X),问题的维数n,终止限ε.Step1选取初始点X0,初始矩阵H0=I,给定终止限ε0.Step2求初始梯度若≤ε,停止输出X0;否则.Step3构造初始BFGS方向,取0000()(),0PHfXfXk.Step4进行一维搜索,求tk,使得11(,),kkkkkkkXlsXPXXtP.Step5求梯度若≤ε,停止输出Xk+1;否则.Step6检验迭代次数,若k+1=n,令X0=Xn转(3);否则.Step7构造BFGS方向,用BFGS公式kTkkTkkkTkkkTkkkTkkTkkkHySSyHSSySyHyySHH111最优化理论与方法8计算,取,令1111,(),1kkkkHPHfXkk转Step4.（三）DFGS算法的流程图结束开始计算f(X0)给定X0,H0=I,ε0计算f(Xk+1)Xk+1取0000()(),0PHfXfXk求tk使),(1kkkPXlsX)(111kkkXfHP1kk||f(X0)||≤εN||f(Xk+1)||≤εNk+1=nNX0YY令X0=XnY四、变尺度法的算法分析Newton法每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了Newton法收敛速度快的优点。而变尺度算法则可以保持Newton法收敛速度快的优点，又可以摆脱关于Hesse矩阵的计算。变尺度法中的二个重要算法DFP算法和BFGS算法迭代过程相同,区别仅在于校正矩阵Ek选取不同,对于DFP法,由于一维搜索的不精确和计算误差的最优化理论与方法9积累可能导致某一轮的Hk奇异,而BFGS法对一维搜索的精度要求不高,并且由它产生的Hk不易变为奇异矩阵.BFGS法比DFP法更具有好的数值稳定性,它比DFP法更具有实用性.