欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

「最优化」拟牛顿法

理解「拟牛顿法」之前,首先理解「牛顿法」和「共轭梯度法」,「拟牛顿」因为其较高的实用性,一直是工业界比较青睐的方法。

已知牛顿法的迭代步骤为:

\(x^{k+1}=x^k-\alpha_k F(x^k)^{-1} g^k \)

拟牛顿法就是寻找一个替代矩阵H,用来近似汉森矩阵的逆 \(F(x)^{-1}\) ,迭代公式可以改写为:

\(x^{k+1}=x^{k}-\alpha H g^k\)

为了保证每一步都是下降的,需要保证H的正定的。 简单证明如下:

\(\begin{matrix}f(x^{k+1})&=&f(x^k)+f'(x^k)(x^{k+1}-x^k) + o(|x^{k+1}-x^k|)\\ &=&f(x^k)-\alpha g^{(k)T} H_k g^k +o(|x^{k+1}-x^k|) \end{matrix}\)

到现在为止,已经介绍了好几个方法,拟牛顿法和别的方法的位置关系如下图:

CEAB6214-D85A-4FB1-A20E-0D51C9A31FA1

汉森矩阵逆矩阵的近似

拟牛顿法和牛顿法的区别就是不直接计算汉森矩阵的逆矩阵,而是通过另外一个矩阵直接近似汉森矩阵的逆。涉及到「近似」和「相似」这些词的时候,就说明两个矩阵有一些共性,例如三角形「相似」说的是三个角相等,这里的「近似」也是有一些标准。

\(H_0,H_1,...,H_k\) 表示汉森矩阵的逆 \(F(x^k)^{-1}\) 的一系列近似,对汉森矩阵,下面式子成立:

\(Q^{-1}\Delta{g^i}=\Delta{x^i}, i \in [0,k]\)

因此相似矩阵也要满足:

\(H_{k+1} \Delta g^i = \Delta x^i,i \in [0,k]\)

其中:

\(g^{k+1}-g^k=Q(x^{k+1}-x^k)\)

\(\Delta g^k=g^{k+1}-g^k\)

\(\Delta x^k = x^{k+1}-x^k\)

上面的条件还可以改为:

\( \begin{matrix}H_n \Delta g^0& = &\Delta x^0 \\ H_n \Delta g^1& = &\Delta x^1 \\ & \vdots & \\ H_n \Delta g^{n-1}& = &\Delta x^{n-1} \\ \end{matrix}\)

改成矩阵乘法的格式为:

\(H_n[\Delta g^0,\Delta g^1,...,\Delta g^{n-1}]=[\Delta x^0,\Delta x^1,...,x^{n-1}]\)

上面等式说明,如果 \([\Delta g^0,\Delta g^1,...,\Delta g^{n-1}]\) 是非奇异的,n词迭代之后 \(H_n\) 可以唯一确定。

拟牛顿的迭代公式

\(d^k=-H_k g^k\)

\(\alpha_k=\arg \min_{\alpha \ge 0}{f(x^k + \alpha d^k)}\)

\(x^{k+1} = x^k +\alpha_k d^k\)

其中H是对称矩阵,实际上拟牛顿法也是一种共轭方向法。容易证明,上式迭代过程中的n个迭代过程的方向是「共轭方向」。

从上面介绍可以看到, \(H_k\) 需要满足一些条件,但是并不是确定的。所以,这就有了针对如何计算 \(H_k\) 的空间。接下来讨论生成(修正) \(H_k\) 的方法。

秩1修正公式

\(H_{k+1}=H_k -\frac{(\Delta x^k-H_k \Delta g^k)(\Delta x^k - H_k \Delta g^k)^T}{\Delta g^{(k)T}(\Delta x^k - H_k \Delta g^k)}\)

秩1修正算法并不完全令人满意,首先该算法产生矩阵 \(H_{k+1}\) 并不一定是正定的,同时如果修正项的分母部分 \(\Delta g^{(k)T}(\Delta x^k - H_k \Delta g^k)\) 为0也会使得计算上面临一些问题。

 

DFP算法

\(H_{k+1}=H_k + \frac{\Delta x^k \Delta x^{(k)T}}{\Delta x^{(k)T} \Delta g^k}-\frac{[H_k \Delta g^k][H_k \Delta g^k]^T}{\Delta g^{(k)^T} H_k \Delta g^k}\)

DFP可以保证矩阵 \(H_{k}\) 保证正定,但是处理一些规模较大的非二次型问题的时候回出现「卡住」现象。造成这个现象的原因是 \(H_k\) 接近成为奇异矩阵了。

BFGS算法

BFGS是使用矩阵 \(B_k\) 对「汉森矩阵」近似,然后通过求 \(B_k\) 逆矩阵 \(H_k^{BFGS}\) 近似 \(F(x^n)^{-1}\) 。迭代公式为:

\(H_{k+1}=H_k+(1+\frac{\Delta ^{(k)T} H_k \Delta g^{k}}{\Delta g^{(k)T} \Delta x^k}) \frac{\Delta x^k \Delta x^{(k)T}}{\Delta x^{(x)T} \Delta g^k}-\frac{H_k \Delta g^k \Delta x^{(k)T}+(H_k \Delta g^k \Delta x^{(k)T})^T}{\Delta g^{(k)T} \Delta x^k}\)

在一维搜索精度不高时,BFGS仍然比较稳健,这一个性质有助于将计算资源从追求高精度的一维搜索中是放出来。就效率而言,BFGS算法远超DFP算法。

参考文献

《最优化导论》Edwin K.P.Chong Stanislaw H. Zak

未经允许不得转载:大数据算法 » 「最优化」拟牛顿法

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站