拟牛顿法

拟牛顿法武等站今消宗鸡著在，是求解非线性优化问题最有效的方法之速一，这种算法在当时看来是非线性优化领域最具创造性的发明之一。

概述

　　拟牛顿法(Quasi-N安们坐国省找反把呀艺害ewton Methods)是求解非线性优化问题率最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W. C. Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fl来自etcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论360百科文。

拟牛顿法

　　拟牛顿法传实图热专但回和最速下降法(Steepest Descent Methods)一移从助互据种方样只要求每一步迭代时知道目标函数的梯度。通探免外混额别金频斗过测量梯度的变化，构端亮院助背造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对势黑车于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法(Newton's Method)更为有效致鸡织南氢。如今，优化软件中包含了大量的拟牛顿算法用等青天广松新落好井来解决无约束，约束，和大规模的优化问题。

　　拟牛顿法的基本思想如下。首秋迅卷空渐配先构造目标函数在当前迭代$x_k$的二次模型：m_k(p)=f_k+g_k^T p+p^T B_k p/2，这里f_k=f(x_k)，g_k=▽f(x_k)，B_k是一个对称正定矩阵。于是我们取这个二次模型的最优解p_k=-B_k^{-1直持练例亲伯江吗念酸} g_k作为搜索方向，并且得到新的迭代点x_{镇染金准喜k+1}=x_k切+a_k p_k，其中我用掌便报航农宗架怀新们要求步长a_k满足Wolfe条件。这样的迭代类似与牛顿法，区别就在于用近似的Hesse矩阵B_k代替真实的Hesse矩阵。所以拟牛顿法最关键的地望依影方就是每一步迭代中矩阵B_k的更新。现在假设得到一个新的迭代x_{k+1}，并得到一个新的二次模型：m_{k+1}(p)刚=f_{k+1}+g_{k+1}^T p + p^T B_{k+1} p/2。我们尽可能地利用上一步的信息来选取B_{k+火1}。具体地，我们要求g_{k+1}-g_k=a_k B_{k+1} p_k，从而得到B_{k+1}s_k=y_k，其中s_k=x_{k+1}-x_k，y_k=g_{k+1}-g_k。这个公式被称为割兴线方程。下面主要介绍这几种方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。

DFP方法

　　记H_k=B_k^{-1}，DFP公式为H_{k+1}=H_k-(H_ky_ky_k^TH_k)/(y_k^T H_k y_k)+(s_ks_k^T)/(y_k^Ts_k)。该公式最初由Davidon于1959年提出，随后被Fletcher和Powell研究和推广。DFP方法是秩-2更新的一种，由它产生的矩阵B_k是正定的，而且满足这样的极小性：min ||B-B_k|| s.t. B=B^T, Bs_k=y_k。

BFGS方法

　　DFP更新公式非常有克倍周值排线意既等听余效，但很快就被BFGS公式取代。BFGS与DFP十分类似，是另一种秩-2更新，以其发明者Boyden, Fletcher, Goldfarb和Shanno的姓氏首字母命名。BFGS公式为B_{k+1}=B_k-(B_ks_ks_k^TB_k)/(s_k^T B_k s_k)季结阻+(y_ky_k^T)/(y_k^Ts_k)。由他产生的矩阵B_k同样保持正定性，而且也满足一个极小性：min ||H-H_k|| s来自.t. H=H^T, Hy_k=s_k。BF360百科GS和DFP公式县积被在形式上是对称的：B_k与H_k对称，s_k与y_k对称。但是BFGS比D稳形降将测气官FP更加有效。

SR1方法

　　有别于DFP和BFG方法，SR1是一种秩-1更新。备担绝述财法非娘鲁下的它的公式是：B_{k+1}=均紧钟稳(y_k-B_ks_k)(y_k-B_ks_k)^T/((y_k-B_ks_k)^Ts_k)。SR1公式不要求矩阵B_k保持正定性，从而更逼近真实的Hesse矩阵，所以适用于信极续劳赖域方法(Trust Region Methods)。

Broyden族

　　Boyden族是更广泛的一类更新公式，其形式为：B_{k+1}=(1师-c_k)B_{k+1}^{BFGS}+c_k B_{k+1}^{DFP}。当c_k=0时，Broyden族公式就变成了BFGS公式；当c_k=1时判识松，Broyden族公式就变成了DFP公式。因此BFGS和DFP均可看成Broyden族的特殊形式或者其中一员。