L-BFGS

L-BFGS###

先介绍下BFGS算法过程

G_{k+1} = V_k^T G_k V_k + \rho_k s_k s_k^T \\ \rho_k = \frac {1}{y_k^T s_k} , V_k = I - \rho_k y_k s_k^T

缺点：矩阵本身的存储大小 $G_k$

\begin{align} G_{k+1} & = (V_{k-1}^T \ldots V_0^T) G_0 (V_0 \ldots V_{k-1}) \\ & + (V_{k-1}^T \ldots V_1^T) s_0 \rho_0 s_0^T (V_1 \ldots V_{k-1}) \\ & + (V_{k-1}^T \ldots V_2^T) s_1 \rho_1 s_1^T (V_2 \ldots V_{k-1}) \\ & + (V_{k-1}^T \ldots V_3^T) s_2 \rho_2 s_2^T (V_3 \ldots V_{k-1}) \\ & + \ldots \\ & + V_{k-1}^T s_{k-2} \rho_{k-2} s_{k-2}^T V_{k-1} \\ & + s_{k-1} \rho_{k-1} s_{k-1}^T \\ \end{align}

从易存储的初始矩阵出发，可以迭代求出 $G_k$ 。而且计算到一定步数之后，可以不用从第一步开始迭代，比如可以取从前m步开始迭代，找一个 $G_k^0$ 跟前m步迭代结果“差不多”就可以近似了。所以递归公式为：

\begin{align} G_{k+1} & = (V_{k-1}^T \ldots V_{k-m}^T) G_k^0 (V_{k-m} \ldots V_{k-1}) \\ & + (V_{k-1}^T \ldots V_{k-m+1}^T) s_{k-m} \rho_{k-m} s_{k-m}^T (V_{k-m+1} \ldots V_{k-1}) \\ & + (V_{k-1}^T \ldots V_{k-m+2}^T) s_{k-m+1} \rho_{k-m+1} s_{k-m+1}^T (V_{k-m+2} \ldots V_{k-1}) \\ & + (V_{k-1}^T \ldots V_{k-m+3}^T) s_{k-m+2} \rho_{k-m+2} s_{k-m+2}^T (V_{k-m+3} \ldots V_{k-1}) \\ & + \ldots \\ & + V_{k-1}^T s_{k-2} \rho_{k-2} s_{k-2}^T V_{k-1} \\ & + s_{k-1} \rho_{k-1} s_{k-1}^T \end{align}

所求方向：

\begin{align} G_{k+1} \nabla f & = (V_{k-1}^T \ldots V_{k-m}^T) G_k^0 (V_{k-m} \ldots V_{k-1}) \nabla f \\ & + (V_{k-1}^T \ldots V_{k-m+1}^T) s_{k-m} \rho_{k-m} s_{k-m}^T (V_{k-m+1} \ldots V_{k-1}) \nabla f \\ & + (V_{k-1}^T \ldots V_{k-m+2}^T) s_{k-m+1} \rho_{k-m+1} s_{k-m+1}^T (V_{k-m+2} \ldots V_{k-1}) \nabla f \\ & + (V_{k-1}^T \ldots V_{k-m+3}^T) s_{k-m+2} \rho_{k-m+2} s_{k-m+2}^T (V_{k-m+3} \ldots V_{k-1}) \nabla f \\ & + \ldots \\ & + V_{k-1}^T s_{k-2} \rho_{k-2} s_{k-2}^T V_{k-1} \nabla f \\ & + s_{k-1} \rho_{k-1} s_{k-1}^T \nabla f \end{align}

等一等，这个式子中有大量的重复计算：

\begin{align} G_{k+1} \nabla f &= \color{RoyalBlue}{ (V_{k-1}^T \ldots V_{k-m}^T) } G_k^0 \color{ForestGreen}{ (V_{k-m} \ldots V_{k-1}) \nabla f } \\ & + \color{RoyalBlue}{(V_{k-1}^T \ldots V_{k-m+1}^T)} s_{k-m} \rho_{k-m} s_{k-m}^T \color{ForestGreen}{ (V_{k-m+1} \ldots V_{k-1}) \nabla f }\\ & + \color{RoyalBlue}{(V_{k-1}^T \ldots V_{k-m+2}^T)} s_{k-m+1} \rho_{k-m+1} s_{k-m+1}^T \color{ForestGreen}{ (V_{k-m+2} \ldots V_{k-1}) \nabla f }\\ & + \color{RoyalBlue}{(V_{k-1}^T \ldots V_{k-m+3}^T)} s_{k-m+2} \rho_{k-m+2} s_{k-m+2}^T \color{ForestGreen}{ (V_{k-m+3} \ldots V_{k-1}) \nabla f }\\ & + \ldots \\ & + \color{RoyalBlue}{ V_{k-1}^T } s_{k-2} \rho_{k-2} s_{k-2}^T \color{ForestGreen}{ V_{k-1} \nabla f} \\ & + s_{k-1} \rho_{k-1} s_{k-1}^T \color{ForestGreen}{\nabla f } \end{align}

右侧优化：

递推： $q_i = V_i q_{i+1}$
初始： $q_k = \nabla f$
得到：$$
\begin{align}
q{k-1} &= V{k-1} \nabla f \
q{k-2} &= V{k-2} V_{k-1} \nabla f \
\ldots \
q{k-m} &= V{k-m} \ldots V{k-2} V{k-1} \nabla f
\end{align}
$$
$\alpha_{k-i} = \rho_{k-i} s_{k-i}^T ( V_{k-i+1} V_{k-i+2} \ldots V_{k-2} V_{k-1}) \nabla f$

然后左侧优化：

递推： $r_{i+1} = V_{i+1}^T r_i + s_{i+1} \alpha_{i+1} = r_i + s_{i+1} (\alpha_{i+1} - \rho_{i+1} y_{i+1}^T r_i)$
初始： $r_{k-m} = V_{k-m}^T G_k^0 (V_{k-m} \ldots V_{k-1}) \nabla f + s_{k-m} \alpha_{k-m}$
得到$$
r{k-1} = (V{k-1}^T \ldots V{k-m}^T) G_k^0 (V{k-m} \ldots V_{k-1}) \nabla f \
(V{k-1}^T \ldots V{k-m+1}^T) s{k-m} \alpha{k-m} \
(V{k-1}^T \ldots V{k-m+2}^T) s{k-m+1} \alpha{k-m+1} \
(V{k-1}^T \ldots V{k-m+3}^T) s{k-m+2} \alpha{k-m+2} \
\ldots \
V{k-1}^T s{k-2} \alpha_{k-2} \
s{k-1} \alpha{k-1}
$$