Numerical optimization globalization and inexact certificates

For any $x,y\in U$, convexity keeps the segment from $x$ to $y$ in $U$. Applying [F1] with Taylor order one gives $f(y)=f(x)+⟨\mathrm{\nabla }f(x),y-x⟩+\frac{1}{2}(y-x{)}^T{H}_f(x+\theta (y-x))(y-x)$ for some $\theta \in (0,1)$. The Hessian hypothesis makes the last term at least $\mu \mathrm{\parallel }y-x{\mathrm{\parallel }}_2^2\mathrm{/}2$, proving the first inequality. Since $H_f⪰\mu I⪰0$, [F2] also makes $f$ convex on $U$.

Let $x^{\ast }$ be an interior minimizer. For each standard basis vector $e_j$, openness gives an interval around $0$ on which $x^{\ast }+t{e}_j\in U$. The one-variable function $t\mapsto f(x^{\ast }+t{e}_j)$ has a minimum at $0$, so its derivative there is $0$; [F4] identifies this derivative with ${\mathrm{\partial }}_{j}f(x^{\ast })$. Thus every coordinate of $\mathrm{\nabla }f(x^{\ast })$ is zero.

Apply the first inequality from step 1.1 once to $(x,y)$ and once to $(y,x)$, and add. The function-value terms cancel, leaving $⟨\mathrm{\nabla }f(y)-\mathrm{\nabla }f(x),y-x⟩\ge \mu \mathrm{\parallel }y-x{\mathrm{\parallel }}_2^2$.

Apply step 1.1 with $x=x^{\ast }$ and $y=x$. Using $\mathrm{\nabla }f(x^{\ast })=0$ gives $f(x)-f^{\ast }\ge \mu \mathrm{\parallel }x-x^{\ast }{\mathrm{\parallel }}_2^2\mathrm{/}2$. This also proves uniqueness, because equality of the minimum values forces $x=x^{\ast }$.

Apply step 1.1 with the ordered pair $(x,x^{\ast })$ and write $d:=x-x^{\ast }$. Rearrangement gives $f(x)-f^{\ast }\le ⟨\mathrm{\nabla }f(x),d⟩-\mu \mathrm{\parallel }d{\mathrm{\parallel }}_2^2\mathrm{/}2$. By [F5] and completing the square, the right-hand side is at most $\mathrm{\parallel }\mathrm{\nabla }f(x){\mathrm{\parallel }}_2^2\mathrm{/}(2\mu )$, since $0\le (\mathrm{\parallel }\mathrm{\nabla }f(x){\mathrm{\parallel }}_2-\mu \mathrm{\parallel }d{\mathrm{\parallel }}_2{)}^2$. This is the gradient-gap inequality.

If $g=0$, [F6] gives $0\ge 2m(f(x)-f^{\ast })$; since $f(x)\ge f^{\ast }$ and $m>0$, $f(x)=f^{\ast }$, and uniqueness gives $x=x^{\ast }$. Now assume $g\mathrm{\ne }0$ and put $r(t):=x-tg$ for $t\ge 0$. [F3] gives ${\varphi }^{\mathrm{\prime }}(0)=-\mathrm{\parallel }g{\mathrm{\parallel }}_2^2<0$ for $\varphi (t):=f(r(t))$. Openness of $U$ and this strict derivative provide a sufficiently small $t>0$ with $r(t)\in U$ and $f(r(t))<f(x)\le f(x_0)$, so $S:=\{t\ge 0:r(t)\in K\}$ is nonempty.

