Full-memory Bfgs converges globally and linearly on a uniformly strongly convex level set

Since $x_{\ast }$ is a global minimizer in the open domain ${\mathbb{R}}^n$, the one-variable restriction $t\mapsto f(x_{\ast }+t{e}_j)$ has a minimum at $t=0$ for every standard basis vector $e_j$, so each partial derivative there is zero and $g_{\ast }:=\mathrm{\nabla }f(x_{\ast })=0$. For $x\in L_0$, [F10] gives the quadratic lower bound $f(x)-f(x_{\ast })\ge g_{\ast }^T(x-x_{\ast })+\frac{\mu }{2}\mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_2^2=\frac{\mu }{2}\mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_2^2\mathrm{.}$ Thus no other point of $L_0$ minimizes $f$, so $x_{\ast }$ is unique.

Initially $H_0$ is SPD. If $g_k\mathrm{\ne }0$ and $H_k$ is SPD, then $p_k=-H_k{g}_k$ is nonzero and $g_k^T{p}_k=-g_k^T{H}_k{g}_k<0$. The strong Wolfe step in [F1] is a Wolfe step by [F9], and [F3] gives $s_k^T{y}_k>0$; [F2] therefore preserves the SPD inverse pair. Its Armijo inequality gives $f(x_{k+1})\le f(x_k)$, hence induction keeps every iterate in $L_0$. If $g_k=0$, then for any $x\in L_0$ the segment from $x_k$ to $x$ lies in $L_0$ and [F10] gives $f(x)\ge f(x_k)+g_k^T(x-x_k)+\frac{\mu }{2}\mathrm{\parallel }x-x_k{\mathrm{\parallel }}_2^2=f(x_k)+\frac{\mu }{2}\mathrm{\parallel }x-x_k{\mathrm{\parallel }}_2^2$. Thus $x_k$ is the unique minimizer on $L_0$. Every point outside $L_0$ has value greater than $f(x_0)\ge f(x_k)$, so $x_k=x_{\ast }$.

At each nonstationary step define ${\eta }_k:=-\frac{g_k^T{p}_k}{\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{\parallel }{p}_k{\mathrm{\parallel }}_2}\in (0,1],B_k:=H_k^{-1}\mathrm{.}$ Since $B_k{p}_k=-g_k$ and $s_k={\alpha }_k{p}_k$, one has $B_k{s}_k=-{\alpha }_k{g}_k$ and therefore ${\eta }_k=\frac{s_k^T{B}_k{s}_k}{\mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2\mathrm{\parallel }{B}_k{s}_k{\mathrm{\parallel }}_2}\mathrm{.}$ The value is at most $1$ by [F8].

The function is bounded below on $L_0$ by $f(x_{\ast })$. Each accepted step segment lies in $L_0$ because its endpoints are in this convex set by step 1.2. Its gradient is $\mathrm{\Lambda }$-Lipschitz by [F10], so the segment and lower-bound hypotheses of [F5] hold for the accepted Wolfe steps.

Apply [F10] to $u=x_{k+1}$ and $v=x_k$. Its strong-monotonicity bound gives $s_k^T{y}_k\ge \mu \mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2^2$, and its gradient-Lipschitz bound gives $\mathrm{\parallel }{y}_k{\mathrm{\parallel }}_2\le \mathrm{\Lambda }\mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2$. Hence $m_k\ge \mu$ and $M_k\le {\mathrm{\Lambda }}^2\mathrm{/}\mu$. With $C_0$ as in the Statement, [F4] gives $\psi (B_{k+1})\le \psi (B_k)+C_0+\log {\eta }_k^2,$ after dropping the nonpositive term $h(q_k\mathrm{/}{\eta }_k^2)$.

