Nonconvex line search and inexact newton methods

Let $D\subseteq {\mathbb{R}}^n$ be open, let $f:D\to \mathbb{R}$ be $C^1$ (Continuously differentiable maps, local inverses, and local diffeomorphisms), let $x\in D$, and let $p\in {\mathbb{R}}^n\setminus \{0\}$. Define the open parameter set $S_{x,p}:=\{t\in \mathbb{R}:x+tp\in D\}$, which contains $0$, the feasible ray $T_{x,p}:=S_{x,p}\cap [0,\mathrm{\infty })$, and $\varphi (t):=f(x+tp)$ for $t\in S_{x,p}$. At every $t\in S_{x,p}$, including $0$, the chain rule gives ${\varphi }^{\mathrm{\prime }}(t)=Df(x+tp)p$. By A total derivative computes every directional derivative, and its matrix is the Jacobian, the matrix of $Df$ is the Jacobian, whose scalar-field row is the transpose of the gradient. Hence ${\varphi }^{\mathrm{\prime }}(t)=⟨\mathrm{\nabla }f(x+tp),p⟩$, using the gradient convention of The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case and the Euclidean inner product of The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$. A direction is a descent direction at $x$ when ${\varphi }^{\mathrm{\prime }}(0)=⟨\mathrm{\nabla }f(x),p⟩<0$.

Assume for the line-search conditions below that $p$ is a descent direction at $x$. Fix constants $0<c_1<c_2<1\mathrm{/}2$. A feasible step $t>0$ is a Wolfe step when

It is a strong Wolfe step when it satisfies the first inequality and

The first inequality is the Armijo sufficient-decrease condition. The second Wolfe inequality is the curvature condition. Every strong Wolfe step is a Wolfe step, because ${\varphi }^{\mathrm{\prime }}(0)<0$ and the strong curvature bound implies ${\varphi }^{\mathrm{\prime }}(t)\ge -c_2\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(0)\mathrm{\mid }=c_2{\varphi }^{\mathrm{\prime }}(0)$.

For a descent direction define its descent angle $\theta \in [0,\pi \mathrm{/}2)$ by

The denominator is nonzero for a descent direction. The Cauchy–Schwarz inequality Cauchy-Schwarz $\mid ⟨x,y⟩\mid \le \parallel x{\parallel }_2\parallel y{\parallel }_2$ with its equality case, the triangle inequality for $\parallel \cdot {\parallel }_2$, the parallelogram law and polarisation ensures $0<\cos \theta \le 1$.

Let $D\subseteq {\mathbb{R}}^n$ be open, let $f:D\to \mathbb{R}$ be $C^1$, and let $x\in D$ and $p\mathrm{\ne }0$ satisfy $x+tp\in D$ for every $t\ge 0$. Let $\varphi (t)=f(x+tp)$ and suppose ${\varphi }^{\mathrm{\prime }}(0)<0$ and $\varphi$ is bounded below on $[0,\mathrm{\infty })$. For the constants $0<c_1<c_2<1\mathrm{/}2$ of Wolfe and strong Wolfe line-search conditions, the set of positive strong Wolfe steps contains a nonempty open interval.

Let $D\subseteq {\mathbb{R}}^n$ be open, let $f:D\to \mathbb{R}$ be $C^1$, let $x\in D$, and let $p\in {\mathbb{R}}^n$ be arbitrary. Fix $0<c_1<c_2<1\mathrm{/}2$ and finite budgets $E,Z\in \mathbb{N}$ for expansion and zoom trials. After the direction check passes, use the functions $\varphi (t)=f(x+tp)$ and ${\varphi }^{\mathrm{\prime }}(t)=⟨\mathrm{\nabla }f(x+tp),p⟩$ from Wolfe and strong Wolfe line-search conditions. Output: either a positive strong Wolfe step, or one of invalid-direction, domain-exit, and evaluation-budget-exhausted.

1. Evaluate and retain $f(x)$ and $\mathrm{\nabla }f(x)$, and set $\varphi (0):=f(x)$ and ${\varphi }^{\mathrm{\prime }}(0):=⟨\mathrm{\nabla }f(x),p⟩$. If ${\varphi }^{\mathrm{\prime }}(0)\ge 0$, return invalid-direction. Set $a:=0$ and $t:=1$. For at most $E$ expansion trials, in order:
   • If $x+tp\mathrm{\notin }D$, return domain-exit without evaluating the trial.
   • Evaluate $\varphi (t)$ and ${\varphi }^{\mathrm{\prime }}(t)$. If $\varphi (t)>\varphi (0)+c_{1}t{\varphi }^{\mathrm{\prime }}(0)$ or $\varphi (t)\ge \varphi (a)$, call the zoom procedure below with the ordered endpoint pair $(a,t)$ and return its output.
   • If $\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(t)\mathrm{\mid }\le c_2\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(0)\mathrm{\mid }$, return $t$ as a strong Wolfe step.
   • If ${\varphi }^{\mathrm{\prime }}(t)\ge 0$, call zoom with the reversed endpoint pair $(t,a)$ and return its output.
   • Otherwise set $a:=t$ and $t:=2t$.
