约束变尺度法

约束变尺度法Newton 法最突出的优点是收敛速度快，在这一点上其它算法无法比拟的。

因此，建议凡是Hesse 矩阵比较容易求出的问题，尽可能使用Newton 法求解。

但是，Newton 法也有一个严重缺陷，就是每次迭代都要计算目标函数的Hesse 矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了Newton 法的优点。

为此，人们开始寻找一种算法既可以保持Newton 法收敛速度快的优点，又可以摆脱关于Hesse 矩阵的计算，这就是变尺度算法。

变尺度法是一种非常好的方法，其中DFP 算法和BFGS 算法。

可以说，直到目前为止，在不用Hesse 矩阵的方法中是最好的算法。

一、拟Newton 法为了吸收Newton 法收敛速度快的优点，同时避免Newton 法每次迭代都要计算目标函数的Hesse 矩阵和它的逆矩阵，人们提出了具有超线性收敛的拟Newton 法。

（一）拟Newton 法的基本原理在Newton 法中的基本迭代公式kk k k P t X X +=+1，其中1=k t ，)()]([12kkk Xf Xf P ∇∇-=-令)()(2kkkkXf gXf G∇=∇=，于是有，，，，21011=-=-+k g G X X k k k k其中X0是初始点, gk 和 Gk 分别是目标函数f (X )在点 Xk 的梯度和Hesse 矩阵.为了消除这个迭代公式中的Hesse 逆矩阵G-1k ,可用某种近似矩阵Hk=Hk(Xk)来替换它,即构造一矩阵序列{Hk}去逼近Hesse 逆矩阵序列{G-1k}，此时kk k k g H X X -=+1事实上,式中 Pk= -Hk gk 无非是确定了第k 次迭代的搜索方向.为了取得更大的灵活性,考虑更一般的迭代公式kk k k k g H t X X -=+1其中步长tk 通过从Xk 出发沿Pk= -Hk gk 作直线搜索来确定.此式代表很广的一类迭代公式.例如,当Hk=I (单位矩阵)时,它变为最速下降法的迭代公式。

附加条件为了使Hk 确实与G-1k 近似并有容易计算的特点,必须对 Hk 附加某些条件:⑴ 为保证迭代公式具有下降性质,要求 {Hk} 中的每一个矩阵都是对称正定的.因为使搜索方向Pk= -Hk gk 是下降方向, 只要<-=k k Tk k T k g H g P g⑵ 求Hk 之间的迭代具有简单形式.可设为最简单的形式:kk k E H H +=+1其中 Ek 称为校正矩阵,此式称为校正公式.⑶ {Hk}必须满足拟Newton 条件.（二）拟Newton 法的算法构造已知目标函数f (X )及其梯度 g(X ),终止限ε。

Step 1 选定初始点X0;计算 f0=f(X0),g0=g(X0),选定初始矩阵 H0,要求 H0 对称正定(例如, H0=I)，置k=0. Step 2 计算搜索方向kk k g H P -=.Step 3 作直线搜索),(1k k k P X ls X =+.计算111111(),(),,k k k k k k k k k kf f Xg g X S X X y g g ++++++===-==.Step 4 判别终止准则是否满足.若满足,则Xk+1就是所求的极小点,否则转Step 5.Step 5 计算kk k E H H +=+1.Step 6 k=k+1,转Step 2 .其中校正矩阵Ek 可由确定的公式来计算.不同的公式对应不同的拟Newton 算法.（三）拟Newton 算法的流程图k =k +1f 0=f (X 0),g 0=g (X 0)开始结束选定X 0,对称正定阵H 0,置k=0X k+1YH 准则满足Nkk k g H P -=),(1k k k P X ls X =+111111(),(),,k k k k k k k k k kf f Xg g X S X X y g g ++++++===-==kk k E H H +=+1二、DFP 变尺度法DFP 算法首先由Davidon 1959年提出,1963年, Fletcher 和Powell 作了改进,形成DFP 算法.D,F,P 是这三位学者名字的字头.这种算法是无约束最优化方法最有效的方法之一.（一）DFP 算法的基本原理考虑校正公式:Tk k k Tk k k k k V V U U H H βα++=+1其中Uk,Vk 是待定n 维向量,αk,βk 是待定常数.这时,校正矩阵是Tk k k T k k k k V V U U E βα+=根据拟Newton 条件kk k k T k k k Tk k k y H S y V V U U -=+)(βα或kk k k T k k k k Tk k k y H S y V V y U U -=+βα满足这个方程的Uk,Vk 有无穷多种取法, 其中的一种:T k k k k kU U y S α=，T k k k k k kV V y H y β=-注意到kTk y U 和kT k y V 都是数量,k k k k k U S V H y ==，不妨取 ， 可取 1/),1/()T Tk k k k k k k S y y H y αβ==-(得kk Tk kTk k k k T k T k k kk y H y H y y H y S S S HH-+=+1这就是DFP 校正公式（二）DFP 算法的算法构造已知目标函数f (X )及其梯度 g(X ),问题的维数n,终止限ε Step 1 选定初始点.计算 0000(),()f f Xg g X ==Step 2 置000,,0H I P g k ==-=.Step 3作直线搜索),(1k k k P X ls X =+1111()()k k k k f f X g g X ++++==，计算Step 4 判别终止准则满足否. Step 5 若k=n,则置010101k k k X X f f g g +++===，，Step 6 计算1k k k S X X +=-,1k k ky g g +=-1T Tk k k k k kk k T Tk k k k kS S H y y H H H S y y H y +=+-,111k k k P H g +++=-置k=k+1,转Step 3.（三）DFP 算法的流程图k =k +1置H 0=I ,k=0,P 0=-g 0开始选定X 0, f 0=f (X 0),g 0=g (X 0)X k+1Y H 准则满足N),(1k k k P X ls X =+1111(),()k k k k f f X g g X ++++==11,k k k k k k S X X y g g ++=-==1T T k k k k k kk k T Tk k k k kS S H y y H H H S y y H y +=+-111k k k P H g +++=-k =n N结束令X 0=X n +10101k k f f g g ++==，Y三、BFGS 变尺度法另一个有效和著名的变尺度算法是Broyden, Fletcher(1970), Goldfarb(1969)和Shanno(1970)共同研究的结果,因而叫做BFGS 法.（一）BFGS 算法的基本原理考虑校正公式Tk k k k Tk k T k kk T k k T k k k k T k T k k k k W W y H y S y y H y H y y H S y S S H H ))((1β+-+=+其中,kk Tk kk k T k k k y H y y H S y S W -=校正矩阵为Tk k k k Tk k T k kk T k k Tk k k k T k T k k k W W y H y S y y H y H y y H S y S S E ))((β+-=β为实数参数, 每取一个实数就对应一种拟Newton 算法. 当取β=0时就是DFP 校正公式 令1/()T k k S y β=得著名的DFGS 校正公式⎥⎥⎦⎤⎢⎢⎣⎡--⎪⎪⎭⎫ ⎝⎛++=+k T k k T k k k T kk k Tk kk T k kTk k k H y S S y H S S y S y H y y S H H 111（二）DFGS 算法迭代步骤已知目标函数f (X )及其梯度g (X ),问题的维数n,终止限ε. Step 1 选取初始点X0,初始矩阵 H0=I,给定终止限 ε>0.Step 2 求初始梯度 f (X0).若|| f (X0)||≤ε,停止输出X0;否则. Step 3 构造初始BFGS 方向,取0000()(),0P H f X f X k =-∇=-∇=.Step 4 进行一维搜索,求tk,使得11(,),k k k k k k kX ls X P X X t P ++==+.Step 5 求梯度 f (Xk+1).若|| f (Xk+1)||≤ ε,停止输出Xk+1;否则. Step 6 检验迭代次数,若k+1=n,令X0=Xn 转(3);否则. Step 7 构造BFGS 方向,用BFGS 公式⎥⎥⎦⎤⎢⎢⎣⎡--⎪⎪⎭⎫ ⎝⎛++=+k T k k T k k k T kk k Tk kk T k kTk k k H y S S y H S S y S y H y y S H H 111计算,取,令1111,(),1k k k k H P H f X k k ++++=-∇=+转Step 4.（三）DFGS 算法的流程图结束开始计算∇f (X 0)给定X 0, H 0=I , ε>0计算∇f (X k +1)Xk+1取0000()(),0P H f X f X k =-∇=-∇=求t k 使),(1k k k P X ls X =+)(111+++∇-=k k k X f H P 1+=k k ||∇f (X 0)||≤εN||∇f (X k +1)||≤ εNk +1=n NX 0YY 令X 0=X nY四、变尺度法的算法分析Newton 法每次迭代都要计算目标函数的Hesse 矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了Newton 法收敛速度快的优点。

而变尺度算法则可以保持Newton 法收敛速度快的优点，又可以摆脱关于Hesse 矩阵的计算。

变尺度法中的二个重要算法DFP 算法和BFGS 算法迭代过程相同,区别仅在于校正矩阵Ek 选取不同,对于DFP 法,由于一维搜索的不精确和计算误差的积累可能导致某一轮的Hk奇异,而BFGS法对一维搜索的精度要求不高,并且由它产生的 Hk不易变为奇异矩阵.BFGS法比DFP法更具有好的数值稳定性,它比DFP 法更具有实用性.。