By [F4], $f$ is convex on $V$, so its sublevel set $K$ is convex because $K\subset V$. By [F7], $K$ is closed and bounded. The affine map $r$ is continuous since $\mathrm{\parallel }r(s)-r(t){\mathrm{\parallel }}_2=\mathrm{\mid }s-t\mathrm{\mid }\mathrm{\parallel }g{\mathrm{\parallel }}_2$, so [F8] makes $S=r^{-1}(K)\cap [0,\mathrm{\infty })$ closed. Boundedness gives $c\in {\mathbb{R}}^d$ and $R_0>0$ with $K\subset B(c,R_0)$; hence $\mathrm{\parallel }y{\mathrm{\parallel }}_2\le \mathrm{\parallel }c{\mathrm{\parallel }}_2+R_0=:R$ on $K$. For $t\in S$, the triangle inequality [F11] yields $t\mathrm{\parallel }g{\mathrm{\parallel }}_2=\mathrm{\parallel }x-r(t){\mathrm{\parallel }}_2\le \mathrm{\parallel }x{\mathrm{\parallel }}_2+R$. Thus $S$ is bounded and compact by [F9].

The continuous restriction of $\varphi$ to the nonempty compact set $S$ attains a minimum $t_{\ast }\in S$ by [F10]. Since $0\in S$, we have $f(r(t_{\ast }))\le f(x)$. Every feasible ray parameter $t$ with $r(t)\in U$ but $t\mathrm{\notin }S$ has $f(r(t))>f(x_0)\ge f(x)\ge f(r(t_{\ast }))$, so $t_{\ast }$ is a global feasible-ray minimizer. If two distinct parameters minimized, their endpoints $y_1,y_2$ would be distinct because $g\mathrm{\ne }0$; their midpoint $z$ lies in $K$ by step 2.1. Apply the strong-convexity inequality [F6] from $z$ to each endpoint and add: $f(z)\le (f(y_1)+f(y_2))\mathrm{/}2-m\mathrm{\parallel }{y}_1-y_2{\mathrm{\parallel }}_2^2\mathrm{/}8$, strictly below their common minimum. Thus the minimizer is unique and the output specified by [F1] is well-defined.

The small step in step 1.1 strictly decreases $f$, so the minimizer from step 3.1 has $t_{\ast }>0$. Since $r(t_{\ast })\in K\subset U$ and $U$ is open, $t_{\ast }$ is interior to the feasible ray and ${\varphi }^{\mathrm{\prime }}(t_{\ast })=0$. Convexity of $V$ and step 2.1 put the segment $[x,r(t_{\ast })]$ in $V$. By [F2], [F3], and the Hessian bounds, $m\mathrm{\parallel }g{\mathrm{\parallel }}_2^2\le {\varphi }^{\mathrm{\prime }\mathrm{\prime }}(s)=g^T{H}_f(r(s))g\le M\mathrm{\parallel }g{\mathrm{\parallel }}_2^2$ on this segment, so ${\varphi }^{\mathrm{\prime }}$ is strictly increasing. The mean-value theorem [F12] applied to ${\varphi }^{\mathrm{\prime }}$ on $[0,t_{\ast }]$ gives $\mathrm{\parallel }g{\mathrm{\parallel }}_2^2={\varphi }^{\mathrm{\prime }}(t_{\ast })-{\varphi }^{\mathrm{\prime }}(0)=t_{\ast }{\varphi }^{\mathrm{\prime }\mathrm{\prime }}(s_0)\le t_{\ast }M\mathrm{\parallel }g{\mathrm{\parallel }}_2^2$ for some $s_0\in (0,t_{\ast })$. Since $g\mathrm{\ne }0$, division yields $t_{\ast }\ge 1\mathrm{/}M$.

The candidate $t_0:=1\mathrm{/}M$ lies in $[0,t_{\ast }]$ by step 4.1, so $r(t_0)$ lies on the segment from $x$ to $r(t_{\ast })$ and belongs to $V$. The lower Hessian bound makes ${\varphi }^{\mathrm{\prime }\mathrm{\prime }}(s)>0$ there; since ${\varphi }^{\mathrm{\prime }}(t_{\ast })=0$, ${\varphi }^{\mathrm{\prime }}(s)<0$ for $0\le s<t_{\ast }$. Hence $f(r(t_0))\le f(x)\le f(x_0)$ and $r(t_0)\in K$. Taylor's formula [F5] with the upper Hessian bound gives $f(r(t_0))\le f(x)-M^{-1}\mathrm{\parallel }g{\mathrm{\parallel }}_2^2+(M\mathrm{/}(2M^2))\mathrm{\parallel }g{\mathrm{\parallel }}_2^2=f(x)-\mathrm{\parallel }g{\mathrm{\parallel }}_2^2\mathrm{/}(2M)$. By the minimization proved in step 3.1, $f(x_{+})\le f(r(t_0))$.