2. If the expansion budget is exhausted, return evaluation-budget-exhausted.

For zoom(a,b), preserve the endpoint order even when $b<a$. For at most $Z$ zoom trials, in order:

1. Set $m:=(a+b)\mathrm{/}2$. If $x+mp\mathrm{\notin }D$, return domain-exit without evaluating the trial.
2. Evaluate $\varphi (m)$ and ${\varphi }^{\mathrm{\prime }}(m)$. If $\varphi (m)>\varphi (0)+c_{1}m{\varphi }^{\mathrm{\prime }}(0)$ or $\varphi (m)\ge \varphi (a)$, set $b:=m$. Otherwise, if $\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(m)\mathrm{\mid }\le c_2\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(0)\mathrm{\mid }$, return $m$ as a strong Wolfe step. In the remaining branch, if ${\varphi }^{\mathrm{\prime }}(m)(b-a)\ge 0$, first set $b:=a$; then set $a:=m$.
3. If the zoom budget is exhausted, return evaluation-budget-exhausted.

The procedure returns a step only after both strong Wolfe inequalities have been checked. Finite budgets and domain exits may return failure even when a strong Wolfe step exists; no convergence claim follows from the procedure alone.

Under the inputs of Finite-budget bracketing and zoom for a strong Wolfe step, assume all requested in-domain function and gradient evaluations terminate with real values and all prescribed comparisons are exact. The procedure terminates with its specified step or failure status. It makes at most $E$ expansion trial evaluations and at most one zoom call with at most $Z$ trial evaluations, hence at most $E+Z$ evaluated trial points. Each evaluates the objective and directional derivative at that point. Every returned step is positive, feasible, and satisfies both strong Wolfe inequalities. A domain-exit trial is not evaluated. The bound excludes the initial-point data and does not bound arithmetic work or guarantee success when a strong Wolfe step exists.

Let $D\subseteq {\mathbb{R}}^n$ be open, $f:D\to \mathbb{R}$ be $C^1$, and $x,p\in {\mathbb{R}}^n$ satisfy $x\in D$, $p\mathrm{\ne }0$, and $g^{T}p<0$, where $g:=\mathrm{\nabla }f(x)$. Let $t>0$ with $x+tp\in D$, and suppose there are a set $N\subseteq D$ containing $x+[0,t]p$ and a constant $L>0$ such that

If $t$ satisfies the Wolfe conditions of Wolfe and strong Wolfe line-search conditions with $0<c_1<c_2<1\mathrm{/}2$, then its descent angle $\theta$ satisfies

Let $D\subseteq {\mathbb{R}}^n$ be open, let $f:D\to \mathbb{R}$ be $C^1$ and let $x_0\in D$. Define its initial sublevel set $L_0:=\{x\in D:f(x)\le f(x_0)\}$, and suppose $f$ is bounded below on $L_0$. Let $N\subseteq D$ contain every segment $x_k+[0,t_k]p_k$ in a sequence $(x_k{)}_{k\ge 0}\subset D$. Suppose there is $L>0$ such that

For every $k\ge 0$, assume $x_{k+1}=x_k+t_k{p}_k$, $p_k\mathrm{\ne }0$ is a descent direction at $x_k$, and $t_k>0$ is a Wolfe step for $f,x_k,p_k$ under Wolfe and strong Wolfe line-search conditions. Define $\cos {\theta }_k:=-\frac{⟨\mathrm{\nabla }f(x_k),p_k⟩}{\mathrm{\parallel }\mathrm{\nabla }f(x_k){\mathrm{\parallel }}_2\mathrm{\parallel }{p}_k{\mathrm{\parallel }}_2}\mathrm{.}$ Then

Under the hypotheses of Wolfe steps imply the Zoutendijk summability condition, suppose there is a constant $\delta >0$ such that $\cos {\theta }_k\ge \delta$ for every $k$. Then $\mathrm{\parallel }\mathrm{\nabla }f(x_k){\mathrm{\parallel }}_2\to 0$. This is convergence of gradient norms to zero; it does not assert convergence of $(x_k)$ or that a limit point is a minimizer.

