Limited memory quasi-Newton update

This is an extract from the paper "Limited memory Quasi-Newton method by Byrd, Nocedal and Schnabel, Math. Program.63, No.2(A), 129-156 (1994)."
The update is based on a different representation of the Quasi Newton matrices: With $s^k$ and $y^k$ in the usual meaning as in the (full) BFGS method, i.e.

${\displaystyle s^k=x^{k+1}-x^k,\mathrm{\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}}{y}^k=\nabla f(x^{k+1})-\nabla f(x^k)}$

Define the $n\times k$ matrices

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{S_k}& =\hfill & (s^0,\dots ,s^{k-1})\hfill \\ \multicolumn{1}{c}{Y_k}& =\hfill & (y^0,\dots ,y^{k-1})\hfill \end{array}}$

and the $k\times k$ matrices

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{(R_k{)}_{\mathrm{ij}}}& =\hfill & \{\begin{array}{cc}(s^{i-1}{)}^T{y}^{j-1}\hfill & i\le j\hfill \\ 0\hfill & i>j\hfill \end{array}\hfill \\ \multicolumn{1}{c}{D_k}& =\hfill & \text{diag}((s^0{)}^T{y}^0),\dots ,(s^{k-1}{)}^T{y}^{k-1}))\hfill \end{array}}$

Observe then $(s^i{)}^T{y}^i>0$ holds for all $i$. Then we get $A_k^{-1}$ (BFGS) as

${\displaystyle A_k^{-1}=A_0^{-1}+(S_k,A_0^{-1}{Y}_k)\left(\begin{array}{cc}\hfill (R_k{)}^{-T}(D_k+Y_k^T{A}_0^{-1}{Y}_k)R_k^{-1}\hfill & \hfill -R_k^{-T}\hfill \\ \hfill -R_k^{-1}\hfill & \hfill 0\hfill \end{array}\right)\left(\begin{array}{c}\hfill S_k^T\hfill \\ \hfill Y_k^T{A}_0^{-1}\hfill \end{array}\right)}$

---

File translated from T_EX by T_TM Unregistered, version 4.03.
On 16 Jun 2016, 16:38.