Subtract $f^{\ast }$ in step 5.1 and use [F6] to get $f(x_{+})-f^{\ast }\le f(x)-f^{\ast }-\mathrm{\parallel }g{\mathrm{\parallel }}_2^2\mathrm{/}(2M)\le (1-m\mathrm{/}M)(f(x)-f^{\ast })$. The factor is nonnegative because $m\le M$. Exact steps never increase the objective, so every later iterate remains in $K$; applying the one-step bound successively proves the stated rate for all generated iterates.

At a nonstationary iterate, $g:=\mathrm{\nabla }f(x)\mathrm{\ne }0$, so [F1] uses the strict descent direction $p=-g$ and [F2] guarantees finite acceptance. Let $T:=2(1-a)\mathrm{/}M$. If $T\ge 1$, the initial trial $t=1$ satisfies $t\le T$. If $T<1$, [F3] gives an index $j$ with $b^j\le T$; choose the least such $j$, so $b^{j-1}>T$ and $b^j>bT$.

For any trial $0<t\le T$ on the assumed segment, [F5] and $H_f⪯MI$ give $f(x-tg)\le f(x)-t\mathrm{\parallel }g{\mathrm{\parallel }}_2^2+(M\mathrm{/}2)t^2\mathrm{\parallel }g{\mathrm{\parallel }}_2^2\le f(x)-at\mathrm{\parallel }g{\mathrm{\parallel }}_2^2$. Thus the initial trial is accepted when $T\ge 1$; when $T<1$, the candidate $b^j$ from step 1.1 passes, so the actual accepted step is at least $b^j>bT$. Both cases give $t_k\ge \min \{1,bT\}=\tau$.

Armijo acceptance and step 2.1 imply $f(x_{k+1})\le f(x_k)-a\tau \mathrm{\parallel }\mathrm{\nabla }f(x_k){\mathrm{\parallel }}_2^2$. Apply [F4] to obtain $f(x_{k+1})-f^{\ast }\le (1-2am\tau )(f(x_k)-f^{\ast })$. The factor is positive because $\tau \le 2b(1-a)\mathrm{/}M$ gives $2am\tau \le 4ab(1-a)m\mathrm{/}M<1$, and it is below one because $a,m,\tau >0$.

Every accepted step decreases $f$, so all generated iterates remain in $K$. Repeatedly apply step 3.1 along the generated updates; induction gives the asserted $k$-step bound, and a stopping status creates no later iterate.

At a nonstationary iterate, $H:=H_f(x)$ is symmetric positive definite by [F6] and the lower bound. Put $g:=\mathrm{\nabla }f(x)$ and $p:=-H^{-1}g$. The Newton decrement is ${\lambda }^2=g^T{H}^{-1}g=p^{T}Hp$, and [F5] gives ${\lambda }^2\ge \mathrm{\parallel }g{\mathrm{\parallel }}_2^2\mathrm{/}M$ and ${\lambda }^2\ge m\mathrm{\parallel }p{\mathrm{\parallel }}_2^2$.

Set $T_N:=2m(1-a)\mathrm{/}M$. For any trial $0<t\le T_N$, [F4] and $H_f⪯MI$ on its segment give $f(x+tp)\le f(x)-t{\lambda }^2+(M\mathrm{/}2)t^2\mathrm{\parallel }p{\mathrm{\parallel }}_2^2\le f(x)-at{\lambda }^2$, where the last inequality uses ${\lambda }^2\ge m\mathrm{\parallel }p{\mathrm{\parallel }}_2^2$. If $T_N\ge 1$, trial $t=1$ passes. If $T_N<1$, [F8] gives a least $j$ with $b^j\le T_N$; then $b^j>b{T}_N$ and that candidate passes, so the first accepted step is at least ${\tau }_N$.