Let $n\ge 1$, let $U\subseteq {\mathbb{R}}^n$ be open, and let $f:U\to \mathbb{R}$ be twice continuously differentiable, meaning that $f$ is $C^1$ and its gradient is $C^1$. Write $g(x):=\mathrm{\nabla }f(x)$ and $H(x):={\mathrm{\nabla }}^{2}f(x)$ using The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case and The Hessian matrix and critical points of a scalar field. The identity matrix $I_n$ and matrix-vector products have the convention of Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes. Use the matrix-free access model of The matrix-free access model for Krylov methods for products $v\mapsto (H(x)+\lambda I_n)v$.

Linear-solver input: a fixed deterministic Krylov procedure $K$ which accepts a matrix-free linear operator $A$, a right-hand side $b$, a tolerance $\tau \ge 0$, and a finite inner-iteration budget $M\in {\mathbb{N}}_0$. It returns either no-candidate or candidate with a vector $p$ and an iteration count $m\in \{0,1,\dots ,M\}$ satisfying $p\in K_m(A,b)$, where $K_m$ is as defined by The Krylov subspace $K_m(A,b)=\mathrm{span}\{b,Ab,\dots ,A^{m-1}b\}$. A candidate's residual status is never trusted: this algorithm recomputes the requested residual using the supplied operator. Other inputs: $x_0\in U$, outer update budget $N\in {\mathbb{N}}_0$, forcing values ${\eta }_k\in [0,\bar{\eta }]$ for a fixed $0\le \bar{\eta }<1$, descent parameter $\sigma \in (0,1)$, regularization factor $\gamma >1$, initial shift ${\lambda }_0>0$, shift cap ${\lambda }_{\max }\ge {\lambda }_0$, regularized-attempt budget $J\in {\mathbb{N}}_0$, inner budget $M$, and the parameters and finite expansion/zoom budgets of Finite-budget bracketing and zoom for a strong Wolfe step. Output: the last valid iterate and one of stationary, iteration-budget-exhausted, no-descent-direction, or line-search-failure; in the last case also return the underlying line-search failure cause.

At iteration $k=0,1,\dots ,N$:

1. Compute $g_k:=g(x_k)$. If $g_k=0$, return $(x_k,\mathtt{\text{stationary}})$. If $k=N$, return $(x_k,\mathtt{\text{iteration-budget-exhausted}})$.
2. Set $\lambda :=0$. For $j=0,1,\dots ,J$, call $K$ on $A_{\lambda }v:=H(x_k)v+\lambda I_{n}v$, right-hand side $-g_k$, tolerance ${\eta }_k\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2$, and budget $M$. A no-candidate result is a rejected attempt. If it returns a candidate $p$, compute $r:=(H(x_k)+\lambda I_n)p+g_k$. Accept this linear solve only when $\mathrm{\parallel }r{\mathrm{\parallel }}_2\le {\eta }_k\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2$ and $⟨g_k,p⟩<-\sigma \mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{\parallel }p{\mathrm{\parallel }}_2$; otherwise reject it. If the attempt is accepted, retain this $p$ and immediately leave the regularization loop. If the attempt is rejected and either $j=J$ or $\lambda ={\lambda }_{\max }$, stop the regularization loop. Otherwise set $\lambda :=\min \{{\lambda }_{\max },{\lambda }_0\}$ when $\lambda =0$, and $\lambda :=\min \{{\lambda }_{\max },\gamma \lambda \}$ when $\lambda >0$; then continue with the next $j$.
3. If no attempt in step 2 was accepted, set $p:=-g_k$ and check $⟨g_k,p⟩<-\sigma \mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{\parallel }p{\mathrm{\parallel }}_2$. If this check fails, return no-descent-direction. For the stated $\sigma$ and $g_k\mathrm{\ne }0$ it passes, but the check remains part of the procedure.
4. Call Finite-budget bracketing and zoom for a strong Wolfe step at $x_k$ in direction $p$. If it returns failure, return $(x_k,\mathtt{\text{line-search-failure}},s)$, where $s$ is the returned line-search failure cause. Otherwise, for its returned strong Wolfe step $t_k$, set $x_{k+1}:=x_k+t_{k}p$ and continue.

The first unregularized system uses the forcing residual $\mathrm{\parallel }H(x_k)p+g_k{\mathrm{\parallel }}_2\le {\eta }_k\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2$. A regularized attempt checks the residual for the shifted system instead. Finite inner, regularization, and line-search budgets can return failure; the procedure makes no global convergence claim. The local rate theorem applies only to an unshifted $\lambda =0$ sequence taking full steps $t_k=1$ and remaining in its stated local tube. This algorithm does not assert that every run enters that branch.

