Bfgs and limited memory quasi newton methods — Examples

The gradient is $\mathrm{\nabla }f(x)=Ax$, so $g_0=(2,3{)}^T$ and the direction in [F2] is $p_0=-g_0=(-2,-3{)}^T$. Along this ray, ${\varphi }^{\mathrm{\prime }}(t)=g_0^T{p}_0+t{p}_0^{T}A{p}_0=-13+35t$, so the exact minimizer is ${\alpha }_0=13\mathrm{/}35$.

At this step ${\varphi }^{\mathrm{\prime }}({\alpha }_0)=0$, which satisfies the strong curvature test for $c_2=2\mathrm{/}5$. The quadratic identity $\varphi (\alpha )=\varphi (0)+\alpha {\varphi }^{\mathrm{\prime }}(0)+\frac{1}{2}{\alpha }^2{p}_0^{T}A{p}_0$ gives $\varphi ({\alpha }_0)-\varphi (0)=-169\mathrm{/}70\le -({10}^{-4})(169\mathrm{/}35)={10}^{-4}{\alpha }_0{\varphi }^{\mathrm{\prime }}(0)$, so the strong Wolfe Armijo test also holds.

The step and gradient change are $s_0={\alpha }_0{p}_0$ and $y_0=A{s}_0={\alpha }_0(-4,-9{)}^T$. Hence $s_0^T{y}_0=35{\alpha }_0^2>0$ and $s_0^T{B}_0{s}_0=13{\alpha }_0^2>0$.

Substitution in [F1] gives $B_1=I-\frac{1}{13}\left(\begin{array}{cc}4& 6\\ 6& 9\end{array}\right)+\frac{1}{35}\left(\begin{array}{cc}16& 36\\ 36& 81\end{array}\right)=\frac{1}{455}\left(\begin{array}{cc}523& 258\\ 258& 1193\end{array}\right)\mathrm{.}$ Multiplication yields $B_1{s}_0={\alpha }_0(-4,-9{)}^T=y_0$. The positive curvature from step 1.3 and [F3] also imply $B_1$ is SPD.

Here $g^{T}p=-1<0$, and $f(x+p)-f(x)=-3\mathrm{/}2$. The Armijo inequality holds for $c_1={10}^{-4}$, but the directional derivatives are ${\varphi }^{\mathrm{\prime }}(0)=-1$ and ${\varphi }^{\mathrm{\prime }}(1)=-2$. For $c_2=2\mathrm{/}5$, the Wolfe curvature test would require $-2\ge -2\mathrm{/}5$, which is false; the strong curvature test fails as well. Thus this is a nonconvex trial pair, not a step accepted by the strong-Wolfe search of [F4].

The raw pair has $s^{T}y=-1$, so its BFGS curvature denominator is negative. Direct substitution into the formal Hessian-update expression gives $I-s{s}^T+y{y}^T\mathrm{/}(-1)=\mathrm{diag}(-1,1)$, whose quadratic form at $e_1=(1,0{)}^T$ is $-1$; it is not SPD.

Here $c=s^{T}Bs=1$ and $s^{T}y=-1<0.2c$, so $\theta =0.8\mathrm{/}(1-(-1))=0.4$ and $\tilde{y}=0.4(-1,0{)}^T+0.6(1,0{)}^T=(0.2,0{)}^T$. Therefore $s^T\tilde{y}=0.2>0$, as also follows from [F2].

The damped update is $B^{+}=I-s{s}^T+\frac{\tilde{y}{\tilde{y}}^T}{s^T\tilde{y}}=\mathrm{diag}(0.2,1)\mathrm{.}$ It is SPD and $B^{+}s=(0.2,0{)}^T=\tilde{y}$, in agreement with [F3]. The example shows the algebraic role of damping; because the trial fails Wolfe, the normal line-search algorithm rejects it rather than treating it as a successful BFGS iteration.

Each dense matrix contains $n^2={1000}^2=\mathrm{1,000,000}$ real entries. The paired state in [F3] therefore stores $2n^2=\mathrm{2,000,000}$ matrix entries; a one-matrix implementation stores $n^2=\mathrm{1,000,000}$.

The L-BFGS pair list contains at most $2mn=2\cdot 10\cdot 1000=\mathrm{20,000}$ real coordinates, plus $O(n+m)$ temporary vectors and scalars.

In exact inverse-matrix mode, computing $p=-Hg$ uses one dense matrix-vector product and costs $O(n^2)$ scalar operations. For the direct update, first compute $u:=Bs$ with one dense matrix-vector product; since $B$ is symmetric, $Bs{s}^{T}B=u{u}^T$. Then form $B^{+}=B-u{u}^T\mathrm{/}(s^{T}u)+y{y}^T\mathrm{/}(s^{T}y)$ using two outer products and an entrywise matrix update, which costs $O(n^2)$. For the inverse update, first compute $v:=Hy$ with one dense matrix-vector product and expand [F4] using symmetry of $H$ to obtain $H^{+}=H-\rho (s{v}^T+v{s}^T)+(\rho +{\rho }^2{y}^{T}v)s{s}^T\mathrm{.}$ This uses a constant number of outer-product updates and also costs $O(n^2)$. Thus the dense direction and the paired BFGS updates use $O(n^2)$ work per iteration. By [F1], the two-loop recursion uses $O(mn)$ scalar work. Here $mn=\mathrm{10,000}$ while $n^2=\mathrm{1,000,000}$; the paired representation uses 100 times as many matrix entries as correction-pair coordinates, and a one-matrix representation uses 50 times as many. These are storage comparisons, not exact operation totals.