Summing step 2.2 for $k=0,\dots ,N-1$ and using $\psi (B_N)>0$ yields ${\sum }_{k=0}^{N-1}-\log {\eta }_k^2\le \psi (B_0)+C_{0}N\mathrm{.}$ Put $c_k:={\eta }_k^2>0$ and ${\bar{c}}_N:=N^{-1}{\sum }_{k<N}{c}_k$. For $u>0$, [F4] gives $\log u\le u-1$ because $h(u)=1-u+\log u\le 0$. Apply this to $u=c_k\mathrm{/}{\bar{c}}_N$ and sum to obtain $N^{-1}{\sum }_{k<N}\log c_k\le \log {\bar{c}}_N$. Therefore ${\bar{c}}_N\ge \exp \text{\hspace{0.17em}⁣}(-C_0-\frac{\psi (B_0)}{N})\ge \delta \mathrm{.}$ In particular, infinitely many indices satisfy ${\eta }_k^2\ge \delta \mathrm{/}2$; otherwise the prefix averages would eventually be less than $\delta$.

By [F6] and the Armijo inequality, $r_k-r_{k+1}\ge c_1{\alpha }_k(-g_k^T{p}_k)\ge \frac{c_1(1-c_2)}{\mathrm{\Lambda }}{\eta }_k^2\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2\mathrm{.}$ For $e_k:=x_k-x_{\ast }$, [F10] applied with $u=x_{\ast }$ and $v=x_k$ gives $r_k\le g_k^T{e}_k-\frac{\mu }{2}\mathrm{\parallel }{e}_k{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{\parallel }{e}_k{\mathrm{\parallel }}_2-\frac{\mu }{2}\mathrm{\parallel }{e}_k{\mathrm{\parallel }}_2^2\le \frac{\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2}{2\mu },$ where the last inequality is completion of the square in $\mathrm{\parallel }{e}_k{\mathrm{\parallel }}_2$. Set $\tau =2\mu c_1(1-c_2)\mathrm{/}\mathrm{\Lambda }$. Since $\mu \le \mathrm{\Lambda }$ and $0<c_1<c_2<1\mathrm{/}2$, $0<\tau <1$. The decrease inequality therefore yields $r_{k+1}\le (1-\tau {\eta }_k^2)r_k$.

By [F5], the nonnegative summands ${\eta }_k^2\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2$ tend to zero. Along the infinite subsequence from step 3.1, ${\eta }_k^2\ge \delta \mathrm{/}2$, so $\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\to 0$ on that subsequence. For any $x\in L_0$, [F10] gives $(\mathrm{\nabla }f(x)-g_{\ast }{)}^T(x-x_{\ast })\ge \mu \mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_2^2$. By [F8], $\mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_2\le \mathrm{\parallel }\mathrm{\nabla }f(x){\mathrm{\parallel }}_2\mathrm{/}\mu$. Thus the subsequence converges to $x_{\ast }$ and its function values converge to $f(x_{\ast })$. The full sequence $f(x_k)$ is nonincreasing by step 1.2 and bounded below by $f(x_{\ast })$, so it converges to $f(x_{\ast })$. Step 1.1 then gives $x_k\to x_{\ast }$.

For $u\ge 0$, put $t:=\exp (-u)>0$. By [F4] and [F11], $h(t)=1-t+\log t=1-e^{-u}-u\le 0$, so $1-u\le e^{-u}$. Apply this with $u=\tau {\eta }_j^2$ in step 3.2. Using ${\sum }_{j<k}{\eta }_j^2\ge \delta k$ from step 3.1 gives $r_k\le r_0{\prod }_{j<k}(1-\tau {\eta }_j^2)\le r_0\exp \text{\hspace{0.17em}⁣}(-\tau {\sum }_{j<k}{\eta }_j^2)\le r_0{e}^{-\tau \delta k}\mathrm{.}$ This is the claimed objective-gap bound.

Finally, step 1.1 gives $\mathrm{\parallel }{x}_k-x_{\ast }{\mathrm{\parallel }}_2\le \sqrt{2r_k\mathrm{/}\mu }\le \sqrt{2r_0\mathrm{/}\mu }{e}^{-\tau \delta k\mathrm{/}2}$. Thus the iterates have an R-linear error bound.