Under the inputs of Finite-budget inexact Newton–Krylov with a descent safeguard, assume every call of the supplied Krylov procedure terminates within its budget of $M$ inner iterations, all requested in-domain function, gradient and Hessian-action evaluations terminate with real values, and the prescribed comparisons are exact. The algorithm terminates with its specified status, retaining the underlying search failure cause when applicable. Every iterate belongs to $U$. There are at most $N$ accepted updates, $N(J+1)$ Krylov calls, $N(J+1)M$ inner iterations, $N$ line-search calls, and $N(E+Z)$ evaluated line-search trial points. Separately, at most $N+1$ outer-iterate gradient evaluations and $N(J+1)$ recomputed candidate residuals occur. Each residual uses one Hessian action outside the Krylov solver. These counts do not bound the number of Hessian actions used internally by an arbitrary supplied solver, total arithmetic work, or convergence. In exact arithmetic the no-descent-direction branch is unreachable under the stated inputs.

For $n=0$, call a linear map invertible when it has a two-sided linear inverse, extending the positive-dimensional convention of Invertible Euclidean linear maps. Let $n\ge 0$ be an integer, let $U\subseteq {\mathbb{R}}^n$ be open, $F:U\to {\mathbb{R}}^n$ be $C^1$, and $x_{\ast }\in U$ satisfy $F(x_{\ast })=0$ with $J_{\ast }:=DF(x_{\ast })$ invertible. Suppose a closed Euclidean ball $K={\bar{B}}_2(x_{\ast },R)\subseteq U$ with $R>0$ is convex and

where $J(x):=DF(x)$ and $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}:={\sup }_{\mathrm{\parallel }v{\mathrm{\parallel }}_2=1}\mathrm{\parallel }Av{\mathrm{\parallel }}_2$ for $n\ge 1$; for $n=0$ set the norm of the unique linear map to $0$. Let $\mathrm{\parallel }v{\mathrm{\parallel }}_{\ast }:=\mathrm{\parallel }{J}_{\ast }v{\mathrm{\parallel }}_2$ and fix $\bar{\eta }\in [0,1)$. There are constants $r_0>0$, $C_F>0$, and $C\ge 0$ such that, whenever $\mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_2\le r_0$, $0\le \eta \le \bar{\eta }$, and $p,r\in {\mathbb{R}}^n$ satisfy

then $J(x)$ is invertible, $\mathrm{\parallel }F(x){\mathrm{\parallel }}_2\le C_F\mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_{\ast }$, and

Let $n\ge 0$ be an integer, let $U\subseteq {\mathbb{R}}^n$ be open, let $F:U\to {\mathbb{R}}^n$ be $C^1$, and let $x_{\ast }\in U$ satisfy $F(x_{\ast })=0$ with $J_{\ast }:=DF(x_{\ast })$ invertible. Suppose $J=DF$ is $L$-Lipschitz on a closed ball of positive radius about $x_{\ast }$ contained in $U$. Fix $\bar{\eta }\in [0,1)$. For $n=0$ use the zero operator-norm convention of An inexact Newton residual gives a local error recurrence. Consider any sequence $x_{k+1}=x_k+p_k,J(x_k)p_k+F(x_k)=r_k,\mathrm{\parallel }{r}_k{\mathrm{\parallel }}_2\le {\eta }_k\mathrm{\parallel }F(x_k){\mathrm{\parallel }}_2,$ with $0\le {\eta }_k\le \bar{\eta }$. Define $\mathrm{\parallel }v{\mathrm{\parallel }}_{\ast }:=\mathrm{\parallel }{J}_{\ast }v{\mathrm{\parallel }}_2$. There is $\rho >0$ such that, if $\mathrm{\parallel }{x}_0-x_{\ast }{\mathrm{\parallel }}_{\ast }\le \rho$, every iterate remains in the ball and $\mathrm{\parallel }{x}_k-x_{\ast }{\mathrm{\parallel }}_{\ast }\le q^k\mathrm{\parallel }{x}_0-x_{\ast }{\mathrm{\parallel }}_{\ast }$ for some $q<1$. Consequently:

1. If ${\eta }_k\to 0$, the iterates converge superlinearly (unless an exact root is reached, in which case the exact recurrence remains there).
2. If ${\eta }_k\le C_{\eta }\mathrm{\parallel }F(x_k){\mathrm{\parallel }}_2$ for a constant $C_{\eta }$, the iterates converge quadratically.

The fixed bound $\bar{\eta }<1$ gives linear convergence. Since $J_{\ast }$ is invertible, these rates in $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_{\ast }$ are equivalent to the same local rates in the Euclidean norm. For $F=\mathrm{\nabla }f$ with $f\in C^2(U)$ (all ordered partial derivatives through order two exist and are continuous), $J(x)={\mathrm{\nabla }}^{2}f(x)$, so the residual is the inexact Newton residual ${\mathrm{\nabla }}^{2}f(x_k)p_k+\mathrm{\nabla }f(x_k)$, using the Hessian convention of The Hessian matrix and critical points of a scalar field. This theorem concerns the unshifted full-step recurrence; it does not assert that a safeguarded line-search algorithm eventually selects that branch.