拟牛顿法

请注意，文章中部分理解可能已被笔者废弃，本文最后更新于：7 个月前

拟牛顿法(Quasi-Newton Methods)
是求解非线性优化问题最有效的方法之一。其在牛顿法的基础上，利用相邻两个点的位移和一阶导数信息构造与二阶导数阵相似的正定矩阵。从而以在不直接计算Hessian矩阵的情况下实现高维问题的超线性收敛。

牛顿法通过计算每一步的梯度 ∇f(xk)\nabla f\left(\mathbf{x}_{k}\right) 与Hessian矩阵 Hf(xk)\mathbf{H}_{f}\left(\mathbf{x}_{k}\right) 迭代更逼近驻点的 xk+1\mathbf{x}_{k+1}

xk+1=xk−Hf−1(xk)∇f(xk).\mathbf{x}_{k+1}=\mathbf{x}_{k}-\mathbf{H}_{f}^{-1}\left(\mathbf{x}_{k}\right) \nabla f\left(\mathbf{x}_{k}\right).

其最大难度在于求解维度超大的Hessian矩阵与其逆矩阵 Hf−1(xk)\mathbf{H}_{f}^{-1}\left(\mathbf{x}_{k}\right) ，而拟牛顿法则通过一维导数（梯度）的变化便可以得到近似的Hessian矩阵，而大大降低了求解难度与求逆的时间。

基本步骤

（以下高维向量、矩阵不再加粗表示）

记 BkB_k 表示第 kk 次迭代的近似Hessian矩阵称为切线刚度矩阵，其初始为单位矩阵，即 B0=IB_0=I. 根据

Bkpk=−∇f(xk)B_kp_k=-\nabla f\left(x_{k}\right)

计算 pkp_k ，作为每一次迭代的步。

xk+1=xk+αpkx_{k+1}=x_k+\alpha p_k

其中 α\alpha 一般计为 1.01.0，也可以从 1.01.0 折半查找，直到 f(xk+1)f(x_{k+1}) 更优。计算

sk=αpk , yk=∇f(xk+1)−∇f(xk).s_k=\alpha p_k\ ,\ y_k=\nabla f\left(x_{k+1}\right)-\nabla f\left(x_{k}\right).

计算新的刚度矩阵

Bk+1=Bk−BkskskTBkskTBksk+ykykTykTsk（BFGS算法）.B_{k+1}=B_{k}-\frac{B_{k} s_{k} s_{k}^{T} B_{k}}{s_{k}^{T} B_{k} s_{k}}+\frac{y_{k} y_{k}^{T}}{y_{k}^{T} s_{k}} （BFGS算法）.

若误差足够小，如等式约束两端误差小于 ϵ\epsilon 则得到解，否则继续迭代。

刚度矩阵算法

以上以BFGS法为例，介绍了基本的拟牛顿法步骤，其他方法也仅仅在计算刚度矩阵上进行的变化。

DFP法

Bk+1=Bk−BkykykTBkykTBkyk+skskTykTskB_{k+1}=B_{k}-\frac{B_{k} y_{k} y_{k}^{T} B_{k}}{y_{k}^{T} B_{k} y_{k}}+\frac{s_{k} s_{k}^{T}}{y_{k}^{T} s_{k}}

DFP方法是秩-2更新的一种，由它产生的矩阵 BkB_k 是正定的，而且满足这样的极小性：

min⁡B∣B−Bk∣ s.t. B=BT,Bsk=yk\min _{B}\left|B-B_{k}\right| \text { s.t. } B=B^{T}, B s_{k}=y_{k}

BFGS法

Bk+1=Bk−BkskskTBkskTBksk+ykykTykTskB_{k+1}=B_{k}-\frac{B_{k} s_{k} s_{k}^{T} B_{k}}{s_{k}^{T} B_{k} s_{k}}+\frac{y_{k} y_{k}^{T}}{y_{k}^{T} s_{k}}

该方法 BkB_k 同样正定，也同样满足上述的极小性。

且BFGS和DFP公式在形式上是对称的，但是BFGS比DFP更加有效。

对称秩1（SR1）法

Bk+1=Bk+(yk−Bksk)(yk−Bksk)T(yk−Bksk)TskB_{k+1}=B_{k}+\frac{\left(y_{k}-B_{k} s_{k}\right)\left(y_{k}-B_{k} s_{k}\right)^{T}}{\left(y_{k}-B_{k} s_{k}\right)^{T} s_{k}}

有别于DFP和BFG方法，SR1是一种秩-1更新。

SR1公式不要求矩阵 BkB_k 保持正定性，从而更逼近真实的Hesse矩阵，所以适用于信赖域方法(Trust Region Methods)。

Broyden族

Bk+1=(1−ck)Bk+1BFGS+ckBk+1DFPB_{k+1}=\left(1-c_{k}\right) B_{k+1}^{B F G S}+c_{k} B_{k+1}^{D F P}

当 ck=0c_k=0 时，Broyden族公式就变成了BFGS公式；当 ck=1c_k=1 时，Broyden族公式就变成了DFP公式。因此BFGS和DFP均可看成Broyden族的特殊形式或者其中一员。

参考