机器人中的数值优化|【四】L-BFGS理论推导与延伸

机器人中的数值优化|【四】L-BFGS理论推导与延伸

往期内容回顾

机器人中的数值优化|【一】数值优化基础
机器人中的数值优化|【二】最速下降法，可行牛顿法的python实现，以Rosenbrock function为例
机器人中的数值优化|【三】无约束优化，拟牛顿法理论与推导

L-BFGS方法

在上一节中我们对拟牛顿法进行了详细的推导，特别是对BFGS的推导过程比较熟悉了，我们发现BFGS虽然解决了牛顿法中hessian可能不存在以及hessian求逆计算复杂的通电，但是在大规模优化过程中，很可能没有办法去存储一个$n\times n$矩阵，因此Limited memory GFGS算法自然而然就被提出，表示使用有限的空间来进行计算。观察原来的式子
$$\Delta B_t=\frac{\Delta g_t\Delta g_t^T}{\Delta x_t\Delta g_t^T}-\frac{B_t\Delta x_t\Delta x_t^T{B}_t^T}{\Delta x_t^T\Delta B_t^T\Delta x_t}$$
$$B_{t+1}^{-1}=(I_n-\frac{\Delta x\Delta g^T}{\Delta x_t^T\Delta g_t})B_t^{-1}(I_n-\frac{\Delta g_t\Delta x_t^T}{\Delta x_t^T\Delta g_t})+\frac{\Delta x_t\Delta x_t^T}{\Delta x_t^T\Delta g_t}$$
我们很容易知道，$B_{t+1}$可以通过迭代计算$\Delta x_t,\Delta g_t$来得到，LBFGS的思想是不再使用所有的$\Delta x_t,\Delta g_t$，而是通过使用最近的$m$个序列来计算。这样只需要保存$2m$个向量，然后每次迭代最近的结果即可计算出近似矩阵$B$，避免显式保存矩阵信息。
令
$${\rho }_k=\frac{1}{\Delta x_k^T\Delta g_k}$$
$$V_k=I-{\rho }_k\Delta x_k\Delta g_k^T$$
可以简写为
$$B_{t+1}^{-1}=V_k{B}_t^{-1}{V}_k^T+{\rho }_k\Delta x_t\Delta x_t^T$$
实际工程应用中，可以使用two-loop recursion方法，直接计算得到搜索方向，不用显示计算矩阵，如下所示：