For any accepted update before the local ball, ${\lambda }^2\ge \mathrm{\parallel }g{\mathrm{\parallel }}_2^2\mathrm{/}M$ by step 1.1 and $t\ge {\tau }_N$ by step 2.1. Armijo acceptance and [F3] therefore give $f(x_{+})-f^{\ast }\le f(x)-f^{\ast }-(a{\tau }_N\mathrm{/}M)\mathrm{\parallel }g{\mathrm{\parallel }}_2^2\le (1-2am{\tau }_N\mathrm{/}M)(f(x)-f^{\ast })$. The coefficient is positive because ${\tau }_N\le 2b(1-a)m\mathrm{/}M$ implies $2am{\tau }_N\mathrm{/}M\le 4ab(1-a)(m\mathrm{/}M{)}^2<1$; it is less than one because all factors in the subtracted term are positive.

If $x$ lies outside $B(x^{\ast },\rho )$, [F3] gives $f(x)-f^{\ast }\ge m{\rho }^2\mathrm{/}2$. Step 1.1 then gives ${\lambda }^2\mathrm{/}2\ge \mathrm{\parallel }g{\mathrm{\parallel }}_2^2\mathrm{/}(2M)\ge (m\mathrm{/}M)(f(x)-f^{\ast })\ge m^2{\rho }^2\mathrm{/}(2M)$. Thus if $\epsilon <m^2{\rho }^2\mathrm{/}(2M)$ the decrement test cannot stop outside the ball. Repeating step 3.1 gives a gap bounded by $q_N^k(f(x_0)-f^{\ast })$; choose $N$ with $q_N^N(f(x_0)-f^{\ast })<m{\rho }^2\mathrm{/}2$, which exists by [F8]. If no earlier stop occurs, [F3] places the $N$th generated iterate inside $B(x^{\ast },\rho )$. For larger tolerances the method may stop before this finite entry, and no post-stop sequence is asserted.

Starting the canonical local theorem [F2] at the first generated iterate in $B(x^{\ast },\rho )$ shows that every later generated iterate remains in that ball. Whenever its decrement test does not stop, [F2] gives $t_k=1$ and $\mathrm{\parallel }{x}_{k+1}-x^{\ast }{\mathrm{\parallel }}_2\le C\mathrm{\parallel }{x}_k-x^{\ast }{\mathrm{\parallel }}_2^2$. If the decrement test stops, the algorithm returns there and no later update is asserted.

Apply [F1] with $x=\tilde{x}$ and $y=x^{\ast }$. Since $\mathrm{\nabla }f(x^{\ast })=0$, it gives $\mu \mathrm{\parallel }\tilde{x}-x^{\ast }{\mathrm{\parallel }}_2^2\le ⟨\mathrm{\nabla }f(\tilde{x}),\tilde{x}-x^{\ast }⟩\le \mathrm{\parallel }\mathrm{\nabla }f(\tilde{x}){\mathrm{\parallel }}_2\mathrm{\parallel }\tilde{x}-x^{\ast }{\mathrm{\parallel }}_2$ by [F3]. If $\tilde{x}=x^{\ast }$ the result is immediate; otherwise divide by the positive distance to obtain $\mu \mathrm{\parallel }\tilde{x}-x^{\ast }{\mathrm{\parallel }}_2\le \mathrm{\parallel }\mathrm{\nabla }f(\tilde{x}){\mathrm{\parallel }}_2$.

The triangle inequality in [F3] and the two verified bounds give $\mathrm{\parallel }\mathrm{\nabla }f(\tilde{x}){\mathrm{\parallel }}_2\le \mathrm{\parallel }\widehat{g}{\mathrm{\parallel }}_2+\mathrm{\parallel }\mathrm{\nabla }f(\tilde{x})-\widehat{g}{\mathrm{\parallel }}_2\le \eta +\delta$. Combine with step 1.1 and divide by $\mu >0$.