Farhad Rahbarnia was partially supported by Alexander Graham Bell Canada Graduate Scholarships - Doctoral number 568744-2022. Dominique Orban was partially supported by NSERC Discovery Grant RGPIN–2020–06535.
Farhad Rahbarnia GERAD and Department of Mathematics and Industrial Engineering, Polytechnique Montréal. E-mail: farhad.rahbarnia@polymtl.ca
Dominique Monnet Université de Rennes, INSA Rennes, CNRS, IRMAR-UMR 6625, F-35000 Rennes, France. E-mail: dominique.monnet@insa-rennes.fr
Dominique Orban GERAD and Department of Mathematics and Industrial Engineering, Polytechnique Montréal. E-mail: dominique.orban@gerad.ca
Introduction
We consider the solution of
minimize x ∈ R n f ( x ) , (1) \underset{x\in\mathbb{R}^{n}}{\operatorname{minimize}}\ f(x), \tag*{(1)} x ∈ R n minimize f ( x ) , (1)
where f : R n → R f:\mathbb{R}^{n}\to\mathbb{R} f : R n → R is C 1 C^{1} C 1 by way of a modified Newton or quasi-Newton method with quadratic regularization. At each iteration, a step is computed by approximately minimizing the sum of a quadratic model of f f f about the current iterate and a multiple of the squared step norm. The multiple in question is a regularization parameter that is updated according to the decrease in f f f induced by the step. Such methods recently received renewed attention, e.g., from Kanzow and Steck [30 ] , who study direct solvers based on limited-memory quasi-Newton approximations, and Diouane et al. [15 ] , who derive convergence and complexity properties under weak assumptions, even when the objective includes a nonsmooth regularizer. Quadratic regularization is related to line search methods and is a well-known alternative to trust-region methods [10 ] . One of its appealing features is that subproblems are unconstrained. It is famously used in the method of Levenberg [34 ] and Marquardt [40 ] for nonlinear least squares.
We propose solver R2N, whose salient features are
a global convergence analysis that follows from [15 ] under the sole assumption that f ∈ C 1 f\in C^{1} f ∈ C 1 , with model Hessians allowed to grow unbounded at a controlled rate, and under a lower bound on Armijo-Goldstein step lengths when directions of nonpositive curvature are exploited;
a structured worst-case evaluation complexity analysis that separates positive- and nonpositive-curvature steps under Lipschitz continuity of ∇ f \nabla f ∇ f and ∇ 2 f \nabla^{2}f ∇ 2 f at the iterates along the steps computed by the algorithm that corrects misleading bounds from [39 ] :
if the sequence of model Hessians { B k } \{B_k\} { B k } remains bounded, we show that accepted steps along which curvature is positive contribute a term proportional to ε − 2 \varepsilon^{-2} ε − 2 to the total number of evaluations to bring ∥ ∇ f ( x k ) ∥ \lVert\nabla f(x_k)\rVert ∥ ∇ f ( x k )∥ below ε > 0 \varepsilon>0 ε > 0 ;
when { B k } \{B_k\} { B k } is allowed to grow unbounded, this first bound deteriorates—see Proposition 13 ;
when B k = ∇ 2 f ( x k ) B_k=\nabla^{2}f(x_k) B k = ∇ 2 f ( x k ) , accepted steps along which curvature is nonpositive contribute a term proportional to ε − 3 / 2 \varepsilon^{-3/2} ε − 3/2 ;
this second bound may further deteriorate when the model curvature is inexact along the step—see Theorem 2;
superlinear or quadratic local convergence near an isolated local minimizer for a variant in which the regularization parameter is driven to zero;
a modular implementation that is suited for large-scale problems, allows multiple iterative and direct subproblem solvers, and accommodates exact, limited-memory quasi-Newton, or other Hessian approximations;
a variant for nonlinear least squares named R2NLS that may be viewed as an implementation of the method of Levenberg [34 ] and Marquardt [40 ] , to which our global convergence and complexity results apply, and our local convergence analysis applies when ∑ i f i ( x k ) ∇ 2 f i ( x k ) → 0 \sum_i f_i(x_k)\nabla^2 f_i(x_k) \to0 ∑ i f i ( x k ) ∇ 2 f i ( x k ) → 0 , in particular for zero-residual problems or when the residuals are linear;
a thorough numerical study, on unconstrained and nonlinear least-squares problems from the CUTEst collection, of the choices that our analysis leaves open: the treatment of nonpositive curvature, the subproblem solver, the update of the regularization parameter, and direct versus iterative subproblem solves, together with a comparison with a trust-region method.
Our current implementation supports the following iterative solvers: the truncated conjugate-gradient method of Dembo and Steihaug [12 ] , the truncated conjugate residuals method of Dahito and Orban [11 ] , the truncated minimum residual method of Liu and Roosta [38 ] , where truncated refers to the identification of directions of nonpositive curvature. R2N currently supports the direct solvers MA57 [18 ] and MA97 [29 ] . When using limited-memory BFGS model Hessians, we also support the direct solver of Erway et al. [20 ] .
One of our objectives is to settle, through a thorough numerical study, the choices that our analysis leaves open. We use exact second derivatives, limited-memory BFGS approximations and Gauss-Newton models, and compare R2N with the trust-region solver Trunk using the same model, subproblem solver and stopping test. Although R2N also supports MA97, only MA57 results are reported. Exploiting nonpositive curvature with the Armijo-Goldstein line search is more efficient and more robust than falling back on the Cauchy step, and comparable to the other strategies we consider. MINRES-QLP is more efficient than truncated CG, and driving σ k \sigma_k σ k to zero near a solution improves efficiency without affecting robustness. Exact subproblem solves, whether by sparse factorization or by the solver of Erway et al. [20 ] , bring no consistent advantage over MINRES-QLP. With exact second derivatives, R2N solves slightly more problems than Trunk and requires fewer objective and gradient evaluations, while Trunk requires fewer Hessian-vector products. With convex models, Trunk performs as well or better.
Li et al. [35 ] , Li and Li [36 ] and Polyak [51 ] study the properties of the regularized Newton method under the assumption that f f f is convex. Ueda and Yamashita [53 ] further study the properties of a regularized Newton method with Armijo line search for nonconvex f f f under the assumption that f f f is C 2 C^2 C 2 . At each iteration, they set the regularization parameter based on the smallest eigenvalue of the Hessian and the gradient norm, thereby ensuring that subproblems are convex. They establish a O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) complexity bound if ∇ 2 f \nabla^2 f ∇ 2 f is Lipschitz continuous and superlinear convergence under a local error bound condition. Under similar assumptions, Ueda and Yamashita [54 ] replace the Armijo line search with a parameter update that plays a role in the definition of the regularization parameter. They establish a complexity bound in O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) , but do not show that it is sharp. Zhang and Ni [55 ] combine a similar strategy with a non-monotone Armijo line search.
Kanzow and Steck [30 ] study a method similar to ours but rely on limited-memory quasi-Newton methods and variants of the direct method developed by Erway et al. [20 ] to solve the first-order stationarity conditions of the model exactly. They assume that model Hessians remain bounded, and do not exploit nonpositive-curvature directions, but merely increase the regularization parameter when they occur.
Gratton et al. [27 ] propose a regularized Newton method for nonconvex f f f in which the shift has the form σ k ∥ ∇ f ( x k ) ∥ \sqrt{\sigma_k}\lVert\nabla f(x_k)\rVert σ k ∥ ∇ f ( x k )∥ , and σ k \sigma_k σ k is updated as in R2N. When the smallest eigenvalue of the Hessian, possibly restricted to a Krylov subspace, is sufficiently negative, they take a step of prescribed length along an approximate eigenvector, and otherwise absorb the negative curvature into the shift. They establish a bound in O ( ∣ log ε ∣ ε − 3 / 2 ) O(\lvert\log\varepsilon\rvert\varepsilon^{-3/2}) O (∣ log ε ∣ ε − 3/2 ) under Lipschitz continuity of the exact Hessian. By contrast, R2N uses σ k \sigma_k σ k itself as the shift, requires no eigenvalue estimate, exploits any direction of nonpositive curvature detected by the subproblem solver in a line search, and allows quasi-Newton models.
Sharp complexity bounds for the regularized (quasi-)Newton method were first established by Diouane et al. [15 ] , even when model Hessians, whether they are exact or not, are allowed to grow unbounded. Because their focus is on nonsmooth problems, they solve subproblems with a first-order method and have no concept of curvature. We build upon their convergence analysis, which is conducted under the sole assumption that f ∈ C 1 f \in C^1 f ∈ C 1 , and discuss multiple subproblem solvers. We also benefit from their complexity analysis, and supplement it to emphasize the contribution of nonpositive-curvature steps to the overall complexity bound. Indeed, contrary to the references above, we allow models to be nonconvex, and we exploit nonpositive curvature wherever possible, in a manner similar to trust-region methods. Our results correct several results by Liu and Roosta [39 ] , who study a regularized Newton method with line search and MINRES as a subproblem solver, and claim an overall O ( ε − 3 / 2 ) O(\varepsilon^{-3/2}) O ( ε − 3/2 ) complexity bound.
Organization of the Paper
The paper is organized as follows. In § 3 , we review quasi-Newton and regularization methods. In § 4 , we introduce the models and the Cauchy decrease condition, and state Algorithm R2N in § 5 . In § 6 , we describe subproblem solvers that satisfy the Cauchy decrease condition, and our treatment of nonpositive curvature. We establish global convergence in § 7 . In § 8 , we derive the structured complexity bound, and show in § 9 and § 10 that its two terms are attained, at least when exact derivatives are used. In § 11 , we present a variant with fast local convergence, and specialize R2N to nonlinear least squares § 12 . Finally, we describe our implementation and reports numerical experiments § 13 .
Notation
We use uppercase and lowercase Latin letters for matrices and vectors, respectively. Lowercase Greek letters denote scalars. The Euclidean norm of vector x x x is denoted ∥ x ∥ \lVert x\rVert ∥ x ∥ . Accordingly, the spectral norm of matrix A A A is ∥ A ∥ \lVert A\rVert ∥ A ∥ . Sets are denoted by uppercase calligraphic letters such as S \mathcal{S} S , and their cardinality by ∣ S ∣ \lvert\mathcal{S}\rvert ∣ S ∣ . A subscript k k k denotes an index or iteration number. For positive sequences { α k } \{\alpha_k\} { α k } and { β k } \{\beta_k\} { β k } , α k = O ( β k ) \alpha_k = O(\beta_k) α k = O ( β k ) means that there exists a constant C > 0 C > 0 C > 0 such that α k ≤ C β k \alpha_k \le C\beta_k α k ≤ C β k for all k k k large enough, and α k = o ( β k ) \alpha_k = o(\beta_k) α k = o ( β k ) means that lim k → ∞ α k / β k = 0 \lim_{k\to\infty}\alpha_k/\beta_k = 0 lim k → ∞ α k / β k = 0 . If A A A is symmetric, A ≻ 0 A \succ0 A ≻ 0 and A ⪰ 0 A \succeq0 A ⪰ 0 mean that it is positive definite and positive semi-definite, respectively.
Background
Traditional quasi-Newton methods for unconstrained optimization compute steps s k s_k s k that approximately minimize a local quadratic model of the objective about the current iterate x k x_k x k [13 ] . The model Hessian B k = B k T B_k = B_k^{\mathrm{T}} B k = B k T is typically updated using first-order information to satisfy the secant equation B k s k − 1 = y k − 1 B_ks_{k-1} = y_{k-1} B k s k − 1 = y k − 1 , where y k − 1 ≔ ∇ f ( x k ) − ∇ f ( x k − 1 ) y_{k-1} \coloneqq\nabla f(x_k) - \nabla f(x_{k-1}) y k − 1 : = ∇ f ( x k ) − ∇ f ( x k − 1 ) , and x k = x k − 1 + s k − 1 x_k = x_{k-1} + s_{k-1} x k = x k − 1 + s k − 1 [13 ] . In a standard line-search framework, the step s k s_k s k is computed by solving B k s k = − ∇ f ( x k ) B_ks_k = -\nabla f(x_k) B k s k = − ∇ f ( x k ) , either exactly or inexactly. A step length α k > 0 \alpha_k > 0 α k > 0 is then computed to satisfy the Armijo condition, which requires s k s_k s k to be a direction of sufficient descent. While it is not strictly necessary for B k B_k B k to be positive definite for s k s_k s k to be a descent direction, as is the case, for example, with the Symmetric Rank-1 (SR1) update, imposing B k ≻ 0 B_k \succ0 B k ≻ 0 is a standard way to guarantee descent. However, when the underlying objective is highly non-convex, maintaining positive-definite approximations can lead to poor performance.
Trust-region methods are able to exploit directions of nonpositive curvature naturally by imposing a bound ∥ s ∥ ≤ Δ k \lVert s\rVert\le\Delta_k ∥ s ∥ ≤ Δ k [10 ] . Rather than imposing a hard constraint on the step norm, quadratic regularization methods augment the quadratic model with an adaptive penalty term 1 2 σ k ∥ s ∥ 2 \frac{1}{2}\sigma_k\lVert s\rVert^2 2 1 σ k ∥ s ∥ 2 , where σ k > 0 \sigma_k > 0 σ k > 0 . The step s k s_k s k is then computed as an approximate solution to the shifted system
( B k + σ k I ) s k = − ∇ f ( x k ) . (2) (B_k + \sigma_k I)s_k = -\nabla f(x_k). \tag*{(2)} ( B k + σ k I ) s k = − ∇ f ( x k ) . (2)
Curiously, this regularized quasi-Newton approach is not mentioned in Cartis et al. [8 ] , although it has received recent attention in the literature, for smooth [30 , 35 , 36 , 53 , 54 ] , and nonsmooth optimization [15 ] . If σ k \sigma_k σ k is large enough, B k + σ k I ≻ 0 B_k + \sigma_k I \succ0 B k + σ k I ≻ 0 , and (2) admits a unique minimizer. However, maintaining a uniformly large σ k \sigma_k σ k artificially restricts the step size and impedes fast local convergence. The algorithm must therefore dynamically adjust σ k \sigma_k σ k based on the predictive quality of the model, while gracefully handling iterations where B k + σ k I ⊁ 0 B_k + \sigma_k I \not\succ0 B k + σ k I ≻ 0 . That can be achieved by detecting and exploiting directions of nonpositive curvature—see the definition below.
Models and Cauchy Decrease
We consider two types of models of f f f about the current iterate x k x_k x k . The first, linear, model is defined as the first-order expansion of f f f about x k x_k x k :
φ c p ( s ; x k ) : = f ( x k ) + ∇ f ( x k ) T s . (3) \varphi_{\mathrm{cp}}(s;x_k) := f(x_k) + \nabla f(x_k)^T s. \tag*{(3)} φ cp ( s ; x k ) := f ( x k ) + ∇ f ( x k ) T s . (3)
The Cauchy point at iteration k k k , denoted s k , c p ( α k , c p ) s_{k,\mathrm{cp}}(\alpha_{k,\mathrm{cp}}) s k , cp ( α k , cp ) , is defined as an appropriate multiple α k , c p > 0 \alpha_{k,\mathrm{cp}} > 0 α k , cp > 0 of − ∇ f ( x k ) -\nabla f(x_k) − ∇ f ( x k ) . We intentionally leave some freedom in the choice of α k , c p \alpha_{k,\mathrm{cp}} α k , cp . In our context, inspired from [15 ] , it is convenient to view s k , c p ( α k , c p ) : = − α k , c p ∇ f ( x k ) s_{k,\mathrm{cp}}(\alpha_{k,\mathrm{cp}}) := -\alpha_{k,\mathrm{cp}}\nabla f(x_k) s k , cp ( α k , cp ) := − α k , cp ∇ f ( x k ) as the unique minimizer of
m ( s ; x k , α k , c p ) : = φ c p ( s ; x k ) + 1 2 α k , c p − 1 ∥ s ∥ 2 . (4) m(s;x_k,\alpha_{k,\mathrm{cp}}) := \varphi_{\mathrm{cp}}(s;x_k) + \frac{1}{2}\alpha_{k,\mathrm{cp}}^{-1}\lVert s\rVert^2. \tag*{(4)} m ( s ; x k , α k , cp ) := φ cp ( s ; x k ) + 2 1 α k , cp − 1 ∥ s ∥ 2 . (4)
We denote the decrease in φ c p ( ⋅ ; x k ) \varphi_{\mathrm{cp}}(\cdot;x_k) φ cp ( ⋅ ; x k ) achieved by s k , c p ( α k , c p ) s_{k,\mathrm{cp}}(\alpha_{k,\mathrm{cp}}) s k , cp ( α k , cp ) as
ξ c p ( x k , α k , c p ) : = φ c p ( 0 ; x k ) − φ c p ( s k , c p ; x k ) = α k , c p ∥ ∇ f ( x k ) ∥ 2 = α k , c p − 1 ∥ s k , c p ( α k , c p ) ∥ 2 > 0 , (5) \begin{aligned}
\xi_{\mathrm{cp}}(x_k,\alpha_{k,\mathrm{cp}}) &:= \varphi_{\mathrm{cp}}(0;x_k)-\varphi_{\mathrm{cp}}(s_{k,\mathrm{cp}};x_k) \\
&= \alpha_{k,\mathrm{cp}}\lVert\nabla f(x_k)\rVert^2 = \alpha_{k,\mathrm{cp}}^{-1}\lVert s_{k,\mathrm{cp}}(\alpha_{k,\mathrm{cp}})\rVert^2 > 0, \tag*{(5)}
\end{aligned} ξ cp ( x k , α k , cp ) := φ cp ( 0 ; x k ) − φ cp ( s k , cp ; x k ) = α k , cp ∥ ∇ f ( x k ) ∥ 2 = α k , cp − 1 ∥ s k , cp ( α k , cp ) ∥ 2 > 0 , (5)
where the final inequality holds as long as ∇ f ( x k ) ≠ 0 \nabla f(x_k) \ne0 ∇ f ( x k ) = 0 .
The second, quadratic, model is
φ ( s ; x k ) : = φ c p ( s ; x k ) + 1 2 s T B k s , (6) \varphi(s;x_k) := \varphi_{\mathrm{cp}}(s;x_k) + \frac{1}{2}s^T B_k s, \tag*{(6)} φ ( s ; x k ) := φ cp ( s ; x k ) + 2 1 s T B k s , (6)
where B k = B k T ∈ R n × n B_k = B_k^T \in\mathbb{R}^{n\times n} B k = B k T ∈ R n × n may be ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇ 2 f ( x k ) if the latter is well-defined, available, and can be obtained at reasonable expense, or an approximation to it. Model (6) serves to compute a step s k s_k s k at iteration k k k as an approximate minimizer of
m ( s ; x k , σ k ) : = φ ( s ; x k ) + 1 2 σ k ∥ s ∥ 2 , (7) m(s;x_k,\sigma_k) := \varphi(s;x_k) + \frac{1}{2}\sigma_k\lVert s\rVert^2, \tag*{(7)} m ( s ; x k , σ k ) := φ ( s ; x k ) + 2 1 σ k ∥ s ∥ 2 , (7)
where σ k > 0 \sigma_k > 0 σ k > 0 is a regularization parameter adjusted at each iteration, and whose role is to drive convergence. The step s k s_k s k need not minimize m ( ⋅ ; x k , σ k ) m(\cdot;x_k,\sigma_k) m ( ⋅ ; x k , σ k ) accurately, but should achieve sufficient decrease , in the sense that
ξ ( x k , σ k ) : = φ ( 0 ; x k ) − φ ( s k ; x k ) (8) \xi(x_k,\sigma_k) := \varphi(0;x_k)-\varphi(s_k;x_k) \tag*{(8)} ξ ( x k , σ k ) := φ ( 0 ; x k ) − φ ( s k ; x k ) (8)
should satisfy
ξ ( x k , σ k ) ≥ τ ξ c p ( x k , ν k ) for all k ∈ N , where 0 < τ ≤ 1 , (9) \xi(x_k,\sigma_k) \ge\tau\xi_{\mathrm{cp}}(x_k,\nu_k) \quad\text{for all } k \in\mathbb{N}, \qquad\text{where } 0 < \tau\le1, \tag*{(9)} ξ ( x k , σ k ) ≥ τ ξ cp ( x k , ν k ) for all k ∈ N , where 0 < τ ≤ 1 , (9)
where
ν k : = θ 1 ∥ B k ∥ + σ k , ( 0 < θ 1 < 1 ) . (10) \nu_k := \frac{\theta_1}{\lVert B_k\rVert+\sigma_k}, \qquad(0 < \theta_1 < 1). \tag*{(10)} ν k := ∥ B k ∥ + σ k θ 1 , ( 0 < θ 1 < 1 ) . (10)
Diouane et al. [15 ] use the special value α k , c p = ν k \alpha_{k,\mathrm{cp}} = \nu_k α k , cp = ν k to define the Cauchy point because s k , c p ( ν k ) s_{k,\mathrm{cp}}(\nu_k) s k , cp ( ν k ) is guaranteed to induce a decrease in (7) as well. Our algorithm below allows to do the same, although ν k \nu_k ν k can be overly restrictive in the smooth context. Thus, we provide other options.
Importantly, s k , c p ( α k , c p ) s_{k,\mathrm{cp}}(\alpha_{k,\mathrm{cp}}) s k , cp ( α k , cp ) need not necessarily be computed during the iterations. Instead, we will establish that the procedures used to compute s k s_k s k satisfy (9) under certain assumptions, and we only compute s k , c p ( α k , c p ) s_{k,\mathrm{cp}}(\alpha_{k,\mathrm{cp}}) s k , cp ( α k , cp ) when those assumptions fail.
The next result parallels [15 Proposition 3.7] but allows for a step s k s_k s k that achieves a fraction of the decrease in m ( ⋅ ; x k , σ k ) m(\cdot;x_k,\sigma_k) m ( ⋅ ; x k , σ k ) induced by s k , c p ( ν k ) s_{k,\mathrm{cp}}(\nu_k) s k , cp ( ν k ) .
Proposition 1 At a general iterate x k ∈ R n x_k \in\mathbb{R}^n x k ∈ R n , let σ k > 0 \sigma_k > 0 σ k > 0 be the regularization parameter, B k = B k T B_k = B_k^T B k = B k T be the model Hessian, and s k , c p ( ν k ) : = − ν k ∇ f ( x k ) s_{k,\mathrm{cp}}(\nu_k) := -\nu_k \nabla f(x_k) s k , cp ( ν k ) := − ν k ∇ f ( x k ) . Assume that there exists τ 0 > 0 \tau_0 > 0 τ 0 > 0 such that s k s_k s k satisfies
m ( 0 ; x k , σ k ) − m ( s k ; x k , σ k ) ≥ τ 0 ( m ( 0 ; x k , σ k ) − m ( s k , c p ( ν k ) ; x k , σ k ) ) . (11) m(0;x_k,\sigma_k)-m(s_k;x_k,\sigma_k) \ge\tau_0\left(m(0;x_k,\sigma_k)-m(s_{k,\mathrm{cp}}(\nu_k);x_k,\sigma_k)\right). \tag*{(11)} m ( 0 ; x k , σ k ) − m ( s k ; x k , σ k ) ≥ τ 0 ( m ( 0 ; x k , σ k ) − m ( s k , cp ( ν k ) ; x k , σ k ) ) . (11) Then, (9) holds with τ : = min ( 1 , τ 0 ( 1 − 1 2 θ 1 ) ) \tau:= \min(1,\tau_0(1-\frac{1}{2}\theta_1)) τ := min ( 1 , τ 0 ( 1 − 2 1 θ 1 )) .
Proof. We combine (5) , (7) , (8) , (10) , and our assumptions to obtain
m ( 0 ; x k , σ k ) − m ( s k ; x k , σ k ) = ξ ( x k , σ k ) − 1 2 σ k ∥ s k ∥ 2 ≥ τ 0 ( m ( 0 ; x k , σ k ) − m ( s k , c p ( ν k ) ; x k , σ k ) ) = τ 0 ( ξ c p ( x k , ν k ) − 1 2 s k , c p ( ν k ) T ( B k + σ k I ) s k , c p ( ν k ) ) ≥ τ 0 ( ξ c p ( x k , ν k ) − 1 2 ( ∥ B k ∥ + σ k ) ∥ s k , c p ( ν k ) ∥ 2 ) = τ 0 ( ξ c p ( x k , ν k ) − 1 2 ( ∥ B k ∥ + σ k ) ν k ξ c p ( x k , ν k ) ) = τ 0 ( 1 − 1 2 θ 1 ) ξ c p ( x k , ν k ) ≥ τ ξ c p ( x k , ν k ) . \begin{aligned}
m(0;x_k,\sigma_k)-m(s_k;x_k,\sigma_k) &= \xi(x_k,\sigma_k)-\frac{1}{2}\sigma_k\lVert s_k\rVert^2 \\
&\ge\tau_0\left(m(0;x_k,\sigma_k)-m(s_{k,\mathrm{cp}}(\nu_k);x_k,\sigma_k)\right) \\
&= \tau_0\left(\xi_{\mathrm{cp}}(x_k,\nu_k)-\frac{1}{2}s_{k,\mathrm{cp}}(\nu_k)^T(B_k+\sigma_k I)s_{k,\mathrm{cp}}(\nu_k)\right) \\
&\ge\tau_0\left(\xi_{\mathrm{cp}}(x_k,\nu_k)-\frac{1}{2}(\lVert B_k\rVert+\sigma_k)\lVert s_{k,\mathrm{cp}}(\nu_k)\rVert^2\right) \\
&= \tau_0\left(\xi_{\mathrm{cp}}(x_k,\nu_k)-\frac{1}{2}(\lVert B_k\rVert+\sigma_k)\nu_k\xi_{\mathrm{cp}}(x_k,\nu_k)\right) \\
&= \tau_0\left(1-\frac{1}{2}\theta_1\right)\xi_{\mathrm{cp}}(x_k,\nu_k) \\
&\ge\tau\xi_{\mathrm{cp}}(x_k,\nu_k).
\end{aligned} m ( 0 ; x k , σ k ) − m ( s k ; x k , σ k ) = ξ ( x k , σ k ) − 2 1 σ k ∥ s k ∥ 2 ≥ τ 0 ( m ( 0 ; x k , σ k ) − m ( s k , cp ( ν k ) ; x k , σ k ) ) = τ 0 ( ξ cp ( x k , ν k ) − 2 1 s k , cp ( ν k ) T ( B k + σ k I ) s k , cp ( ν k ) ) ≥ τ 0 ( ξ cp ( x k , ν k ) − 2 1 (∥ B k ∥ + σ k ) ∥ s k , cp ( ν k ) ∥ 2 ) = τ 0 ( ξ cp ( x k , ν k ) − 2 1 (∥ B k ∥ + σ k ) ν k ξ cp ( x k , ν k ) ) = τ 0 ( 1 − 2 1 θ 1 ) ξ cp ( x k , ν k ) ≥ τ ξ cp ( x k , ν k ) .
where τ \tau τ is as defined in the statement of the present result. We combine the first and last lines above to obtain ξ ( x k , σ k ) ≥ τ ξ c p ( x k , ν k ) + 1 2 σ k ∥ s k ∥ 2 ≥ τ ξ c p ( x k , ν k ) \xi(x_k,\sigma_k) \ge\tau\xi_{\mathrm{cp}}(x_k,\nu_k) + \frac{1}{2}\sigma_k\lVert s_k\rVert^2 \ge\tau\xi_{\mathrm{cp}}(x_k,\nu_k) ξ ( x k , σ k ) ≥ τ ξ cp ( x k , ν k ) + 2 1 σ k ∥ s k ∥ 2 ≥ τ ξ cp ( x k , ν k ) .
In § 6 , we review several strategies to compute a step that satisfies the assumption of Proposition 1. First, we state a general algorithmic framework in the next section.
Algorithm Statement
Our algorithm follows that of [15 ] with the differences that we need not systematically compute a Cauchy point in the outer loop, and that we have explicit treatment of directions of nonpositive curvature. The latter is also a major difference with the algorithms of [39 ] and [30 ] . Specifically, when such a direction is detected during the step computation, we perform an Armijo-Goldstein line search in order to ensure controlled decrease along said direction. The Armijo-Goldstein line search is the key mechanism that allows us to quantify the decrease achieved along a nonpositive-curvature direction in terms of the user-defined stopping tolerance—see Theorem 2. First, we assume that steps are generated along gradient-related directions .
Definition 1 (Gradient-Related Direction) We call d ∈ R n d \in\mathbb{R}^n d ∈ R n a gradient-related direction at x k x_k x k if there exist κ 1 > 0 \kappa_1 > 0 κ 1 > 0 and κ 2 > 0 \kappa_2 > 0 κ 2 > 0 , independent of k k k , such that
(1). ∇ f ( x k ) T d ≤ − κ 1 ∥ ∇ f ( x k ) ∥ 2 \nabla f(x_k)^T d \le-\kappa_1\lVert\nabla f(x_k)\rVert^2 ∇ f ( x k ) T d ≤ − κ 1 ∥ ∇ f ( x k ) ∥ 2 , and
(2). ∥ d ∥ ≤ κ 2 ∥ ∇ f ( x k ) ∥ \lVert d\rVert\le\kappa_2\lVert\nabla f(x_k)\rVert ∥ d ∥ ≤ κ 2 ∥ ∇ f ( x k )∥ .
If d k ∈ R n d_k \in\mathbb{R}^n d k ∈ R n is a gradient-related direction, the first part of Definition 1 and the Cauchy-Schwarz inequality yield ∥ ∇ f ( x k ) ∥ ∥ d k ∥ ≥ ∣ ∇ f ( x k ) T d k ∣ = − ∇ f ( x k ) T d k ≥ κ 1 ∥ ∇ f ( x k ) ∥ 2 \lVert\nabla f(x_k)\rVert\lVert d_k\rVert\ge\lvert\nabla f(x_k)^T d_k\rvert= -\nabla f(x_k)^T d_k \ge\kappa_1\lVert\nabla f(x_k)\rVert^2 ∥ ∇ f ( x k )∥ ∥ d k ∥ ≥ ∣ ∇ f ( x k ) T d k ∣ = − ∇ f ( x k ) T d k ≥ κ 1 ∥ ∇ f ( x k ) ∥ 2 . Thus,
∥ d k ∥ ≥ κ 1 ∥ ∇ f ( x k ) ∥ . (12) \lVert d_k\rVert\ge\kappa_1\lVert\nabla f(x_k)\rVert. \tag*{(12)} ∥ d k ∥ ≥ κ 1 ∥ ∇ f ( x k )∥ . (12)
Similarly, the second part of Definition 1 and the Cauchy-Schwarz inequality yield − ∇ f ( x k ) T d k ≤ ∥ ∇ f ( x k ) ∥ ∥ d k ∥ ≤ κ 2 ∥ ∇ f ( x k ) ∥ 2 -\nabla f(x_k)^T d_k \le\lVert\nabla f(x_k)\rVert\lVert d_k\rVert\le\kappa_2\lVert\nabla f(x_k)\rVert^2 − ∇ f ( x k ) T d k ≤ ∥ ∇ f ( x k )∥ ∥ d k ∥ ≤ κ 2 ∥ ∇ f ( x k ) ∥ 2 . Thus, we also have
∇ f ( x k ) T d k ≥ − κ 2 ∥ ∇ f ( x k ) ∥ 2 . (13) \nabla f(x_k)^T d_k \ge-\kappa_2\lVert\nabla f(x_k)\rVert^2. \tag*{(13)} ∇ f ( x k ) T d k ≥ − κ 2 ∥ ∇ f ( x k ) ∥ 2 . (13)
Definition 2 (Non-Positive Curvature Direction) We call d k ∈ R n d_k \in\mathbb{R}^n d k ∈ R n a direction of nonpositive curvature at x k x_k x k if it is gradient-related and d k T ( B k + σ k I ) d k ≤ 0 d_k^T(B_k+\sigma_k I)d_k \le0 d k T ( B k + σ k I ) d k ≤ 0 .
We formally state R2N as Algorithm 4.1 . Our formulation uses a constant σ min \sigma_{\min} σ m i n that may be chosen to be zero, or a positive value. This freedom is used to highlight the convergence guarantees that σ min > 0 \sigma_{\min}>0 σ m i n > 0 affords and the extra assumptions required to provide similar guarantees when σ min = 0 \sigma_{\min}=0 σ m i n = 0 . In § 11 , we require σ min = 0 \sigma_{\min}=0 σ m i n = 0 to establish superlinear convergence near an isolated local minimizer.
Algorithm 4.1 R2N: A modified Quasi-Newton method.
Choose constants σ min ≥ 0 \sigma_{\min}\ge0 σ m i n ≥ 0 , θ 2 > 1 \theta_2>1 θ 2 > 1 , 0 < ρ L < ρ U < 1 0<\rho_L<\rho_U<1 0 < ρ L < ρ U < 1 , 0 < η 1 ≤ η 2 < 1 0<\eta_1\le\eta_2<1 0 < η 1 ≤ η 2 < 1 and 0 < γ 3 ≤ 1 < γ 1 ≤ γ 2 0<\gamma_3\le1<\gamma_1\le\gamma_2 0 < γ 3 ≤ 1 < γ 1 ≤ γ 2 .
Choose x 0 ∈ R n x_0\in\mathbb{R}^n x 0 ∈ R n , σ 0 ≥ σ min \sigma_0\ge\sigma_{\min} σ 0 ≥ σ m i n .
for k = 0 , 1 , … k=0,1,\ldots k = 0 , 1 , … do
Choose B k = B k T ∈ R n × n B_k=B_k^T\in\mathbb{R}^{n\times n} B k = B k T ∈ R n × n
Compute Cauchy step s k , c p s_{k,\mathrm{cp}} s k , cp using Algorithm 4.2
Compute a step s k s_k s k that satisfies {(11)} or identify a direction of nonpositive curvature d k d_k d k at x k x_k x k .
if a direction of nonpositive curvature d k d_k d k at x k x_k x k was identified then
Compute α k > 0 \alpha_k>0 α k > 0 such that perform Armijo-Goldstein line search
f ( x k ) + ρ U α k ∇ f ( x k ) T d k ≤ f ( x k + α k d k ) ≤ f ( x k ) + ρ L α k ∇ f ( x k ) T d k . (14) f(x_k)+\rho_U\alpha_k\nabla f(x_k)^T d_k\le f(x_k+\alpha_kd_k)\le f(x_k)+\rho_L\alpha_k\nabla f(x_k)^T d_k. \tag*{(14)} f ( x k ) + ρ U α k ∇ f ( x k ) T d k ≤ f ( x k + α k d k ) ≤ f ( x k ) + ρ L α k ∇ f ( x k ) T d k . (14) Reset s k = α k d k s_k=\alpha_kd_k s k = α k d k .
end if
if ∥ s k ∥ > θ 2 ∥ s k , c p ∥ \lVert s_k\rVert>\theta_2\lVert s_{k,\mathrm{cp}}\rVert ∥ s k ∥ > θ 2 ∥ s k , cp ∥ then
reset s k = s k , c p s_k=s_{k,\mathrm{cp}} s k = s k , cp .
end if
Compute the ratio
ρ k : = f ( x k ) − f ( x k + s k ) φ ( 0 ; x k ) − φ ( s k ; x k ) . \rho_k:=\frac{f(x_k)-f(x_k+s_k)}{\varphi(0;x_k)-\varphi(s_k;x_k)}. ρ k := φ ( 0 ; x k ) − φ ( s k ; x k ) f ( x k ) − f ( x k + s k ) . if ρ k ≥ η 1 \rho_k\ge\eta_1 ρ k ≥ η 1 then
set x k + 1 = x k + s k x_{k+1}=x_k+s_k x k + 1 = x k + s k .
else
set x k + 1 = x k x_{k+1}=x_k x k + 1 = x k .
end if
Update the regularization parameter according to
σ k + 1 ∈ { [ γ 3 σ k , σ k ] if ρ k ≥ η 2 , very successful iteration , [ σ k , γ 1 σ k ] if η 1 ≤ ρ k < η 2 , successful iteration , [ γ 1 σ k , γ 2 σ k ] if ρ k < η 1 . unsuccessful iteration \sigma_{k+1}\in
\begin{cases}
[\gamma_3\sigma_k,\sigma_k] & \text{if }\rho_k\ge\eta_2,\quad\text{very successful iteration},\\
[\sigma_k,\gamma_1\sigma_k] & \text{if }\eta_1\le\rho_k<\eta_2,\quad\text{successful iteration},\\
[\gamma_1\sigma_k,\gamma_2\sigma_k] & \text{if }\rho_k<\eta_1.\quad\text{unsuccessful iteration}
\end{cases} σ k + 1 ∈ ⎩ ⎨ ⎧ [ γ 3 σ k , σ k ] [ σ k , γ 1 σ k ] [ γ 1 σ k , γ 2 σ k ] if ρ k ≥ η 2 , very successful iteration , if η 1 ≤ ρ k < η 2 , successful iteration , if ρ k < η 1 . unsuccessful iteration Reset σ k + 1 = max ( σ k + 1 , σ min ) \sigma_{k+1}=\max(\sigma_{k+1},\sigma_{\min}) σ k + 1 = max ( σ k + 1 , σ m i n ) .
end for
Algorithm 4.2 R2N: Calculation of Cauchy Step.
Require: Gradient ∇ f ( x k ) \nabla f(x_k) ∇ f ( x k ) , model Hessian B k = B k T B_k = B_k^T B k = B k T , regularization parameter σ k \sigma_k σ k .
Require: Parameters 0 < θ 1 < 1 0 < \theta_1 < 1 0 < θ 1 < 1 .
Compute γ k \gamma_k γ k according to (16) .
if γ k ≤ 0 \gamma_k \le0 γ k ≤ 0 then
Set α k , c p = θ 1 / ( ∥ B k ∥ + σ k ) \alpha_{k,\mathrm{cp}} = \theta_1/(\lVert B_k\rVert+ \sigma_k) α k , cp = θ 1 / (∥ B k ∥ + σ k ) .
else
Set α k , c p = α ˉ k , c p = 1 / γ k \alpha_{k,\mathrm{cp}} = \bar{\alpha}_{k,\mathrm{cp}} = 1/\gamma_k α k , cp = α ˉ k , cp = 1/ γ k .
end if
return s k , c p = − α k , c p ∇ f ( x k ) s_{k,\mathrm{cp}} = -\alpha_{k,\mathrm{cp}}\nabla f(x_k) s k , cp = − α k , cp ∇ f ( x k )
In Algorithm 4.2, the computation of ∥ B k ∥ \lVert B_k\rVert ∥ B k ∥ at Algorithm 4.2 may be costly if operator-vector products with B k B_k B k are expensive. Firstly, although we use the spectral norm by convention, any other norm may be used in its place, as that will only affect constants in the analysis. Secondly, Diouane et al. [15 ] explain that computing β k ≥ μ B ∥ B k ∥ \beta_k \ge\mu_B\lVert B_k\rVert β k ≥ μ B ∥ B k ∥ for 0 < μ B ≤ 1 0 < \mu_B \le1 0 < μ B ≤ 1 and setting ν k : = θ 1 / ( β k + σ k ) \nu_k := \theta_1/(\beta_k+\sigma_k) ν k := θ 1 / ( β k + σ k ) with θ 1 < μ B \theta_1 < \mu_B θ 1 < μ B continues to ensure that our convergence and complexity results hold unchanged. Estimating ∥ B k ∥ \lVert B_k\rVert ∥ B k ∥ with an iterative method only requires operator-vector products, and is thus feasible when the latter are cheap, e.g., when B k B_k B k is a limited-memory quasi-Newton approximation.
When operator-vector products are expensive, an alternative to s k , c p ( ν k ) s_{k,\mathrm{cp}}(\nu_k) s k , cp ( ν k ) is to define the Cauchy step as − α ˉ k ∇ f ( x k ) -\bar{\alpha}_k\nabla f(x_k) − α ˉ k ∇ f ( x k ) where α ˉ k \bar{\alpha}_k α ˉ k minimizes ψ k ( α ) : = m ( − α ∇ f ( x k ) ; x k , σ k ) \psi_k(\alpha) := m(-\alpha\nabla f(x_k);x_k,\sigma_k) ψ k ( α ) := m ( − α ∇ f ( x k ) ; x k , σ k ) when it is bounded below. Specifically,
α ˉ k , c p = 1 / γ k , (15) \bar{\alpha}_{k,\mathrm{cp}} = 1/\gamma_k, \tag*{(15)} α ˉ k , cp = 1/ γ k , (15)
whenever γ k > 0 \gamma_k > 0 γ k > 0 , where
γ k : = ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ∥ ∇ f ( x k ) ∥ 2 , (16) \gamma_k := \frac{\nabla f(x_k)^T(B_k+\sigma_k I)\nabla f(x_k)}{\lVert\nabla f(x_k)\rVert^2}, \tag*{(16)} γ k := ∥ ∇ f ( x k ) ∥ 2 ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) , (16)
is the model curvature along the gradient direction. When γ k > 0 \gamma_k > 0 γ k > 0 , ψ k \psi_k ψ k is strictly convex, ψ k ( 0 ) = f ( x k ) = ψ k ( α k , max ) \psi_k(0)=f(x_k)=\psi_k(\alpha_{k,\max}) ψ k ( 0 ) = f ( x k ) = ψ k ( α k , m a x ) , where α k , max : = 2 / γ k = 2 α ˉ k , c p \alpha_{k,\max}:=2/\gamma_k=2\bar{\alpha}_{k,\mathrm{cp}} α k , m a x := 2/ γ k = 2 α ˉ k , cp , and ψ k ( α ) < f ( x k ) \psi_k(\alpha)<f(x_k) ψ k ( α ) < f ( x k ) for all 0 < α < α k , max 0<\alpha<\alpha_{k,\max} 0 < α < α k , m a x . Hence, (11) holds for s k = s k , c p ( α k ) s_k=s_{k,\mathrm{cp}}(\alpha_k) s k = s k , cp ( α k ) whenever γ k > 0 \gamma_k>0 γ k > 0 and there is 0 < δ < 1 0<\delta<1 0 < δ < 1 independent of k k k such that ( 1 − δ ) α ˉ k , c p ≤ α k ≤ ( 1 + δ ) α ˉ k , c p (1-\delta)\bar{\alpha}_{k,\mathrm{cp}}\le\alpha_k\le(1+\delta)\bar{\alpha}_{k,\mathrm{cp}} ( 1 − δ ) α ˉ k , cp ≤ α k ≤ ( 1 + δ ) α ˉ k , cp . In that situation, α k \alpha_k α k may be used in place of ν k \nu_k ν k everywhere, or when convenient. Indeed, such α k \alpha_k α k is guaranteed to result in a fraction of the optimal decrease in ψ \psi ψ , hence a fraction of ψ ( 0 ) − ψ ( ν k ) \psi(0)-\psi(\nu_k) ψ ( 0 ) − ψ ( ν k ) . Continuing further, any s k s_k s k that results in a fraction of the decrease ψ ( 0 ) − ψ ( α k ) \psi(0)-\psi(\alpha_k) ψ ( 0 ) − ψ ( α k ) also satisfies (11) .
Treatment of directions of nonpositive curvature does not appear in [15 ] . Such directions indicate that m ( ⋅ ; x k , σ k ) m(\cdot;x_k,\sigma_k) m ( ⋅ ; x k , σ k ) is unbounded below. The algorithm of [15 ] would simply increase σ k \sigma_k σ k and compute a new step, or fall back on s k , c p ( ν k ) s_{k,\mathrm{cp}}(\nu_k) s k , cp ( ν k ) . Instead, Algorithm 4.1 exploits such directions by performing an Armijo-Goldstein line search.
We now justify that, under reasonable assumptions, a step length that satisfies the Armijo-Goldstein conditions along a nonpositive-curvature direction yields a step that satisfies (9) .
Our first result establishes that there exists an interval of positive step lengths that satisfy the Armijo-Goldstein line search conditions, whether the search direction is one of nonpositive curvature or not. We state this result as we were not able to find it in the literature, although it is very likely known.
Proposition 2 Let f : R n → R f : \mathbb{R}^{n} \to\mathbb{R} f : R n → R with f ∈ C 1 f \in C^{1} f ∈ C 1 be bounded below, x ∈ R n x \in\mathbb{R}^{n} x ∈ R n , and d d d be a descent direction for f f f from x x x , i.e., ∇ f ( x ) T d < 0 \nabla f(x)^{T}d < 0 ∇ f ( x ) T d < 0 . Let also 0 < ρ L < ρ U < 1 0 < \rho_{L} < \rho_{U} < 1 0 < ρ L < ρ U < 1 . Then, there exist 0 < α U < α L 0 < \alpha_{U} < \alpha_{L} 0 < α U < α L (possibly dependent on x x x ) such that (14) holds for all α U ≤ α ≤ α L \alpha_{U} \leq\alpha\leq\alpha_{L} α U ≤ α ≤ α L .
Proof. Denote ϕ ( α ) = f ( x + α d ) \phi(\alpha)=f(x+\alpha d) ϕ ( α ) = f ( x + α d ) . Since f f f is bounded below, so is ϕ \phi ϕ . Because ϕ ′ ( 0 ) = ∇ f ( x ) T d < 0 \phi'(0)=\nabla f(x)^{T}d<0 ϕ ′ ( 0 ) = ∇ f ( x ) T d < 0 and ϕ ′ \phi' ϕ ′ is continuous, there exists δ > 0 \delta>0 δ > 0 such that ϕ ′ ( α ) < 0 \phi'(\alpha)<0 ϕ ′ ( α ) < 0 , and hence ϕ ( α ) < ϕ ( 0 ) = f ( x ) \phi(\alpha)<\phi(0)=f(x) ϕ ( α ) < ϕ ( 0 ) = f ( x ) , for all 0 < α < δ 0<\alpha<\delta 0 < α < δ . Therefore, because 0 < ρ L < 1 0<\rho_{L}<1 0 < ρ L < 1 and d d d is a descent direction, the line ℓ L ( α ) = f ( x ) + ρ L α ∇ f ( x ) T d \ell_{L}(\alpha)=f(x)+\rho_{L}\alpha\nabla f(x)^{T}d ℓ L ( α ) = f ( x ) + ρ L α ∇ f ( x ) T d is unbounded below, and necessarily intersects the graph of ϕ \phi ϕ for some 0 < α < δ 0<\alpha<\delta 0 < α < δ . Let α L > 0 \alpha_{L}>0 α L > 0 be the smallest α > 0 \alpha>0 α > 0 such that ℓ L ( α ) = ϕ ( α ) \ell_{L}(\alpha)=\phi(\alpha) ℓ L ( α ) = ϕ ( α ) , i.e.,
f ( x + α L d ) = f ( x ) + ρ L α L ∇ f ( x ) T d . (17) f(x+\alpha_{L}d)=f(x)+\rho_{L}\alpha_{L}\nabla f(x)^{T}d. \tag*{(17)} f ( x + α L d ) = f ( x ) + ρ L α L ∇ f ( x ) T d . (17)
By construction,
f ( x + α d ) ≤ f ( x ) + ρ L α ∇ f ( x ) T d for all 0 ≤ α ≤ α L . (18) f(x+\alpha d)\leq f(x)+\rho_{L}\alpha\nabla f(x)^{T}d \quad\text{for all } 0\leq\alpha\leq\alpha_{L}. \tag*{(18)} f ( x + α d ) ≤ f ( x ) + ρ L α ∇ f ( x ) T d for all 0 ≤ α ≤ α L . (18)
As a consequence, any such α \alpha α satisfies the Armijo condition.
Define now ℓ U ( α ) = f ( x ) + ρ U α ∇ f ( x ) T d \ell_{U}(\alpha)=f(x)+\rho_{U}\alpha\nabla f(x)^{T}d ℓ U ( α ) = f ( x ) + ρ U α ∇ f ( x ) T d . By the same reasoning as above, there exists a smallest α ^ U > 0 \hat{\alpha}_{U}>0 α ^ U > 0 such that ϕ ( α ^ U ) = ℓ U ( α ^ U ) \phi(\hat{\alpha}_{U})=\ell_{U}(\hat{\alpha}_{U}) ϕ ( α ^ U ) = ℓ U ( α ^ U ) , i.e., f ( x + α ^ U d ) = f ( x ) + ρ U α ^ U ∇ f ( x ) T d f(x+\hat{\alpha}_{U}d)=f(x)+\rho_{U}\hat{\alpha}_{U}\nabla f(x)^{T}d f ( x + α ^ U d ) = f ( x ) + ρ U α ^ U ∇ f ( x ) T d . By construction,
f ( x + α d ) ≤ f ( x ) + ρ U α ∇ f ( x ) T d for all 0 ≤ α ≤ α ^ U . (19) f(x+\alpha d)\leq f(x)+\rho_{U}\alpha\nabla f(x)^{T}d \quad\text{for all } 0\leq\alpha\leq\hat{\alpha}_{U}. \tag*{(19)} f ( x + α d ) ≤ f ( x ) + ρ U α ∇ f ( x ) T d for all 0 ≤ α ≤ α ^ U . (19)
If, by contradiction, it were that α L ≤ α ^ U \alpha_{L}\leq\hat{\alpha}_{U} α L ≤ α ^ U , (17) and (19) would imply
f ( x ) + ρ U α L ∇ f ( x ) T d ≥ f ( x + α L d ) = f ( x ) + ρ L α L ∇ f ( x ) T d . f(x)+\rho_{U}\alpha_{L}\nabla f(x)^{T}d\geq f(x+\alpha_{L}d)=f(x)+\rho_{L}\alpha_{L}\nabla f(x)^{T}d. f ( x ) + ρ U α L ∇ f ( x ) T d ≥ f ( x + α L d ) = f ( x ) + ρ L α L ∇ f ( x ) T d .
But because ∇ f ( x ) T d < 0 \nabla f(x)^{T}d<0 ∇ f ( x ) T d < 0 , this would imply ρ U ≤ ρ L \rho_{U}\leq\rho_{L} ρ U ≤ ρ L , which is a contradiction. Hence, α L > α ^ U \alpha_{L}>\hat{\alpha}_{U} α L > α ^ U , and [ α ^ U , α L ] ≠ ∅ [\hat{\alpha}_{U},\alpha_{L}]\ne\varnothing [ α ^ U , α L ] = ∅ and is not a singleton.
There may exist other values α ^ U < α < α L \hat{\alpha}_{U}<\alpha<\alpha_{L} α ^ U < α < α L such that ϕ ( α ) = ℓ U ( α ) \phi(\alpha)=\ell_{U}(\alpha) ϕ ( α ) = ℓ U ( α ) . If so, let α U \alpha_{U} α U be the largest such α \alpha α —note that α U < α L \alpha_{U}<\alpha_{L} α U < α L because ℓ U ( α ) < ℓ L ( α ) \ell_{U}(\alpha)<\ell_{L}(\alpha) ℓ U ( α ) < ℓ L ( α ) for all α > 0 \alpha>0 α > 0 . If not, set α U = α ^ U \alpha_{U}=\hat{\alpha}_{U} α U = α ^ U . By continuity,
f ( x + α d ) ≥ f ( x ) + ρ U α ∇ f ( x ) T d for all α U ≤ α ≤ α L , (20) f(x+\alpha d)\geq f(x)+\rho_{U}\alpha\nabla f(x)^{T}d \quad\text{for all } \alpha_{U}\leq\alpha\leq\alpha_{L}, \tag*{(20)} f ( x + α d ) ≥ f ( x ) + ρ U α ∇ f ( x ) T d for all α U ≤ α ≤ α L , (20)
i.e., the Goldstein condition is satisfied. □ \quad\square □
The next result states that if d k d_{k} d k is a nonpositive-curvature direction at x k x_{k} x k and α k > 0 \alpha_{k}>0 α k > 0 satisfies (14) , s k : = α k d k s_{k}:=\alpha_{k}d_{k} s k := α k d k satisfies (9) under mild assumptions.
Proposition 3 Let f : R n → R f : \mathbb{R}^{n}\to\mathbb{R} f : R n → R with f ∈ C 1 f\in C^{1} f ∈ C 1 be bounded below. At iteration k k k , let x k ∈ R n x_{k}\in\mathbb{R}^{n} x k ∈ R n be the current iterate, d k ∈ R n d_{k}\in\mathbb{R}^{n} d k ∈ R n satisfy Definition 2, and α k > 0 \alpha_{k}>0 α k > 0 satisfy (14) . Assume that either (i) σ min > 0 \sigma_{\min}>0 σ m i n > 0 in Algorithm 4.1 , or that (ii) there exist κ 3 > 0 \kappa_{3}>0 κ 3 > 0 independent of k k k such that d k T B k d k ≤ − κ 3 ∥ d k ∥ 2 d_{k}^{T}B_{k}d_{k}\leq-\kappa_{3}\lVert d_{k}\rVert^{2} d k T B k d k ≤ − κ 3 ∥ d k ∥ 2 and κ b > 0 \kappa_{b}>0 κ b > 0 such that ∥ B k ∥ ≥ κ b \lVert B_{k}\rVert\geq\kappa_{b} ∥ B k ∥ ≥ κ b for all k k k . Assume also that there exists α min > 0 \alpha_{\min}>0 α m i n > 0 independent of k k k such that α k ≥ α min \alpha_{k}\geq\alpha_{\min} α k ≥ α m i n . There exists τ > 0 \tau>0 τ > 0 sufficiently small such that s k : = α k d k s_{k}:=\alpha_{k}d_{k} s k := α k d k satisfies (9) .
Proof. If σ k ≥ σ min > 0 \sigma_k \ge\sigma_{\min} > 0 σ k ≥ σ m i n > 0 , d k T B k d k ≤ − σ k ∥ d k ∥ 2 ≤ − σ min κ 1 2 ∥ ∇ f ( x k ) ∥ 2 d_k^T B_k d_k \le-\sigma_k \lVert d_k\rVert^2 \le-\sigma_{\min}\kappa_1^2 \lVert\nabla f(x_k)\rVert^2 d k T B k d k ≤ − σ k ∥ d k ∥ 2 ≤ − σ m i n κ 1 2 ∥ ∇ f ( x k ) ∥ 2 . Otherwise, our assumption ensures that d k T B k d k ≤ − κ 3 κ 1 2 ∥ ∇ f ( x k ) ∥ 2 d_k^T B_k d_k \le-\kappa_3\kappa_1^2 \lVert\nabla f(x_k)\rVert^2 d k T B k d k ≤ − κ 3 κ 1 2 ∥ ∇ f ( x k ) ∥ 2 . We continue the proof under the first assumption, but the second case is similar. Definition 2 yields
φ ( 0 ; x k ) − φ ( s k ; x k ) = − α k ∇ f ( x k ) T d k − 1 2 α k 2 d k T B k d k ≥ ( κ 1 α k + 1 2 σ min κ 1 2 α k 2 ) ∥ ∇ f ( x k ) ∥ 2 . \varphi(0;x_k)-\varphi(s_k;x_k)=-\alpha_k\nabla f(x_k)^T d_k-\frac{1}{2}\alpha_k^2d_k^T B_kd_k
\ge\left(\kappa_1\alpha_k+\frac{1}{2}\sigma_{\min}\kappa_1^2\alpha_k^2\right)\lVert\nabla f(x_k)\rVert^2. φ ( 0 ; x k ) − φ ( s k ; x k ) = − α k ∇ f ( x k ) T d k − 2 1 α k 2 d k T B k d k ≥ ( κ 1 α k + 2 1 σ m i n κ 1 2 α k 2 ) ∥ ∇ f ( x k ) ∥ 2 .
Thus, (9) holds if there exists τ > 0 \tau>0 τ > 0 such that κ 1 α k + 1 2 σ min κ 1 2 α k 2 ≥ τ ν k \kappa_1\alpha_k+\frac{1}{2}\sigma_{\min}\kappa_1^2\alpha_k^2\ge\tau\nu_k κ 1 α k + 2 1 σ m i n κ 1 2 α k 2 ≥ τ ν k . Under assumption (i), ν k ≤ ν max : = 1 / σ min \nu_k\le\nu_{\max}:=1/\sigma_{\min} ν k ≤ ν m a x := 1/ σ m i n for all k k k , which under assumption (ii), the same holds with ν max : = 1 / κ b \nu_{\max}:=1/\kappa_b ν m a x := 1/ κ b . Thus, the above holds if κ 1 α k + 1 2 σ min κ 1 2 α k 2 ≥ τ ν max \kappa_1\alpha_k+\frac{1}{2}\sigma_{\min}\kappa_1^2\alpha_k^2\ge\tau\nu_{\max} κ 1 α k + 2 1 σ m i n κ 1 2 α k 2 ≥ τ ν m a x . Since α k ≥ α min \alpha_k\ge\alpha_{\min} α k ≥ α m i n , it suffices to choose τ ≤ ( κ 1 α min + 1 2 σ min κ 1 2 α min 2 ) / ν max \tau\le(\kappa_1\alpha_{\min}+\frac{1}{2}\sigma_{\min}\kappa_1^2\alpha_{\min}^2)/\nu_{\max} τ ≤ ( κ 1 α m i n + 2 1 σ m i n κ 1 2 α m i n 2 ) / ν m a x .
In Proposition 3, Assumptions (i) and (ii) are assumptions on the algorithm. In particular, B k B_k B k must be chosen so nonpositive-curvature directions are directions of sufficient negative curvature for B k B_k B k . The assumption ∥ B k ∥ ≥ κ b \lVert B_k\rVert\ge\kappa_b ∥ B k ∥ ≥ κ b simply requires that B k B_k B k not asymptotically vanish. On the contrary, the assumption on α min \alpha_{\min} α m i n is an assumption on f f f . We now show that it holds, in particular, when ∇ f \nabla f ∇ f is Lipschitz continuous.
Proposition 4 Let d k ∈ R n d_k\in\mathbb{R}^n d k ∈ R n satisfy Definition 2 at x k ∈ R n x_k\in\mathbb{R}^n x k ∈ R n , and let α k > 0 \alpha_k>0 α k > 0 satisfy (14). Assume that ∇ f \nabla f ∇ f is Lipschitz continuous with constant L > 0 L>0 L > 0 . Finally, let κ 1 > ρ U κ 2 \kappa_1>\rho_U\kappa_2 κ 1 > ρ U κ 2 . Then, there exists α min > 0 \alpha_{\min}>0 α m i n > 0 independent of k k k such that α k ≥ α min \alpha_k\ge\alpha_{\min} α k ≥ α m i n .
Proof. We combine (14) with Lipschitz continuity of ∇ f \nabla f ∇ f to obtain
ρ U α k ∇ f ( x k ) T d k ≤ f ( x k + α k d k ) − f ( x k ) ≤ α k ∇ f ( x k ) T d k + 1 2 L α k 2 ∥ d k ∥ 2 . \rho_U\alpha_k\nabla f(x_k)^Td_k\le f(x_k+\alpha_kd_k)-f(x_k)\le\alpha_k\nabla f(x_k)^Td_k+\frac{1}{2}L\alpha_k^2\lVert d_k\rVert^2. ρ U α k ∇ f ( x k ) T d k ≤ f ( x k + α k d k ) − f ( x k ) ≤ α k ∇ f ( x k ) T d k + 2 1 L α k 2 ∥ d k ∥ 2 .
The left- and right-hand sides combine with Definition 1 and (13) to give
− ρ U κ 2 α k ∥ ∇ f ( x k ) ∥ 2 ≤ − κ 1 α k ∥ ∇ f ( x k ) ∥ 2 + 1 2 L κ 2 2 α k 2 ∥ ∇ f ( x k ) ∥ 2 . -\rho_U\kappa_2\alpha_k\lVert\nabla f(x_k)\rVert^2\le-\kappa_1\alpha_k\lVert\nabla f(x_k)\rVert^2+\frac{1}{2}L\kappa_2^2\alpha_k^2\lVert\nabla f(x_k)\rVert^2. − ρ U κ 2 α k ∥ ∇ f ( x k ) ∥ 2 ≤ − κ 1 α k ∥ ∇ f ( x k ) ∥ 2 + 2 1 L κ 2 2 α k 2 ∥ ∇ f ( x k ) ∥ 2 .
After simplifying by α k ∥ ∇ f ( x k ) ∥ 2 \alpha_k\lVert\nabla f(x_k)\rVert^2 α k ∥ ∇ f ( x k ) ∥ 2 , there remains
α k ≥ α min : = 2 ( κ 1 − ρ U κ 2 ) L κ 2 2 > 0. \alpha_k\ge\alpha_{\min}:=\frac{2(\kappa_1-\rho_U\kappa_2)}{L\kappa_2^2}>0. α k ≥ α m i n := L κ 2 2 2 ( κ 1 − ρ U κ 2 ) > 0.
Step Computation
We turn to practical procedures to compute s k s_k s k . The only requirement on s k s_k s k to preserve the convergence properties of [15 ] is that it satisfy (9). For reference, we note that the first-order optimality conditions of the subproblem are the symmetric linear system
( B k + σ k I ) s = − ∇ f ( x k ) . (21) (B_k+\sigma_kI)s=-\nabla f(x_k). \tag*{(21)} ( B k + σ k I ) s = − ∇ f ( x k ) . (21)
It is possible that an (inexact) solution of (21) be a descent direction for m ( ⋅ ; x k , σ k ) m(\cdot;x_k,\sigma_k) m ( ⋅ ; x k , σ k ) from s = 0 s=0 s = 0 even if B k + σ k I ⪰̸ 0 B_k+\sigma_kI\not\succeq0 B k + σ k I ⪰ 0 . We now outline several procedures to compute an exact or inexact solution of (21) that satisfies (9).
Exact Minimizer with Limited-Memory Quasi-Newton Approximation
When B k B_k B k is a limited-memory quasi-Newton approximation, and in particular, an L-BFGS approximation, Erway et al. [20 ] describe a procedure to solve (21) , which yields the unique exact minimizer of (7) . Clearly, this choice of s k s_k s k satisfies (11) . The procedure scans the pairs { s i , y i } \{s_i,y_i\} { s i , y i } , i = 1 , … , q i=1,\ldots,q i = 1 , … , q , that compose the approximation, where y i ≔ ∇ f ( x i + s i ) − ∇ f ( x i ) y_i \coloneqq\nabla f(x_i+s_i)-\nabla f(x_i) y i : = ∇ f ( x i + s i ) − ∇ f ( x i ) , and q ∈ N 0 q \in\mathbb{N}_0 q ∈ N 0 is the memory parameter. Overall, it requires 3 q 2 + 6 q + 3 3q^2+6q+3 3 q 2 + 6 q + 3 dot products and 2 q 2 − 2 q + 1 2q^2-2q+1 2 q 2 − 2 q + 1 vector updates. In addition, it requires 2 q 2q 2 q system solves with B k , 0 + σ k I B_{k,0}+\sigma_k I B k , 0 + σ k I as coefficient, where B k , 0 B_{k,0} B k , 0 is the initial L-BFGS approximation at iteration k k k . In our case, this coefficient is a multiple of the identity. In practice, q q q is typically around 5 or 10, which makes this procedure relatively cheap.
The conditions of Definition 1 are satisfied provided B k + σ k I B_k+\sigma_k I B k + σ k I is uniformly bounded and uniformly positive definite.
The Truncated Conjugate-Gradient Method
The conjugate-gradient (CG) method of Hestenes and Stiefel [28 ] was designed to solve symmetric positive-definite linear systems. In the absence of positive definiteness, Steihaug [52 ] argued that it remains relevant for optimization in the sense that it may be applied to (21) with appropriate stopping conditions, and yield a step that induces sufficient decrease in m ( ⋅ ; x k , σ k ) m(\cdot;x_k,\sigma_k) m ( ⋅ ; x k , σ k ) . The procedure proposed in [52 ] is called the truncated conjugate-gradient method, which we refer to as truncated CG . Even though we do not assume that B k + σ k I ≻ 0 B_k+\sigma_k I \succ0 B k + σ k I ≻ 0 , in order for this approach to apply, we assume that the first CG iteration is well defined, i.e.,
∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) > 0. (22) \nabla f(x_k)^T(B_k+\sigma_k I)\nabla f(x_k)>0. \tag*{(22)} ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) > 0. (22)
When (22) does not hold, d k = − ∇ f ( x k ) d_k=-\nabla f(x_k) d k = − ∇ f ( x k ) is a direction of nonpositive curvature, and we perform an Armijo-Goldstein line search along that direction.
CG generates iterates s k , j s_{k,j} s k , j , j = 0 , 1 , … j=0,1,\ldots j = 0 , 1 , … , starting with s k , 0 ≔ 0 s_{k,0}\coloneqq0 s k , 0 : = 0 , by way of an exact line search procedure s k , j + 1 = s k , j + α k , j p k , j s_{k,j+1}=s_{k,j}+\alpha_{k,j}p_{k,j} s k , j + 1 = s k , j + α k , j p k , j , where α k , j > 0 \alpha_{k,j}>0 α k , j > 0 is a step length and p k , j p_{k,j} p k , j is a search direction. The s k , j s_{k,j} s k , j are increasingly better approximations of an exact solution of (21) in the sense that m ( s k , j ; x k , σ k ) m(s_{k,j};x_k,\sigma_k) m ( s k , j ; x k , σ k ) decreases monotonically as j j j increases as long as p k , j T ( B k + σ k I ) p k , j > 0 p_{k,j}^T(B_k+\sigma_k I)p_{k,j}>0 p k , j T ( B k + σ k I ) p k , j > 0 . If B k + σ k I ≻ 0 B_k+\sigma_k I\succ0 B k + σ k I ≻ 0 , CG will, in exact arithmetic, terminate after at most n n n iterations with s k , n = s k s_{k,n}=s_k s k , n = s k , an exact solution of (21) . In practice, it is not necessary to achieve optimality of the subproblem. Indeed, by the monotonicity property just mentioned, m ( s k , j ; x k , σ k ) ≤ m ( s k , 1 ; x k , σ k ) m(s_{k,j};x_k,\sigma_k)\leq m(s_{k,1};x_k,\sigma_k) m ( s k , j ; x k , σ k ) ≤ m ( s k , 1 ; x k , σ k ) for all j ≥ 1 j\geq1 j ≥ 1 . Below, we justify that s k , 1 s_{k,1} s k , 1 satisfies (11) , which continues to hold if we perform further CG iterations.
If B k + σ k I ≠ 0 B_k+\sigma_k I\neq0 B k + σ k I = 0 , CG will generate a search direction p k , j p_{k,j} p k , j such that p k , j T ( B k + σ k I ) p k , j ≤ 0 p_{k,j}^T(B_k+\sigma_k I)p_{k,j}\leq0 p k , j T ( B k + σ k I ) p k , j ≤ 0 , at least in exact arithmetic. We call such p k , j p_{k,j} p k , j a direction of nonpositive curvature. The logic of truncated CG is that we apply the CG updates as long as no such p k , j p_{k,j} p k , j is generated, and terminate when the residual norm ∥ ( B k + σ k I ) s + ∇ f ( x k ) ∥ \lVert(B_k+\sigma_k I)s+\nabla f(x_k)\rVert ∥( B k + σ k I ) s + ∇ f ( x k )∥ is smaller than a prescribed tolerance. If a direction of nonpositive curvature p k , j p_{k,j} p k , j is generated at iteration j > 0 j>0 j > 0 of CG, the iterate s k , j s_{k,j} s k , j is returned. If instead j = 0 j=0 j = 0 , (22) does not hold because p k , 0 ≔ − ∇ f ( x k ) p_{k,0}\coloneqq-\nabla f(x_k) p k , 0 : = − ∇ f ( x k ) , and the direction − ∇ f ( x k ) -\nabla f(x_k) − ∇ f ( x k ) is returned as it is known to be a descent direction for m ( ⋅ ; x k , σ k ) m(\cdot;x_k,\sigma_k) m ( ⋅ ; x k , σ k ) from s = 0 s=0 s = 0 .
Proposition 5 Let (22) hold. The iterate s k , j s_{k,j} s k , j returned by truncated CG satisfies (11) .
Proof. By assumption, truncated CG stops at an iteration j ≥ 1 j \ge1 j ≥ 1 . At iteration j = 1 j = 1 j = 1 , s k , 1 s_{k,1} s k , 1 is selected as the unique global minimizer of the convex quadratic α ↦ m ( − α ∇ f ( x k ) ; x k , σ k ) \alpha\mapsto m(-\alpha\nabla f(x_k);x_k,\sigma_k) α ↦ m ( − α ∇ f ( x k ) ; x k , σ k ) . CG iterations 2 , … , j − 1 2,\ldots,j-1 2 , … , j − 1 further decrease m ( ⋅ ; x k , σ k ) m(\cdot;x_k,\sigma_k) m ( ⋅ ; x k , σ k ) , and therefore, (11) must be satisfied with τ 0 = 1 \tau_0=1 τ 0 = 1 .
Recall that, when (22) holds, s k , 1 = α k , 0 p k , 0 s_{k,1}=\alpha_{k,0}p_{k,0} s k , 1 = α k , 0 p k , 0 where p k , 0 : = − ∇ f ( x k ) p_{k,0}:=-\nabla f(x_k) p k , 0 := − ∇ f ( x k ) and
α k , 0 = α k C G : = α ˉ k , c p , (23) \alpha_{k,0}=\alpha_k^{\mathrm{CG}}:=\bar{\alpha}_{k,\mathrm{cp}}, \tag*{(23)} α k , 0 = α k CG := α ˉ k , cp , (23)
where α ˉ k , c p \bar{\alpha}_{k,\mathrm{cp}} α ˉ k , cp is defined in (15) . We also define s k C G : = − α k C G ∇ f ( x k ) s_k^{\mathrm{CG}}:=-\alpha_k^{\mathrm{CG}}\nabla f(x_k) s k CG := − α k CG ∇ f ( x k ) .
In CG, detecting directions of nonpositive curvature is straightforward as p k , j T ( B k + σ k I ) p k , j p_{k,j}^{T}(B_k+\sigma_k I)p_{k,j} p k , j T ( B k + σ k I ) p k , j is computed once per iteration. When that quantity is nonpositive, CG terminates and returns
the search direction − ∇ f ( x k ) -\nabla f(x_k) − ∇ f ( x k ) if j = 0 j=0 j = 0 , and flags that direction as a direction of nonpositive curvature;
the iterate s k , j s_{k,j} s k , j as approximate solution if j > 0 j>0 j > 0 , and flags p k , j p_{k,j} p k , j as a direction of nonpositive curvature.
In the second case, one may choose to simply use s k , j s_{k,j} s k , j as step s k s_k s k as it satisfies (11) , or to exploit the direction of nonpositive curvature via the Armijo-Goldstein line search.
The conditions of Definition 1 are satisfied provided the projection of B k + σ k I B_k+\sigma_k I B k + σ k I in the subspace generated by the p k , j p_{k,j} p k , j during the CG iterations is uniformly bounded and uniformly positive definite.
The Truncated Conjugate-Residual Method
The conjugate-residual (CR) method was also proposed by Hestenes and Stiefel [28 ] . Contrary to CG, it is designed to solve (21) by minimizing its residual norm. Similarly to CG, CR generates iterates s k , j s_{k,j} s k , j from s k , 0 : = 0 s_{k,0}:=0 s k , 0 := 0 by way of an exact line search procedure and is known to induce monotonic decrease in m ( ⋅ ; x k , σ k ) m(\cdot;x_k,\sigma_k) m ( ⋅ ; x k , σ k ) as long as no nonpositive curvature direction has been found [11 , 22 ] .
Dahito and Orban [11 ] formulate the truncated CR method, which is relevant for optimization and shares the main features of truncated CG. As in § 6.2 , we show that the first truncated CR iterate s k , 1 s_{k,1} s k , 1 satisfies (11) . Further iterations only result in further decrease in m ( ⋅ ; x k , σ k ) m(\cdot;x_k,\sigma_k) m ( ⋅ ; x k , σ k ) as long as positive curvature is observed. For the truncated CR method to apply, we again assume that (22) holds for s k , 1 : = α k , 0 p k , 0 s_{k,1}:=\alpha_{k,0}p_{k,0} s k , 1 := α k , 0 p k , 0 with p k , 0 : = − ∇ f ( x k ) p_{k,0}:=-\nabla f(x_k) p k , 0 := − ∇ f ( x k ) as in truncated CG, but this time,
α k , 0 = α k C R : = ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ∇ f ( x k ) T ( B k + σ k I ) 2 ∇ f ( x k ) , (24) \alpha_{k,0}=\alpha_k^{\mathrm{CR}}:=\frac{\nabla f(x_k)^T(B_k+\sigma_k I)\nabla f(x_k)}{\nabla f(x_k)^T(B_k+\sigma_k I)^2\nabla f(x_k)}, \tag*{(24)} α k , 0 = α k CR := ∇ f ( x k ) T ( B k + σ k I ) 2 ∇ f ( x k ) ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) , (24)
and s k C R : = − α k C R ∇ f ( x k ) s_k^{\mathrm{CR}}:=-\alpha_k^{\mathrm{CR}}\nabla f(x_k) s k CR := − α k CR ∇ f ( x k ) . We examine two cases. In the first, B k + σ k I ≻ 0 B_k+\sigma_k I\succ0 B k + σ k I ≻ 0 , and (11) holds without further assumptions. In the second, B k + σ k I ⊁ 0 B_k+\sigma_k I\not\succ0 B k + σ k I ≻ 0 , and (11) follows provided the left-hand side of (22) remains sufficiently positive and { B k } \{B_k\} { B k } is bounded.
In both cases, the following result holds.
Proposition 6. Assume (22) holds. Then, α k C R ≤ α k C G \alpha_k^{\mathrm{CR}} \le\alpha_k^{\mathrm{CG}} α k CR ≤ α k CG .
Proof. By the Cauchy-Schwarz inequality,
( ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ) 2 ≤ ∥ ∇ f ( x k ) ∥ 2 ∥ ( B k + σ k I ) ∇ f ( x k ) ∥ 2 = ∥ ∇ f ( x k ) ∥ 2 ( ∇ f ( x k ) T ( B k + σ k I ) 2 ∇ f ( x k ) ) . \left(\nabla f(x_k)^T(B_k+\sigma_k I)\nabla f(x_k)\right)^2 \le\|\nabla f(x_k)\|^2\|(B_k+\sigma_k I)\nabla f(x_k)\|^2
= \|\nabla f(x_k)\|^2\left(\nabla f(x_k)^T(B_k+\sigma_k I)^2\nabla f(x_k)\right). ( ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ) 2 ≤ ∥∇ f ( x k ) ∥ 2 ∥ ( B k + σ k I ) ∇ f ( x k ) ∥ 2 = ∥∇ f ( x k ) ∥ 2 ( ∇ f ( x k ) T ( B k + σ k I ) 2 ∇ f ( x k ) ) .
Therefore, (23) and (24) yield α k C R ≤ α k C G \alpha_k^{\mathrm{CR}} \le\alpha_k^{\mathrm{CG}} α k CR ≤ α k CG .
Proposition 7. Assume (22) holds. Let B k + σ k I ≻ 0 B_k+\sigma_kI \succ0 B k + σ k I ≻ 0 . Then, ν k ≤ α k C R ≤ α k C G \nu_k \le\alpha_k^{\mathrm{CR}} \le\alpha_k^{\mathrm{CG}} ν k ≤ α k CR ≤ α k CG and (11) holds with τ 0 = 1 \tau_0=1 τ 0 = 1 .
Proof. Because B k + σ k I ≻ 0 B_k+\sigma_kI \succ0 B k + σ k I ≻ 0 ,
∇ f ( x k ) T ( B k + σ k I ) 2 ∇ f ( x k ) ≤ ∥ B k + σ k I ∥ ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) . \nabla f(x_k)^T(B_k+\sigma_kI)^2\nabla f(x_k) \le\|B_k+\sigma_kI\|\nabla f(x_k)^T(B_k+\sigma_kI)\nabla f(x_k). ∇ f ( x k ) T ( B k + σ k I ) 2 ∇ f ( x k ) ≤ ∥ B k + σ k I ∥∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) .
Thus, (24) yields α k C R ≥ 1 / ∥ B k + σ k I ∥ ≥ 1 / ( ∥ B k ∥ + σ k ) ≥ ν k \alpha_k^{\mathrm{CR}} \ge1/\|B_k+\sigma_kI\| \ge1/(\|B_k\|+\sigma_k) \ge\nu_k α k CR ≥ 1/∥ B k + σ k I ∥ ≥ 1/ ( ∥ B k ∥ + σ k ) ≥ ν k . Proposition 6 provides α k C R ≤ α k C G \alpha_k^{\mathrm{CR}} \le\alpha_k^{\mathrm{CG}} α k CR ≤ α k CG . Because α k C G \alpha_k^{\mathrm{CG}} α k CG is the step length to the unique global minimizer of the convex quadratic α ↦ m ( − α ∇ f ( x k ) ; x k , σ k ) \alpha\mapsto m(-\alpha\nabla f(x_k);x_k,\sigma_k) α ↦ m ( − α ∇ f ( x k ) ; x k , σ k ) by definition,
m ( 0 ; x k , σ k ) − m ( s k , c p ; x k , σ k ) ≤ m ( 0 ; x k , σ k ) − m ( s k C R ; x k , σ k ) ≤ m ( 0 ; x k , σ k ) − m ( s k C G ; x k , σ k ) , m(0;x_k,\sigma_k)-m(s_{k,\mathrm{cp}};x_k,\sigma_k) \le m(0;x_k,\sigma_k)-m(s_k^{\mathrm{CR}};x_k,\sigma_k)
\le m(0;x_k,\sigma_k)-m(s_k^{\mathrm{CG}};x_k,\sigma_k), m ( 0 ; x k , σ k ) − m ( s k , cp ; x k , σ k ) ≤ m ( 0 ; x k , σ k ) − m ( s k CR ; x k , σ k ) ≤ m ( 0 ; x k , σ k ) − m ( s k CG ; x k , σ k ) ,
so that (11) holds with τ 0 = 1 \tau_0=1 τ 0 = 1 .
Whenever B k ⪰ 0 B_k \succeq0 B k ⪰ 0 for all k k k , as is the case if it is an L-BFGS approximation, among other situations, Proposition 7 shows that the truncated CR method always yields sufficient decrease. When B k + σ k I ⊁ 0 B_k+\sigma_kI \not\succ0 B k + σ k I ≻ 0 , we require additional assumptions. For reference, define
Δ k ( α ) : = m ( 0 ; x k , σ k ) − m ( − α ∇ f ( x k ) ; x k , σ k ) = α ( ∥ ∇ f ( x k ) ∥ 2 − 1 2 α ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ) . (25) \Delta_k(\alpha) \mathrel{:=} m(0;x_k,\sigma_k)-m(-\alpha\nabla f(x_k);x_k,\sigma_k)
= \alpha\left(\|\nabla f(x_k)\|^2-\frac{1}{2}\alpha\nabla f(x_k)^T(B_k+\sigma_kI)\nabla f(x_k)\right). \tag*{(25)} Δ k ( α ) := m ( 0 ; x k , σ k ) − m ( − α ∇ f ( x k ) ; x k , σ k ) = α ( ∥∇ f ( x k ) ∥ 2 − 2 1 α ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ) . (25)
Proposition 8. Let s k s_k s k be computed by the truncated CR method. Assume that there exist γ min > 0 \gamma_{\min}>0 γ m i n > 0 , κ B > 0 \kappa_B>0 κ B > 0 and $\sigma_{\max}>0 such that
∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ≥ γ min ∥ ∇ f ( x k ) ∥ 2 , (26) \nabla f(x_k)^T(B_k+\sigma_kI)\nabla f(x_k) \ge\gamma_{\min}\|\nabla f(x_k)\|^2, \tag*{(26)} ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ≥ γ m i n ∥∇ f ( x k ) ∥ 2 , (26) ∥ B k ∥ ≤ κ B \|B_k\|\le\kappa_B ∥ B k ∥ ≤ κ B , and σ k ≤ σ max \sigma_k\le\sigma_{\max} σ k ≤ σ m a x for all k k k . There exists τ 0 > 0 \tau_0>0 τ 0 > 0 such that (11) holds for all k k k .
Proof. By (25) , the model decrease at s k , c p s_{k,\mathrm{cp}} s k , cp reads
Δ k ( ν k ) = θ 1 ∥ B k ∥ + σ k ( ∥ ∇ f ( x k ) ∥ 2 − 1 2 θ 1 ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ∥ B k ∥ + σ k ) ≤ θ 1 ( 1 − 1 2 θ 1 γ min κ B + σ max ) ∥ ∇ f ( x k ) ∥ 2 ∥ B k ∥ + σ k . \begin{aligned}
\Delta_k(\nu_k)=\frac{\theta_1}{\|B_k\|+\sigma_k}\left(\|\nabla f(x_k)\|^2-\frac{1}{2}\theta_1\frac{\nabla f(x_k)^T(B_k+\sigma_kI)\nabla f(x_k)}{\|B_k\|+\sigma_k}\right) \\
&\le\theta_1\left(1-\frac{1}{2}\theta_1\frac{\gamma_{\min}}{\kappa_B+\sigma_{\max}}\right)\frac{\|\nabla f(x_k)\|^2}{\|B_k\|+\sigma_k}.
\end{aligned} Δ k ( ν k ) = ∥ B k ∥ + σ k θ 1 ( ∥∇ f ( x k ) ∥ 2 − 2 1 θ 1 ∥ B k ∥ + σ k ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ) ≤ θ 1 ( 1 − 2 1 θ 1 κ B + σ m a x γ m i n ) ∥ B k ∥ + σ k ∥∇ f ( x k ) ∥ 2 .
Without loss of generality, we may assume that κ B \kappa_B κ B and σ max \sigma_{\max} σ m a x are large enough that the parenthesized factor above is positive. Our assumption on γ min \gamma_{\min} γ m i n and (24) yield α k C R ≥ γ min ( ∥ B k ∥ + σ k ) 2 \alpha_k^{\mathrm{CR}} \ge\frac{\gamma_{\min}}{(\lVert B_k\rVert+\sigma_k)^2} α k CR ≥ (∥ B k ∥ + σ k ) 2 γ m i n . The same Cauchy-Schwarz inequality as in the proof of Proposition 6 gives
α k C R ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) = ( ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ) 2 ∇ f ( x k ) T ( B k + σ k I ) 2 ∇ f ( x k ) ≤ ∥ ∇ f ( x k ) ∥ 2 . \alpha_k^{\mathrm{CR}}\nabla f(x_k)^T(B_k+\sigma_k I)\nabla f(x_k)=\frac{\left(\nabla f(x_k)^T(B_k+\sigma_k I)\nabla f(x_k)\right)^2}{\nabla f(x_k)^T(B_k+\sigma_k I)^2\nabla f(x_k)}\le\lVert\nabla f(x_k)\rVert^2. α k CR ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) = ∇ f ( x k ) T ( B k + σ k I ) 2 ∇ f ( x k ) ( ∇ f ( x k ) T ( B k + σ k I ) ∇ f ( x k ) ) 2 ≤ ∥ ∇ f ( x k ) ∥ 2 .
Combined with (25) , the above shows that the model decrease at s k C R s_k^{\mathrm{CR}} s k CR is
Δ k ( α k C R ) ≥ 1 2 γ min ( ∥ B k ∥ + σ k ) 2 ∥ ∇ f ( x k ) ∥ 2 ≥ 1 2 γ min κ B + σ max ∥ ∇ f ( x k ) ∥ 2 ∥ B k ∥ + σ k . \Delta_k(\alpha_k^{\mathrm{CR}})\ge\frac{1}{2}\frac{\gamma_{\min}}{(\lVert B_k\rVert+\sigma_k)^2}\lVert\nabla f(x_k)\rVert^2\ge\frac{1}{2}\frac{\gamma_{\min}}{\kappa_B+\sigma_{\max}}\frac{\lVert\nabla f(x_k)\rVert^2}{\lVert B_k\rVert+\sigma_k}. Δ k ( α k CR ) ≥ 2 1 (∥ B k ∥ + σ k ) 2 γ m i n ∥ ∇ f ( x k ) ∥ 2 ≥ 2 1 κ B + σ m a x γ m i n ∥ B k ∥ + σ k ∥ ∇ f ( x k ) ∥ 2 .
Finally, we obtain Δ k ( α k C R ) ≥ τ 0 Δ k ( ν k ) \Delta_k(\alpha_k^{\mathrm{CR}})\ge\tau_0\Delta_k(\nu_k) Δ k ( α k CR ) ≥ τ 0 Δ k ( ν k ) with
τ 0 : = 1 2 γ min κ B + σ max ( θ 1 ( 1 − 1 2 θ 1 γ min κ B + σ max ) ) . \tau_0:=\frac{1}{2}\frac{\gamma_{\min}}{\kappa_B+\sigma_{\max}}\left(\theta_1\left(1-\frac{1}{2}\theta_1\frac{\gamma_{\min}}{\kappa_B+\sigma_{\max}}\right)\right). τ 0 := 2 1 κ B + σ m a x γ m i n ( θ 1 ( 1 − 2 1 θ 1 κ B + σ m a x γ m i n ) ) .
In Algorithm 4.1 , there is no guarantee that { σ k } \{\sigma_k\} { σ k } remains bounded, even if { B k } \{B_k\} { B k } is bounded, unless ∇ f \nabla f ∇ f is Lipschitz continuous. However, under the latter assumption, boundedness of { B k } \{B_k\} { B k } implies boundedness of { σ k } \{\sigma_k\} { σ k } . The proof of this assertion is identical to that of [3 Theorem 4.1] .
In CR, it is possible to detect two types of directions of nonpositive curvature. As in CG, nonpositive curvature may occur along a search direction p k , j p_{k,j} p k , j , but it may also occur along a residual r k , j = − ∇ f ( x k ) − ( B k + σ k I ) s k , j r_{k,j}=-\nabla f(x_k)-(B_k+\sigma_k I)s_{k,j} r k , j = − ∇ f ( x k ) − ( B k + σ k I ) s k , j . Dahito and Orban [11 ] modify CR to instrument it with nonpositive curvature detection along both directions without incurring the cost of extra operator-vector products with B k + σ k I B_k+\sigma_k I B k + σ k I . When nonpositive curvature is detected along either, or both, directions, CR terminates and returns
the search direction − ∇ f ( x k ) -\nabla f(x_k) − ∇ f ( x k ) if j = 0 j=0 j = 0 , and flags that direction as a direction of nonpositive curvature;
the iterate s k , j s_{k,j} s k , j as approximate solution if j > 0 j>0 j > 0 , and flags either or both of p k , j p_{k,j} p k , j and r k , j r_{k,j} r k , j as a direction of nonpositive curvature.
In the second case, one may simply use s k , j s_{k,j} s k , j as step s k s_k s k as it satisfies (11) , or to exploit the direction(s) of nonpositive curvature via the Armijo-Goldstein line search.
As in the case of truncated CG, the conditions of Definition 1 are satisfied provided the projection of B k + σ k I B_k+\sigma_k I B k + σ k I in the subspace generated by the p k , j p_{k,j} p k , j during the CR iterations is uniformly bounded and uniformly positive definite.
Modified MINRES
In exact arithmetic, MINRES [49 ] is equivalent to CR as long as no direction of nonpositive curvature is detected. In practice, MINRES can be significantly more stable than CR in the presence of rounding errors and ill conditioning. In MINRES as in CR, nonpositive curvature may occur along a search direction p k , j p_{k,j} p k , j or along a residual r k , j = − ∇ f ( x k ) − ( B k + σ k I ) s k , j r_{k,j}=-\nabla f(x_k)-(B_k+\sigma_k I)s_{k,j} r k , j = − ∇ f ( x k ) − ( B k + σ k I ) s k , j . Based on the work of Dahito and Orban [11 ] , Liu and Roosta [38 ] modified MINRES to add nonpositive curvature detection. The results on truncated CR apply to modified MINRES, and the same guarantees hold.
Exact Solution via Sparse Factorization
When ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇ 2 f ( x k ) exists and is available at acceptable expense, it often occurs that it is large and sparse. In our implementation of Algorithm 4.1 , it is possible to solve (21) via a sparse factorization method. Such a method typically raises a warning when B k + σ k I B_k+\sigma_k I B k + σ k I is singular, and its solution may fail to be a descent direction. In that event, we declare iteration k k k unsuccessful without evaluating f f f , i.e., we set x k + 1 = x k x_{k+1}=x_k x k + 1 = x k and increase σ k \sigma_k σ k . If s k s_k s k is a positive-curvature direction, we now verify that it satisfies (9) .
Proposition 9 Assume that either σ min > 0 \sigma_{\min}>0 σ m i n > 0 in Algorithm 4.1 or that there exists κ b > 0 \kappa_b>0 κ b > 0 such that ∥ B k ∥ ≥ κ b \lVert B_k\rVert\geq\kappa_b ∥ B k ∥ ≥ κ b for all k k k . Let s k s_k s k be computed by solving the nonsingular system (21) via a sparse factorization, and satisfy Definition 1. Then, there exists τ > 0 \tau>0 τ > 0 independent of k k k such that (9) holds.
Proof. If σ min > 0 \sigma_{\min}>0 σ m i n > 0 , let ν max : = 1 / σ min \nu_{\max}:=1/\sigma_{\min} ν m a x := 1/ σ m i n . Otherwise, if ∥ B k ∥ ≥ κ b \lVert B_k\rVert\geq\kappa_b ∥ B k ∥ ≥ κ b for all k k k , let ν max : = 1 / κ b \nu_{\max}:=1/\kappa_b ν m a x := 1/ κ b . In both cases, ν k ≤ ν max \nu_k\leq\nu_{\max} ν k ≤ ν m a x for all k k k . Define also τ : = 1 2 κ 1 / ν max \tau:=\frac{1}{2}\kappa_1/\nu_{\max} τ := 2 1 κ 1 / ν m a x . From (21) and Definition 1,
φ ( 0 ; x k ) − φ ( s k ; x k ) = − ∇ f ( x k ) T s k − 1 2 s k T B k s k = − 1 2 ∇ f ( x k ) T s k + 1 2 σ k ∥ s k ∥ 2 ≥ − 1 2 ∇ f ( x k ) T s k ≥ 1 2 κ 1 ∥ ∇ f ( x k ) ∥ 2 = τ ν max ∥ ∇ f ( x k ) ∥ 2 ≥ τ ν k ∥ ∇ f ( x k ) ∥ 2 = τ ξ k , c p ≥ min ( 1 , τ ) ξ k , c p , \begin{aligned}
\varphi(0;x_k)-\varphi(s_k;x_k)
&=-\nabla f(x_k)^T s_k-\frac{1}{2}s_k^T B_k s_k\\
&=-\frac{1}{2}\nabla f(x_k)^T s_k+\frac{1}{2}\sigma_k\lVert s_k\rVert^2\\
&\geq-\frac{1}{2}\nabla f(x_k)^T s_k\\
&\geq\frac{1}{2}\kappa_1\lVert\nabla f(x_k)\rVert^2\\
&=\tau\nu_{\max}\lVert\nabla f(x_k)\rVert^2\\
&\geq\tau\nu_k\lVert\nabla f(x_k)\rVert^2\\
&=\tau\xi_{k,\mathrm{cp}}\geq\min(1,\tau)\xi_{k,\mathrm{cp}},
\end{aligned} φ ( 0 ; x k ) − φ ( s k ; x k ) = − ∇ f ( x k ) T s k − 2 1 s k T B k s k = − 2 1 ∇ f ( x k ) T s k + 2 1 σ k ∥ s k ∥ 2 ≥ − 2 1 ∇ f ( x k ) T s k ≥ 2 1 κ 1 ∥ ∇ f ( x k ) ∥ 2 = τ ν m a x ∥ ∇ f ( x k ) ∥ 2 ≥ τ ν k ∥ ∇ f ( x k ) ∥ 2 = τ ξ k , cp ≥ min ( 1 , τ ) ξ k , cp ,
The conditions of Definition 1 are satisfied provided B k + σ k I B_k+\sigma_k I B k + σ k I is uniformly bounded and uniformly nonsingular.
Treatment of Nonpositive Curvature Directions
As indicated above, if d k d_k d k satisfying Definition 2 is identified using any of the subproblem solvers, we perform an Armijo-Goldstein line search along that direction. Other strategies are possible. In truncated CG, CR and MINRES, one may choose to set s k s_k s k to the most recent subproblem solver iterate before nonpositive curvature was identified. Or one may revert to the Cauchy step. We compare such strategies in § 13 .
As a final remark, under reasonable assumptions, we may bypass the computation of ρ k \rho_k ρ k and the acceptance test ρ k ≥ η 1 \rho_k\geq\eta_1 ρ k ≥ η 1 for steps s k = α k d k s_k=\alpha_kd_k s k = α k d k computed from a nonpositive-curvature direction and a step length satisfying the Armijo-Goldstein conditions.
Proposition 10 Let d k ∈ R n d_k\in\mathbb{R}^n d k ∈ R n be a direction of nonpositive curvature at x k ∈ R n x_k\in\mathbb{R}^n x k ∈ R n , and assume that there exists κ 4 > 0 \kappa_4>0 κ 4 > 0 such that d k T B k d k ≥ − κ 4 ∥ d k ∥ 2 d_k^T B_kd_k\geq-\kappa_4\lVert d_k\rVert^2 d k T B k d k ≥ − κ 4 ∥ d k ∥ 2 . Let α k > 0 \alpha_k>0 α k > 0 be such that (14) holds, and assume that there exists α max > 0 \alpha_{\max}>0 α m a x > 0 such that α k ≤ α max \alpha_k\leq\alpha_{\max} α k ≤ α m a x for all k k k . Finally, let s k : = α k d k s_k:=\alpha_kd_k s k := α k d k . Then, ρ k ≥ η ~ 1 \rho_k\geq\tilde{\eta}_1 ρ k ≥ η ~ 1 , where η ~ 1 : = ρ L κ 1 / ( κ 2 ( 1 + 1 2 κ 2 κ 4 α max ) ) > 0 \tilde{\eta}_1:=\rho_L\kappa_1/\left(\kappa_2\left(1+\frac{1}{2}\kappa_2\kappa_4\alpha_{\max}\right)\right)>0 η ~ 1 := ρ L κ 1 / ( κ 2 ( 1 + 2 1 κ 2 κ 4 α m a x ) ) > 0 .
Proof. The Armijo condition in (14) and (13) yield
f ( x k ) − f ( x k + s k ) ≥ − ρ L α k ∇ f ( x k ) T d k ≥ ρ L κ 1 α k ∥ ∇ f ( x k ) ∥ 2 . f(x_k)-f(x_k+s_k) \ge-\rho_L\alpha_k\nabla f(x_k)^T d_k \ge\rho_L\kappa_1\alpha_k\lVert\nabla f(x_k)\rVert^2. f ( x k ) − f ( x k + s k ) ≥ − ρ L α k ∇ f ( x k ) T d k ≥ ρ L κ 1 α k ∥ ∇ f ( x k ) ∥ 2 .
The definition of ρ k \rho_k ρ k , Definition 2, (13) again, and our assumption give
ρ k = f ( x k ) − f ( x k + s k ) − α k ∇ f ( x k ) T d k − 1 2 α k 2 d k T B k d k ≥ ρ L κ 1 α k ∥ ∇ f ( x k ) ∥ 2 κ 2 α k ∥ ∇ f ( x k ) ∥ 2 + 1 2 κ 4 α k 2 ∥ d k ∥ 2 ≥ ρ L κ 1 α k ∥ ∇ f ( x k ) ∥ 2 κ 2 α k ∥ ∇ f ( x k ) ∥ 2 + 1 2 κ 2 2 κ 4 α k 2 ∥ ∇ f ( x k ) ∥ 2 = ρ L κ 1 κ 2 + 1 2 κ 2 2 κ 4 α k ≥ η ~ 1 . \begin{aligned}
\rho_k
&= \frac{f(x_k)-f(x_k+s_k)}
{-\alpha_k\nabla f(x_k)^T d_k-\frac{1}{2}\alpha_k^2d_k^T B_kd_k}\\
&\ge\frac{\rho_L\kappa_1\alpha_k\lVert\nabla f(x_k)\rVert^2}
{\kappa_2\alpha_k\lVert\nabla f(x_k)\rVert^2+\frac{1}{2}\kappa_4\alpha_k^2\lVert d_k\rVert^2}\\
&\ge\frac{\rho_L\kappa_1\alpha_k\lVert\nabla f(x_k)\rVert^2}
{\kappa_2\alpha_k\lVert\nabla f(x_k)\rVert^2+\frac{1}{2}\kappa_2^2\kappa_4\alpha_k^2\lVert\nabla f(x_k)\rVert^2}\\
&= \frac{\rho_L\kappa_1}{\kappa_2+\frac{1}{2}\kappa_2^2\kappa_4\alpha_k}\ge\widetilde{\eta}_1.
\end{aligned} ρ k = − α k ∇ f ( x k ) T d k − 2 1 α k 2 d k T B k d k f ( x k ) − f ( x k + s k ) ≥ κ 2 α k ∥ ∇ f ( x k ) ∥ 2 + 2 1 κ 4 α k 2 ∥ d k ∥ 2 ρ L κ 1 α k ∥ ∇ f ( x k ) ∥ 2 ≥ κ 2 α k ∥ ∇ f ( x k ) ∥ 2 + 2 1 κ 2 2 κ 4 α k 2 ∥ ∇ f ( x k ) ∥ 2 ρ L κ 1 α k ∥ ∇ f ( x k ) ∥ 2 = κ 2 + 2 1 κ 2 2 κ 4 α k ρ L κ 1 ≥ η 1 .
The first assumption in Proposition 10 asserts that nonpositive-curvature directions are not directions of arbitrarily-negative curvature for B k B_k B k . The second assumption requires that step lengths that satisfy the Armijo condition in (14) not be arbitrarily large. It holds, in particular, when f f f satisfies a Polyak–Łojasiewicz-type inequality1 , i.e., there exists μ P L > 0 \mu_{\mathrm{PL}}>0 μ PL > 0 such that
∥ ∇ f ( x k ) ∥ 2 ≥ μ P L ( f ( x k ) − f l o w ) , (27) \lVert\nabla f(x_k)\rVert^2\ge\mu_{\mathrm{PL}}(f(x_k)-f_{\mathrm{low}}), \tag*{(27)} ∥ ∇ f ( x k ) ∥ 2 ≥ μ PL ( f ( x k ) − f low ) , (27)
where f l o w f_{\mathrm{low}} f low is a lower bound on { f ( x k ) } \{f(x_k)\} { f ( x k )} , i.e., f ( x k ) ≥ f l o w f(x_k)\ge f_{\mathrm{low}} f ( x k ) ≥ f low for all k k k .
Proposition 11 Assume that f ( x 0 ) > f l o w f(x_0)>f_{\mathrm{low}} f ( x 0 ) > f low , and that x k x_k x k is not stationary. Let (27) hold. Then, α k ≤ 1 / ( ρ L κ 1 μ P L ) \alpha_k\le1/(\rho_L\kappa_1\mu_{\mathrm{PL}}) α k ≤ 1/ ( ρ L κ 1 μ PL ) .
Proof. The rightmost inequality in (14) and Definition 1 imply
f ( x k ) − f ( x k + s k ) ≥ − ρ L α k ∇ f ( x k ) T d k ≥ ρ L κ 1 α k ∥ ∇ f ( x k ) ∥ 2 . f(x_k)-f(x_k+s_k) \ge-\rho_L\alpha_k\nabla f(x_k)^T d_k \ge\rho_L\kappa_1\alpha_k\lVert\nabla f(x_k)\rVert^2. f ( x k ) − f ( x k + s k ) ≥ − ρ L α k ∇ f ( x k ) T d k ≥ ρ L κ 1 α k ∥ ∇ f ( x k ) ∥ 2 .
Thus, (27) yields
α k ≤ f ( x k ) − f ( x k + s k ) ρ L κ 1 ∥ ∇ f ( x k ) ∥ 2 ≤ f ( x k ) − f l o w ρ L κ 1 ∥ ∇ f ( x k ) ∥ 2 ≤ 1 ρ L κ 1 μ P L . \alpha_k\le\frac{f(x_k)-f(x_k+s_k)}{\rho_L\kappa_1\lVert\nabla f(x_k)\rVert^2}\le\frac{f(x_k)-f_{\mathrm{low}}}{\rho_L\kappa_1\lVert\nabla f(x_k)\rVert^2}\le\frac{1}{\rho_L\kappa_1\mu_{\mathrm{PL}}}. α k ≤ ρ L κ 1 ∥ ∇ f ( x k ) ∥ 2 f ( x k ) − f ( x k + s k ) ≤ ρ L κ 1 ∥ ∇ f ( x k ) ∥ 2 f ( x k ) − f low ≤ ρ L κ 1 μ PL 1 .
In view of Proposition 10 , we may accept s k s_k s k without checking whether ρ k ≥ η 1 \rho_k\ge\eta_1 ρ k ≥ η 1 , and, in that instance, we leave σ k \sigma_k σ k unchanged.
Convergence Analysis
The main differences between Algorithm 4.1 and [15 Algorithm 4.1] are that (5) holds as an equality, whereas only ξ k , c p ≥ 1 2 ν k − 1 ∥ s k , c p ∥ 2 \xi_{k,\mathrm{cp}} \ge\frac{1}{2}\nu_k^{-1}\lVert s_{k,\mathrm{cp}}\rVert^2 ξ k , cp ≥ 2 1 ν k − 1 ∥ s k , cp ∥ 2 holds in the presence of a nonsmooth term, and Proposition 1 is less demanding than [15 Proposition 3.7] . Because h = 0 h=0 h = 0 in (1), the model ψ = 0 \psi=0 ψ = 0 satisfies [15 Model Assumptions 4.1–4.3] immediately, and [15 Problem Assumption 4.1] reduces to f ∈ C 1 f \in C^1 f ∈ C 1 . Because the Cauchy step simplifies to s k , c p ( ν k ) = − ν k ∇ f ( x k ) s_{k,\mathrm{cp}}(\nu_k)=-\nu_k\nabla f(x_k) s k , cp ( ν k ) = − ν k ∇ f ( x k ) , the stationarity measure of Diouane et al. [15 ] reduces exactly to the gradient norm:
ν k − 1 / 2 ξ k , c p 1 / 2 = ν k − 1 / 2 ( ν k ∥ ∇ f ( x k ) ∥ 2 ) 1 / 2 = ∥ ∇ f ( x k ) ∥ . (28) \nu_k^{-1/2}\xi_{k,\mathrm{cp}}^{1/2}=\nu_k^{-1/2}\left(\nu_k\lVert\nabla f(x_k)\rVert^2\right)^{1/2}=\lVert\nabla f(x_k)\rVert. \tag*{(28)} ν k − 1/2 ξ k , cp 1/2 = ν k − 1/2 ( ν k ∥ ∇ f ( x k ) ∥ 2 ) 1/2 = ∥ ∇ f ( x k )∥ . (28)
The only remaining assumption for global convergence concerns the growth of { B k } \{B_k\} { B k } , and corresponds to [15 Model Assumption 4.4] .
Model Assumption 1 The sequence { B k } \{B_k\} { B k } satisfies
∑ k = 0 ∞ 1 1 + max 0 ≤ j ≤ k ∥ B j ∥ = + ∞ . \sum_{k=0}^{\infty}\frac{1}{1+\max_{0\le j\le k}\lVert B_j\rVert}=+\infty. k = 0 ∑ ∞ 1 + max 0 ≤ j ≤ k ∥ B j ∥ 1 = + ∞.
Model Assumption 1 holds whenever { B k } \{B_k\} { B k } is bounded, or grows sufficiently slowly with k k k . We can now state the main convergence result.
Theorem 1 (15, Theorems 5.6 and 5.9) Let f ∈ C 1 f\in C^1 f ∈ C 1 be bounded below, and { B k } \{B_k\} { B k } satisfy Model Assumption 1 . Assume that s k s_k s k satisfies (9) with a constant τ > 0 \tau>0 τ > 0 independent of k k k . Then, the sequence of iterates generated by Algorithm 4.1 satisfies
lim inf k → ∞ ∥ ∇ f ( x k ) ∥ = 0. (29) \liminf_{k\to\infty}\lVert\nabla f(x_k)\rVert=0. \tag*{(29)} k → ∞ lim inf ∥ ∇ f ( x k )∥ = 0. (29) If Algorithm 4.1 generates only finitely many successful iterations, the boundedness assumption on f f f can be removed, and there exists x ⋆ ∈ R n x^\star\in\mathbb{R}^n x ⋆ ∈ R n such that x k = x ⋆ x_k=x^\star x k = x ⋆ for all large enough k k k , and ∇ f ( x ⋆ ) = 0 \nabla f(x^\star)=0 ∇ f ( x ⋆ ) = 0 .
Proof. By (28), the stationarity measure of Diouane et al. [15 ] reduces to ∥ ∇ f ( x k ) ∥ \lVert\nabla f(x_k)\rVert ∥ ∇ f ( x k )∥ . By assumption, s k s_k s k satisfies (9), which coincides with the sufficient decrease condition of [15 Proposition 3.7] . Since Model Assumption 1 coincides with [15 Model Assumption 4.4] , the results follow from [15 Theorems 5.6 and 5.9] . □ \square □
The Cauchy decrease condition (9) is satisfied by each subproblem solver under the assumptions stated in § 6 .
To establish worst-case evaluation complexity bounds, Diouane et al. [15 ] additionally make a Lipschitz-continuity assumption on ∇ f \nabla f ∇ f . We expand on these bounds in § 8 , distinguishing progress along positive- and nonpositive-curvature directions.
Structured Worst-Case Complexity
The algorithm of Diouane et al. [15 ] results in a worst-case iteration complexity in O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) under the assumption that ∇ f \nabla f ∇ f is Lipschitz continuous and { B k } \{B_k\} { B k } remains bounded. However, close examination of their analysis reveals that Lipschitz continuity is not necessary, but that Problem Assumption 1 below is sufficient. Thus, the same bound applies to Algorithm 4.1 under the same assumptions.
As we now show, the iteration complexity bound can be refined to distinguish between iterations in which a nonpositive curvature direction was identified and those in which a positive curvature direction was identified. We show that the former contribute O ( ε − 3 / 2 ) O(\varepsilon^{-3/2}) O ( ε − 3/2 ) terms to the overall complexity bound, and that the asymptotic order of those terms deteriorates with the quality of the Hessian curvature approximation along the step. We do so by correcting the analysis of Liu and Roosta [39 ] , which contains an error. Because positive curvature directions contribute O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) terms to the complexity bound, the tightness of the bound established in [15 ] shows that there exists f f f satisfying the assumptions below, and for which O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) iterations are necessary to achieve ∥ ∇ f ( x k ) ∥ ≤ ε \|\nabla f(x_k)\| \le\varepsilon ∥∇ f ( x k ) ∥ ≤ ε . Thus, contrary to claims in [39 ] , the overall complexity bound cannot be O ( ε − 3 / 2 ) O(\varepsilon^{-3/2}) O ( ε − 3/2 ) . However, we show below that the overall complexity bound can be decomposed according to the contributions of positive- and nonpositive-curvature accepted steps. Moreover, we exhibit an example for which the bound O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) is attained, and one for which the bound O ( ε − 3 / 2 ) O(\varepsilon^{-3/2}) O ( ε − 3/2 ) is attained.
We denote by S \mathcal{S} S the set of successful iterations, and partition it according to the curvature along the step:
S : = { k ∈ N ∣ ρ k ≥ η 1 } , S > 0 : = { k ∈ S ∣ s k T ( B k + σ k I ) s k > 0 } , S ≤ 0 : = S ∖ S > 0 . \mathcal{S} := \{k \in\mathbb{N} \mid\rho_k \ge\eta_1\}, \qquad\mathcal{S}_{>0} := \{k \in\mathcal{S} \mid s_k^{T}(B_k+\sigma_k I)s_k > 0\}, \qquad\mathcal{S}_{\le0} := \mathcal{S} \setminus\mathcal{S}_{>0}. S := { k ∈ N ∣ ρ k ≥ η 1 } , S > 0 := { k ∈ S ∣ s k T ( B k + σ k I ) s k > 0 } , S ≤ 0 := S ∖ S > 0 .
Problem Assumption 1 There exists L g ≥ 0 L_g \ge0 L g ≥ 0 such that, for all k ∈ N k \in\mathbb{N} k ∈ N ,
∣ f ( x k + 1 ) − ( f ( x k ) + ∇ f ( x k ) T s k ) ∣ ≤ 1 2 L g ∥ s k ∥ 2 , \left|f(x_{k+1})-\left(f(x_k)+\nabla f(x_k)^T s_k\right)\right| \le\frac{1}{2}L_g\|s_k\|^2, f ( x k + 1 ) − ( f ( x k ) + ∇ f ( x k ) T s k ) ≤ 2 1 L g ∥ s k ∥ 2 ,
where x k x_k x k and s k s_k s k are the iterate and step generated at iteration k k k of Algorithm 4.1 .
For completeness, we begin by restating the decrease along directions of positive curvature as established by Diouane et al. [15 ] . Their proof does not depend on boundedness of { B k } \{B_k\} { B k } . We only require the result below on successful iterations where a positive-curvature step is computed.
We implicitly assume that ∣ S ∣ |\mathcal{S}| ∣ S ∣ is infinite for otherwise, the final iterate can be shown to be stationary [15 Theorem 6.3] . The proof of the following result is classic and constitutes the first part of the proof of Diouane et al. [15 Theorem 6.4] .
Proposition 12 For k ∈ S > 0 k \in\mathcal{S}_{>0} k ∈ S > 0 ,
f ( x k ) − f ( x k + 1 ) ≥ η 1 τ v k ∥ ∇ f ( x k ) ∥ 2 . f(x_k)-f(x_{k+1}) \ge\eta_1\tau v_k\|\nabla f(x_k)\|^2. f ( x k ) − f ( x k + 1 ) ≥ η 1 τ v k ∥∇ f ( x k ) ∥ 2 . Proof. By definition of ρ k \rho_k ρ k , the identity x k + 1 = x k + s k x_{k+1}=x_k+s_k x k + 1 = x k + s k , (5) and (9) yield
f ( x k ) − f ( x k + 1 ) ≥ η 1 ξ ( x k , σ k ) ≥ η 1 τ ξ c p ( x k , v k ) ≥ η 1 τ v k ∥ ∇ f ( x k ) ∥ 2 . f(x_k)-f(x_{k+1}) \ge\eta_1\xi(x_k,\sigma_k) \ge\eta_1\tau\xi_{\mathrm{cp}}(x_k,v_k) \ge\eta_1\tau v_k\|\nabla f(x_k)\|^2. f ( x k ) − f ( x k + 1 ) ≥ η 1 ξ ( x k , σ k ) ≥ η 1 τ ξ cp ( x k , v k ) ≥ η 1 τ v k ∥∇ f ( x k ) ∥ 2 .
Proposition 12 contradicts [39 Lemma 8] , where the authors use MINRES to compute s k s_k s k . Indeed, the decrease achieved along positive curvature directions is entirely independent of MINRES’s nonpositive-curvature detection abilities. Below, we show an example where the bound given by Proposition 12 is attained, even though (21) is solved exactly, which suggests an error in [39 Lemma 8] .
To quantify the objective decrease along nonpositive-curvature directions, we require the following assumption.
Problem Assumption 2 f f f is C 2 C^2 C 2 and there exists L H ≥ 0 L_H \ge0 L H ≥ 0 such that, for all k ∈ S ≤ 0 k \in\mathcal{S}_{\le0} k ∈ S ≤ 0 ,
∣ f ( x k + 1 ) − ( f ( x k ) + ∇ f ( x k ) T s k + 1 2 s k T ∇ 2 f ( x k ) s k ) ∣ ≤ 1 3 ! L H ∥ s k ∥ 3 , \left|f(x_{k+1})-\left(f(x_k)+\nabla f(x_k)^T s_k+\frac{1}{2}s_k^T\nabla^2 f(x_k)s_k\right)\right| \le\frac{1}{3!}L_H\lVert s_k\rVert^3, f ( x k + 1 ) − ( f ( x k ) + ∇ f ( x k ) T s k + 2 1 s k T ∇ 2 f ( x k ) s k ) ≤ 3 ! 1 L H ∥ s k ∥ 3 , where x k x_k x k and s k s_k s k are the iterate and step generated at iteration k k k of Algorithm 4.1.
Although Problem Assumptions 1 and 2 are not assumptions on the problem alone, their interest resides in the facts that they are weaker than local or global Lipschitz continuity, and that they allow for the construction of examples that attain the worst-case complexity bounds. We develop such examples in § 9 and § 10 .
In addition, we require model Hessians to match the objective Hessian sufficiently along the step using the same assumption as in [19 ] . Note that the latter is significantly weaker than that used by Lim and Roosta [37 ] , who impose a uniform bound of the form ∥ ∇ 2 f ( x k ) − B k ∥ ≤ δ \lVert\nabla^2 f(x_k)-B_k\rVert\le\delta ∥ ∇ 2 f ( x k ) − B k ∥ ≤ δ where δ > 0 \delta> 0 δ > 0 .
Model Assumption 2 There exist C H > 0 C_H > 0 C H > 0 and 0 < ζ ≤ 1 0 < \zeta\le1 0 < ζ ≤ 1 such that, for all k ∈ S ≤ 0 k \in\mathcal{S}_{\le0} k ∈ S ≤ 0 ,
∥ ( ∇ 2 f ( x k ) − B k ) s k ∥ ≤ C H ∥ s k ∥ 1 + ζ , \lVert(\nabla^2 f(x_k)-B_k)s_k\rVert\le C_H\lVert s_k\rVert^{1+\zeta}, ∥( ∇ 2 f ( x k ) − B k ) s k ∥ ≤ C H ∥ s k ∥ 1 + ζ , where x k x_k x k and s k s_k s k are the iterate and step generated at iteration k k k of Algorithm 4.1.
The following result corrects [39 Lemma 9] and generalizes it to the case of inexact Hessian.
Theorem 2 Let Problem Assumption 2 and Model Assumption 2 be satisfied. Let k ∈ S ≤ 0 k \in\mathcal{S}_{\le0} k ∈ S ≤ 0 and assume that ρ U < κ 1 / κ 2 \rho_U < \kappa_1/\kappa_2 ρ U < κ 1 / κ 2 . Then,
f ( x k ) − f ( x k + 1 ) ≥ ρ L κ 1 min ( c 1 ∥ ∇ f ( x k ) ∥ 3 / 2 , c 2 ∥ ∇ f ( x k ) ∥ 2 + ζ 1 + ζ ) , f(x_k)-f(x_{k+1}) \ge\rho_L\kappa_1\min\left(c_1\lVert\nabla f(x_k)\rVert^{3/2},c_2\lVert\nabla f(x_k)\rVert^{\frac{2+\zeta}{1+\zeta}}\right), f ( x k ) − f ( x k + 1 ) ≥ ρ L κ 1 min ( c 1 ∥ ∇ f ( x k ) ∥ 3/2 , c 2 ∥ ∇ f ( x k ) ∥ 1 + ζ 2 + ζ ) , where
c 1 : = 3 ( κ 1 − κ 2 ρ U ) L H κ 2 3 , c 2 : = ( κ 1 − κ 2 ρ U C H κ 2 2 + ζ ) 1 1 + ζ . c_1 := \sqrt{\frac{3(\kappa_1-\kappa_2\rho_U)}{L_H\kappa_2^3}}, \qquad c_2 := \left(\frac{\kappa_1-\kappa_2\rho_U}{C_H\kappa_2^{2+\zeta}}\right)^{\frac{1}{1+\zeta}}. c 1 := L H κ 2 3 3 ( κ 1 − κ 2 ρ U ) , c 2 := ( C H κ 2 2 + ζ κ 1 − κ 2 ρ U ) 1 + ζ 1 .
Proof. Because s k s_k s k is accepted, x k + 1 = x k + s k x_{k+1}=x_k+s_k x k + 1 = x k + s k . By Definitions 1 and 2 , Problem Assumption 2 , Model Assumption 2 , and s k = α k d k s_k=\alpha_kd_k s k = α k d k ,
f ( x k + 1 ) − f ( x k ) ≤ ∇ f ( x k ) T s k + 1 2 s k T B k s k + 1 2 s k T ( ∇ 2 f ( x k ) − B k ) s k + 1 3 ! L H ∥ s k ∥ 3 ≤ − κ 1 α k ∥ ∇ f ( x k ) ∥ 2 + 1 2 C H κ 2 2 + ζ α k 2 + ζ ∥ ∇ f ( x k ) ∥ 2 + ζ + 1 3 ! L H κ 2 3 α k 3 ∥ ∇ f ( x k ) ∥ 3 . \begin{aligned}
f(x_{k+1})-f(x_k)
&\le\nabla f(x_k)^T s_k+\frac{1}{2}s_k^T B_k s_k+\frac{1}{2}s_k^T(\nabla^2 f(x_k)-B_k)s_k+\frac{1}{3!}L_H\lVert s_k\rVert^3\\
&\le-\kappa_1\alpha_k\lVert\nabla f(x_k)\rVert^2+\frac{1}{2}C_H\kappa_2^{2+\zeta}\alpha_k^{2+\zeta}\lVert\nabla f(x_k)\rVert^{2+\zeta}+\frac{1}{3!}L_H\kappa_2^3\alpha_k^3\lVert\nabla f(x_k)\rVert^3.
\end{aligned} f ( x k + 1 ) − f ( x k ) ≤ ∇ f ( x k ) T s k + 2 1 s k T B k s k + 2 1 s k T ( ∇ 2 f ( x k ) − B k ) s k + 3 ! 1 L H ∥ s k ∥ 3 ≤ − κ 1 α k ∥ ∇ f ( x k ) ∥ 2 + 2 1 C H κ 2 2 + ζ α k 2 + ζ ∥ ∇ f ( x k ) ∥ 2 + ζ + 3 ! 1 L H κ 2 3 α k 3 ∥ ∇ f ( x k ) ∥ 3 .
The left-hand side inequality of the Armijo-Goldstein conditions combines with (13) to yield − κ 2 ρ U α k ∥ ∇ f ( x k ) ∥ 2 ≤ ρ U α k ∇ f ( x k ) T d k ≤ f ( x k + 1 ) − f ( x k ) -\kappa_{2}\rho_{U}\alpha_{k}\|\nabla f(x_{k})\|^{2}\leq\rho_{U}\alpha_{k}\nabla f(x_{k})^{T}d_{k}\leq f(x_{k+1})-f(x_{k}) − κ 2 ρ U α k ∥∇ f ( x k ) ∥ 2 ≤ ρ U α k ∇ f ( x k ) T d k ≤ f ( x k + 1 ) − f ( x k ) . We combine the latter inequality with the above to obtain
− κ 2 ρ U α k ∥ ∇ f ( x k ) ∥ 2 ≤ − κ 1 α k ∥ ∇ f ( x k ) ∥ 2 + 1 2 C H κ 2 2 + ζ α k 2 + ζ ∥ ∇ f ( x k ) ∥ 2 + ζ + 1 3 ! L H κ 2 3 α k 3 ∥ ∇ f ( x k ) ∥ 3 , -\kappa_{2}\rho_{U}\alpha_{k}\|\nabla f(x_{k})\|^{2}\leq
-\kappa_{1}\alpha_{k}\|\nabla f(x_{k})\|^{2}+\frac{1}{2}C_{H}\kappa_{2}^{2+\zeta}\alpha_{k}^{2+\zeta}\|\nabla f(x_{k})\|^{2+\zeta}+\frac{1}{3!}L_{H}\kappa_{2}^{3}\alpha_{k}^{3}\|\nabla f(x_{k})\|^{3}, − κ 2 ρ U α k ∥∇ f ( x k ) ∥ 2 ≤ − κ 1 α k ∥∇ f ( x k ) ∥ 2 + 2 1 C H κ 2 2 + ζ α k 2 + ζ ∥∇ f ( x k ) ∥ 2 + ζ + 3 ! 1 L H κ 2 3 α k 3 ∥∇ f ( x k ) ∥ 3 ,
which simplifies, after dividing by α k ∥ ∇ f ( x k ) ∥ 2 \alpha_{k}\|\nabla f(x_{k})\|^{2} α k ∥∇ f ( x k ) ∥ 2 , to
( κ 1 − κ 2 ρ U ) ≤ 1 3 ! L H κ 2 3 α k 2 ∥ ∇ f ( x k ) ∥ + 1 2 C H κ 2 2 + ζ α k 1 + ζ ∥ ∇ f ( x k ) ∥ ζ . (30) (\kappa_{1}-\kappa_{2}\rho_{U})\leq\frac{1}{3!}L_{H}\kappa_{2}^{3}\alpha_{k}^{2}\|\nabla f(x_{k})\|+\frac{1}{2}C_{H}\kappa_{2}^{2+\zeta}\alpha_{k}^{1+\zeta}\|\nabla f(x_{k})\|^{\zeta}. \tag*{(30)} ( κ 1 − κ 2 ρ U ) ≤ 3 ! 1 L H κ 2 3 α k 2 ∥∇ f ( x k ) ∥ + 2 1 C H κ 2 2 + ζ α k 1 + ζ ∥∇ f ( x k ) ∥ ζ . (30)
By assumption, κ 1 − κ 2 ρ U > 0 \kappa_{1}-\kappa_{2}\rho_{U}>0 κ 1 − κ 2 ρ U > 0 . There are two possible regimes. Firstly, if 1 3 ! L H κ 2 3 α k 2 ∥ ∇ f ( x k ) ∥ ≥ 1 2 C H κ 2 2 + ζ α k 1 + ζ ∥ ∇ f ( x k ) ∥ ζ \frac{1}{3!}L_{H}\kappa_{2}^{3}\alpha_{k}^{2}\|\nabla f(x_{k})\|\geq\frac{1}{2}C_{H}\kappa_{2}^{2+\zeta}\alpha_{k}^{1+\zeta}\|\nabla f(x_{k})\|^{\zeta} 3 ! 1 L H κ 2 3 α k 2 ∥∇ f ( x k ) ∥ ≥ 2 1 C H κ 2 2 + ζ α k 1 + ζ ∥∇ f ( x k ) ∥ ζ , (30) yields
( κ 1 − κ 2 ρ U ) ≤ 1 3 ! L H κ 2 3 α k 2 ∥ ∇ f ( x k ) ∥ ⟺ α k ≥ c 1 ∥ ∇ f ( x k ) ∥ − 1 / 2 . (\kappa_{1}-\kappa_{2}\rho_{U})\leq\frac{1}{3!}L_{H}\kappa_{2}^{3}\alpha_{k}^{2}\|\nabla f(x_{k})\|\quad\Longleftrightarrow\quad\alpha_{k}\geq c_{1}\|\nabla f(x_{k})\|^{-1/2}. ( κ 1 − κ 2 ρ U ) ≤ 3 ! 1 L H κ 2 3 α k 2 ∥∇ f ( x k ) ∥ ⟺ α k ≥ c 1 ∥∇ f ( x k ) ∥ − 1/2 .
Secondly, if 1 3 ! L H κ 2 3 α k 2 ∥ ∇ f ( x k ) ∥ < 1 2 C H κ 2 2 + ζ α k 1 + ζ ∥ ∇ f ( x k ) ∥ ζ \frac{1}{3!}L_{H}\kappa_{2}^{3}\alpha_{k}^{2}\|\nabla f(x_{k})\|<\frac{1}{2}C_{H}\kappa_{2}^{2+\zeta}\alpha_{k}^{1+\zeta}\|\nabla f(x_{k})\|^{\zeta} 3 ! 1 L H κ 2 3 α k 2 ∥∇ f ( x k ) ∥ < 2 1 C H κ 2 2 + ζ α k 1 + ζ ∥∇ f ( x k ) ∥ ζ , (30) yields
( κ 1 − κ 2 ρ U ) ≤ C H κ 2 2 + ζ α k 1 + ζ ∥ ∇ f ( x k ) ∥ ζ ⟺ α k ≥ c 2 ∥ ∇ f ( x k ) ∥ − ζ 1 + ζ . (\kappa_{1}-\kappa_{2}\rho_{U})\leq C_{H}\kappa_{2}^{2+\zeta}\alpha_{k}^{1+\zeta}\|\nabla f(x_{k})\|^{\zeta}\quad\Longleftrightarrow\quad\alpha_{k}\geq c_{2}\|\nabla f(x_{k})\|^{-\frac{\zeta}{1+\zeta}}. ( κ 1 − κ 2 ρ U ) ≤ C H κ 2 2 + ζ α k 1 + ζ ∥∇ f ( x k ) ∥ ζ ⟺ α k ≥ c 2 ∥∇ f ( x k ) ∥ − 1 + ζ ζ .
In both cases,
α k ≥ min ( c 1 ∥ ∇ f ( x k ) ∥ − 1 / 2 , c 2 ∥ ∇ f ( x k ) ∥ − ζ 1 + ζ ) . \alpha_{k}\geq\min\left(c_{1}\|\nabla f(x_{k})\|^{-1/2},\ c_{2}\|\nabla f(x_{k})\|^{-\frac{\zeta}{1+\zeta}}\right). α k ≥ min ( c 1 ∥∇ f ( x k ) ∥ − 1/2 , c 2 ∥∇ f ( x k ) ∥ − 1 + ζ ζ ) .
We substitute the latter bound on α k \alpha_{k} α k into the Armijo condition, i.e., the right-hand side inequality of (14) , and use Definition 1 to obtain
f ( x k + 1 ) − f ( x k ) ≤ ρ L α k ∇ f ( x k ) T d k ≤ − ρ L κ 1 α k ∥ ∇ f ( x k ) ∥ 2 . f(x_{k+1})-f(x_{k})\leq\rho_{L}\alpha_{k}\nabla f(x_{k})^{T}d_{k}\leq-\rho_{L}\kappa_{1}\alpha_{k}\|\nabla f(x_{k})\|^{2}. f ( x k + 1 ) − f ( x k ) ≤ ρ L α k ∇ f ( x k ) T d k ≤ − ρ L κ 1 α k ∥∇ f ( x k ) ∥ 2 .
The identity 2 − ζ / ( 1 + ζ ) = ( 2 + ζ ) / ( 1 + ζ ) 2-\zeta/(1+\zeta)=(2+\zeta)/(1+\zeta) 2 − ζ / ( 1 + ζ ) = ( 2 + ζ ) / ( 1 + ζ ) yields the desired result. □ \square □
Theorem 2 implicitly assumes that the step is not reset to the Cauchy step on Algorithm 4.1 of Algorithm 4.1 , which is a safe assumption if θ 2 \theta_{2} θ 2 is chosen large enough, given the second part of Definition 1.
The proof of Theorem 2 simplifies when the curvature along the step is exact and gives a tighter bound.
Corollary 1. Problem Assumption 2 hold and assume that for all k k k , s k T B k s k = s k T ∇ 2 f ( x k ) s k s_{k}^{T}B_{k}s_{k}=s_{k}^{T}\nabla^{2}f(x_{k})s_{k} s k T B k s k = s k T ∇ 2 f ( x k ) s k , as would happen, e.g., if B k = ∇ 2 f ( x k ) B_{k}=\nabla^{2}f(x_{k}) B k = ∇ 2 f ( x k ) . Assume that at iteration k k k , a direction d k d_{k} d k of nonpositive curvature is identified at Algorithm 4.1 of Algorithm 4.1 , and that ρ U < κ 1 / κ 2 \rho_{U}<\kappa_{1}/\kappa_{2} ρ U < κ 1 / κ 2 . Finally, assume that the corresponding step s k = α k d k s_{k}=\alpha_{k}d_{k} s k = α k d k is accepted. Then,
f ( x k ) − f ( x k + 1 ) ≥ ρ L κ 1 c 3 ∥ ∇ f ( x k ) ∥ 3 / 2 , c 3 : = 3 ! ( κ 1 − κ 2 ρ U ) L H κ 2 3 . f(x_{k})-f(x_{k+1})\geq\rho_{L}\kappa_{1}c_{3}\|\nabla f(x_{k})\|^{3/2},\qquad c_{3}:=\sqrt{\frac{3!(\kappa_{1}-\kappa_{2}\rho_{U})}{L_{H}\kappa_{2}^{3}}}. f ( x k ) − f ( x k + 1 ) ≥ ρ L κ 1 c 3 ∥∇ f ( x k ) ∥ 3/2 , c 3 := L H κ 2 3 3 ! ( κ 1 − κ 2 ρ U ) .
Proof. We follow the logic of the proof of Theorem 2, but the terms involving ζ \zeta ζ are absent. We obtain directly the bound
α k ≥ c 3 ∥ ∇ f ( x k ) ∥ − 1 / 2 . \alpha_k \ge c_3 \lVert\nabla f(x_k) \rVert^{-1/2}. α k ≥ c 3 ∥ ∇ f ( x k ) ∥ − 1/2 .
The same logic then yields the result. □ \square □
For any 0 < ζ < 1 0 < \zeta< 1 0 < ζ < 1 , 2 + ζ 1 + ζ > 3 2 \frac{2+\zeta}{1+\zeta} > \frac{3}{2} 1 + ζ 2 + ζ > 2 3 . Hence, when ∥ ∇ f ( x k ) ∥ \lVert\nabla f(x_k) \rVert ∥ ∇ f ( x k )∥ is sufficiently small, the term in ∥ ∇ f ( x k ) ∥ 2 + ζ 1 + ζ \lVert\nabla f(x_k) \rVert^{\frac{2+\zeta}{1+\zeta}} ∥ ∇ f ( x k ) ∥ 1 + ζ 2 + ζ achieves the minimum in Theorem 2. As a consequence, any degree of inexactness in the curvature approximation deteriorates the worst-case complexity bound relative to the case where the curvature is exact. The optimal O ( ε − 3 / 2 ) O(\varepsilon^{-3/2}) O ( ε − 3/2 ) complexity along directions of nonpositive curvature is recovered only when ζ = 1 \zeta= 1 ζ = 1 (as shown in Corollary 1) or when the curvature approximation is exact.
Let ε > 0 \varepsilon> 0 ε > 0 . We are interested in finding the smallest k ε k_\varepsilon k ε such that ∥ ∇ f ( x k ε − 1 ) ∥ > ε \lVert\nabla f(x_{k_\varepsilon-1}) \rVert> \varepsilon ∥ ∇ f ( x k ε − 1 )∥ > ε and ∥ ∇ f ( x k ε ) ∥ ≤ ε \lVert\nabla f(x_{k_\varepsilon}) \rVert\le\varepsilon ∥ ∇ f ( x k ε )∥ ≤ ε . Because Algorithm 4.1 generates iterates by searching along directions of nonpositive and positive curvature, we define the sets
S > 0 ( ε ) : = { k < k ε ∣ ρ k ≥ η 1 and s k T ( B k + σ k I ) s k > 0 } (31) \mathcal{S}_{>0}(\varepsilon) := \{k < k_\varepsilon\mid\rho_k \ge\eta_1 \text{ and } s_k^T(B_k+\sigma_k I)s_k > 0\} \tag*{(31)} S > 0 ( ε ) := { k < k ε ∣ ρ k ≥ η 1 and s k T ( B k + σ k I ) s k > 0 } (31)
S ≤ 0 ( ε ) : = { k < k ε ∣ ρ k ≥ η 1 and s k T ( B k + σ k I ) s k ≤ 0 } (32) \mathcal{S}_{\le0}(\varepsilon) := \{k < k_\varepsilon\mid\rho_k \ge\eta_1 \text{ and } s_k^T(B_k+\sigma_k I)s_k \le0\} \tag*{(32)} S ≤ 0 ( ε ) := { k < k ε ∣ ρ k ≥ η 1 and s k T ( B k + σ k I ) s k ≤ 0 } (32)
U ( ε ) : = { k < k ε ∣ ρ k < η 1 } , (33) \mathcal{U}(\varepsilon) := \{k < k_\varepsilon\mid\rho_k < \eta_1\}, \tag*{(33)} U ( ε ) := { k < k ε ∣ ρ k < η 1 } , (33)
respectively the sets of successful iterations on which positive and nonpositive curvature was detected, and the set of unsuccessful iterations. We also define
S ( ε ) : = S > 0 ( ε ) ∪ ˙ S ≤ 0 ( ε ) , (34) \mathcal{S}(\varepsilon) := \mathcal{S}_{>0}(\varepsilon) \mathbin{\dot{\cup}} \mathcal{S}_{\le0}(\varepsilon), \tag*{(34)} S ( ε ) := S > 0 ( ε ) ∪ ˙ S ≤ 0 ( ε ) , (34)
where ∪ ˙ \mathbin{\dot{\cup}} ∪ ˙ denotes the disjoint union. Clearly, ∣ S ( ε ) ∣ = ∣ S > 0 ( ε ) ∣ + ∣ S ≤ 0 ( ε ) ∣ |\mathcal{S}(\varepsilon)| = |\mathcal{S}_{>0}(\varepsilon)| + |\mathcal{S}_{\le0}(\varepsilon)| ∣ S ( ε ) ∣ = ∣ S > 0 ( ε ) ∣ + ∣ S ≤ 0 ( ε ) ∣ .
Theorem 2 readily lets us bound ∣ S ≤ 0 ( ε ) ∣ |\mathcal{S}_{\le0}(\varepsilon)| ∣ S ≤ 0 ( ε ) ∣ as follows.
Theorem 3 Let Problem Assumption 2 and Model Assumption 2 be satisfied. Assume further that f f f is bounded below by f l o w f_{\mathrm{low}} f low . Then,
∣ S ≤ 0 ( ε ) ∣ ≤ f ( x 0 ) − f l o w ρ L κ 1 min ( c 1 ε 3 / 2 , c 2 ε 2 + ζ 1 + ζ ) . |\mathcal{S}_{\le0}(\varepsilon)| \le\frac{f(x_0)-f_{\mathrm{low}}}{\rho_L\kappa_1 \min\left(c_1\varepsilon^{3/2},c_2\varepsilon^{\frac{2+\zeta}{1+\zeta}}\right)}. ∣ S ≤ 0 ( ε ) ∣ ≤ ρ L κ 1 min ( c 1 ε 3/2 , c 2 ε 1 + ζ 2 + ζ ) f ( x 0 ) − f low . where c 1 c_1 c 1 and c 2 c_2 c 2 are as in Theorem 2.
Proof. Let k ∈ S ≤ 0 ( ε ) k \in\mathcal{S}_{\le0}(\varepsilon) k ∈ S ≤ 0 ( ε ) . By Theorem 2, f ( x k ) − f ( x k + 1 ) ≥ ρ L κ 1 min ( c 1 ε 3 / 2 , c 2 ε 2 + ζ 1 + ζ ) f(x_k)-f(x_{k+1}) \ge\rho_L\kappa_1 \min\left(c_1\varepsilon^{3/2},c_2\varepsilon^{\frac{2+\zeta}{1+\zeta}}\right) f ( x k ) − f ( x k + 1 ) ≥ ρ L κ 1 min ( c 1 ε 3/2 , c 2 ε 1 + ζ 2 + ζ ) . We sum those inequalities over S ≤ 0 ( ε ) \mathcal{S}_{\le0}(\varepsilon) S ≤ 0 ( ε ) and obtain
f ( x 0 ) − f l o w ≥ ∑ k ∈ S ≤ 0 ( ε ) ( f ( x k ) − f ( x k + 1 ) ) ≥ ∣ S ≤ 0 ( ε ) ∣ ρ L κ 1 min ( c 1 ε 3 / 2 , c 2 ε 2 + ζ 1 + ζ ) . \begin{aligned}
f(x_0)-f_{\mathrm{low}} \ge\sum_{k\in\mathcal{S}_{\le0}(\varepsilon)} \left(f(x_k)-f(x_{k+1})\right) \\
&\ge|\mathcal{S}_{\le0}(\varepsilon)|\rho_L\kappa_1 \min\left(c_1\varepsilon^{3/2},c_2\varepsilon^{\frac{2+\zeta}{1+\zeta}}\right).
\end{aligned} f ( x 0 ) − f low ≥ k ∈ S ≤ 0 ( ε ) ∑ ( f ( x k ) − f ( x k + 1 ) ) ≥ ∣ S ≤ 0 ( ε ) ∣ ρ L κ 1 min ( c 1 ε 3/2 , c 2 ε 1 + ζ 2 + ζ ) .
□ \square □
Under the stronger assumptions of Corollary 1, the bound in Theorem 3 becomes
∣ S ≤ 0 ( ε ) ∣ ≤ f ( x 0 ) − f l o w ρ L κ 1 c 3 ε − 3 / 2 . |\mathcal{S}_{\leq0}(\varepsilon)| \leq\frac{f(x_0)-f_{\mathrm{low}}}{\rho_L\kappa_1c_3}\varepsilon^{-3/2}. ∣ S ≤ 0 ( ε ) ∣ ≤ ρ L κ 1 c 3 f ( x 0 ) − f low ε − 3/2 .
Diouane et al. [15 ] make two additional assumptions, which we only require on iterations in S > 0 \mathcal{S}_{>0} S > 0 . The first assumption concerns adequacy between f ( x k ) f(x_k) f ( x k ) and φ ( ⋅ ; x k ) \varphi(\cdot;x_k) φ ( ⋅ ; x k ) , and states that there exists κ m > 0 \kappa_m>0 κ m > 0 such that for all k ∈ S > 0 k\in\mathcal{S}_{>0} k ∈ S > 0 ,
∣ f ( x k + s k ) − φ ( s k ; x k ) ∣ ≤ κ m ( 1 + ∥ B k ∥ ) ∥ s k ∥ 2 . |f(x_k+s_k)-\varphi(s_k;x_k)|\leq\kappa_m(1+\|B_k\|)\|s_k\|^2. ∣ f ( x k + s k ) − φ ( s k ; x k ) ∣ ≤ κ m ( 1 + ∥ B k ∥ ) ∥ s k ∥ 2 .
By Problem Assumption 1 and the definition of φ ( ⋅ ; x k ) \varphi(\cdot;x_k) φ ( ⋅ ; x k ) , the previous inequality is always satisfied with κ m = 1 2 max ( 1 , L g ) \kappa_m=\frac{1}{2}\max(1,L_g) κ m = 2 1 max ( 1 , L g ) . The second concerns the growth rate of { B k } \{B_k\} { B k } and is necessary to quantify the decay of ν k \nu_k ν k in the bound of Proposition 12 .
Model Assumption 3 There exist μ > 0 \mu>0 μ > 0 and 0 ≤ p ≤ 1 0\leq p\leq1 0 ≤ p ≤ 1 such that, for all k ∈ N k\in\mathbb{N} k ∈ N ,
∥ B k ∥ ≤ μ ( 1 + ∣ S > 0 , k − 1 ∣ p ) , \|B_k\|\leq\mu(1+|\mathcal{S}_{>0,k-1}|^p), ∥ B k ∥ ≤ μ ( 1 + ∣ S > 0 , k − 1 ∣ p ) , where S > 0 , k = { 0 ≤ j ≤ k ∣ j ∈ S > 0 } \mathcal{S}_{>0,k}=\{0\leq j\leq k\mid j\in\mathcal{S}_{>0}\} S > 0 , k = { 0 ≤ j ≤ k ∣ j ∈ S > 0 } and S > 0 , − 1 = ∅ \mathcal{S}_{>0,-1}=\varnothing S > 0 , − 1 = ∅ .
The classic assumption, which requires { B k } \{B_k\} { B k } to be bounded, corresponds to p = 0 p=0 p = 0 in Model Assumption 3. However, any value 0 ≤ p ≤ 1 0\leq p\leq1 0 ≤ p ≤ 1 is allowed to capture the growth of { B k } \{B_k\} { B k } . A similar assumption was first formulated by Leconte and Orban [31 ] in the context of trust-region methods. Model Assumption 3 is compatible with Problem Assumption 2 and Model Assumption 2. However, in our complexity analysis, they are used in different situations; the first applies along positive-curvature steps while the other two apply along nonpositive-curvature steps.
We are now in position to establish the following tight bound.
Proposition 13 (15, Theorem 6.4) Let Problem Assumption 1 and Model Assumption 3 be satisfied. Assume further that f f f is bounded below by f l o w f_{\mathrm{low}} f low . Then,
∣ S > 0 ( ε ) ∣ ≤ { ( ( 1 − p ) κ s ε − 2 + 1 ) 1 / ( 1 − p ) − 1 if 0 ≤ p < 1 , exp ( κ s ε − 2 ) − 1 if p = 1 , |\mathcal{S}_{>0}(\varepsilon)|\leq
\begin{cases}
\left((1-p)\kappa_s\varepsilon^{-2}+1\right)^{1/(1-p)}-1 & \text{if }0\leq p<1,\\
\exp(\kappa_s\varepsilon^{-2})-1 & \text{if }p=1,
\end{cases} ∣ S > 0 ( ε ) ∣ ≤ { ( ( 1 − p ) κ s ε − 2 + 1 ) 1/ ( 1 − p ) − 1 exp ( κ s ε − 2 ) − 1 if 0 ≤ p < 1 , if p = 1 , where
κ s : = ( f ( x 0 ) − f l o w ) ( b max + 2 μ ( 1 + b max ) ) η 1 θ 1 τ , \kappa_s:=\frac{(f(x_0)-f_{\mathrm{low}})(b_{\max}+2\mu(1+b_{\max}))}{\eta_1\theta_1\tau}, κ s := η 1 θ 1 τ ( f ( x 0 ) − f low ) ( b m a x + 2 μ ( 1 + b m a x )) , b max : = max ( σ 0 ( 1 + ∥ B 0 ∥ ) − 1 , 2 κ m γ 2 / ( 1 − η 2 ) ) . b_{\max}:=\max\left(\sigma_0(1+\|B_0\|)^{-1},2\kappa_m\gamma_2/(1-\eta_2)\right). b m a x := max ( σ 0 ( 1 + ∥ B 0 ∥ ) − 1 , 2 κ m γ 2 / ( 1 − η 2 ) ) .
Finally, Diouane et al. [15 Theorem 6.5] establish that
∣ U ( ε ) ∣ ≤ log γ 1 ( b max / σ 0 ) + ∣ log γ 1 ( γ 3 ) ∣ ∣ S ( ε ) ∣ + log γ 1 ( 1 + μ ( 1 + ∣ S ( ε ) ∣ p ) ) . (35) |\mathcal{U}(\varepsilon)|\leq\log_{\gamma_1}(b_{\max}/\sigma_0)+|\log_{\gamma_1}(\gamma_3)||\mathcal{S}(\varepsilon)|+\log_{\gamma_1}(1+\mu(1+|\mathcal{S}(\varepsilon)|^p)). \tag*{(35)} ∣ U ( ε ) ∣ ≤ log γ 1 ( b m a x / σ 0 ) + ∣ log γ 1 ( γ 3 ) ∣∣ S ( ε ) ∣ + log γ 1 ( 1 + μ ( 1 + ∣ S ( ε ) ∣ p )) . (35)
Theorem 3 and Proposition 13 show that the overall complexity bound contains terms in ε − 2 \varepsilon^{-2} ε − 2 driven by successful iterations along positive-curvature steps, and terms in ε − 3 / 2 + ε − ( 2 + ζ ) / ( 1 + ζ ) \varepsilon^{-3/2}+\varepsilon^{-(2+\zeta)/(1+\zeta)} ε − 3/2 + ε − ( 2 + ζ ) / ( 1 + ζ ) driven by successful iterations along nonpositive-curvature steps. Therefore, the worst-case complexity of Algorithm 4.1 remains in ε − 2 \varepsilon^{-2} ε − 2 , whether or not MINRES is used to compute steps, because no special property of MINRES helps improve that bound along positive-curvature steps. In that sense, the bound reported in [39 ] is misleading and erroneous. Indeed, as shown in the next section, there exists f f f satisfying our assumptions and a choice of B k B_k B k such that every step in Algorithm 4.1 is a positive-curvature step, every step is computed exactly, every iteration is very successful, and therefore, such that the total number of iterations attains ε − 2 \varepsilon^{-2} ε − 2 .
Slow Convergence of Algorithm R2N in the Absence of Nonpositive Curvature
We exhibit an example on which Algorithm 4.1 performs exactly a number of successful iterations of the asymptotic order given in Proposition 13 before finding an approximately stationary point. The example is directly inspired from similar examples in [16 , 31 ] , and covers the cases of bounded and unbounded model Hessians. Because the construction of such an example uses well-established results, we refer the reader to [16 , 31 ] for the details.
Let 0 < ε ≤ 1 2 0 < \varepsilon\le\frac{1}{2} 0 < ε ≤ 2 1 . We set 0 ≤ p < 1 0 \le p < 1 0 ≤ p < 1 and k ε : = ⌈ ε − 2 / ( 1 − p ) ⌉ k_\varepsilon:= \lceil\varepsilon^{-2/(1-p)} \rceil k ε := ⌈ ε − 2/ ( 1 − p ) ⌉ . The case p = 1 p = 1 p = 1 can be handled using an example similar to that in [16 ] . For k = 0 , … , k ε k = 0,\ldots,k_\varepsilon k = 0 , … , k ε , we set
w k : = k ε − k k ε , g k : = − ε ( 1 + w k ) , B k : = ( k + 1 ) p . w_k := \frac{k_\varepsilon-k}{k_\varepsilon}, \qquad g_k := -\varepsilon(1+w_k), \qquad B_k := (k+1)^p. w k := k ε k ε − k , g k := − ε ( 1 + w k ) , B k := ( k + 1 ) p .
It is clear that ∣ g k ∣ > ε |g_k| > \varepsilon ∣ g k ∣ > ε for k = 0 , … , k ε − 1 k = 0,\ldots,k_\varepsilon-1 k = 0 , … , k ε − 1 , that ∣ g k ε ∣ = ε |g_{k_\varepsilon}| = \varepsilon ∣ g k ε ∣ = ε , and that B k + σ k ≻ 0 B_k+\sigma_k \succ0 B k + σ k ≻ 0 for all k = 0 , … , k ε k = 0,\ldots,k_\varepsilon k = 0 , … , k ε . No nonpositive-curvature is ever detected.
The step is computed exactly as
s k = − ( B k + σ k ) − 1 g k = ε ( 1 + w k ) ( k + 1 ) p + σ k , k = 0 , … , k ε − 1. s_k = -(B_k+\sigma_k)^{-1}g_k = \frac{\varepsilon(1+w_k)}{(k+1)^p+\sigma_k}, \qquad k = 0,\ldots,k_\varepsilon-1. s k = − ( B k + σ k ) − 1 g k = ( k + 1 ) p + σ k ε ( 1 + w k ) , k = 0 , … , k ε − 1.
The iterates and function values are generated as x k + 1 : = x k + s k x_{k+1} := x_k+s_k x k + 1 := x k + s k , and
f 0 : = 4 ( 1 + ε 2 1 − p ) 1 − p , f k + 1 : = f k + g k s k = f k − g k 2 ( k + 1 ) p + σ k , k = 0 , … , k ε − 1. (36) f_0 := \frac{4(1+\varepsilon^{\frac{2}{1-p}})}{1-p}, \qquad f_{k+1} := f_k+g_ks_k = f_k-\frac{g_k^2}{(k+1)^p+\sigma_k}, \qquad k = 0,\ldots,k_\varepsilon-1. \tag*{(36)} f 0 := 1 − p 4 ( 1 + ε 1 − p 2 ) , f k + 1 := f k + g k s k = f k − ( k + 1 ) p + σ k g k 2 , k = 0 , … , k ε − 1. (36)
Lemma 1 The definitions above ensure that there exists κ f > 0 \kappa_f > 0 κ f > 0 such that
(1). f k ≥ 0 f_k \ge0 f k ≥ 0 for all k ∈ { 0 , … , k ε } k \in\{0,\ldots,k_\varepsilon\} k ∈ { 0 , … , k ε } , and { f k } \{f_k\} { f k } is strictly decreasing;
(2). for k ∈ { 0 , … , k ε − 1 } k \in\{0,\ldots,k_\varepsilon-1\} k ∈ { 0 , … , k ε − 1 } , ∣ g k + 1 − g k ∣ ≤ κ f s k |g_{k+1}-g_k| \le\kappa_f s_k ∣ g k + 1 − g k ∣ ≤ κ f s k ;
(3). for all k ∈ { 0 , … , k ε − 1 } k \in\{0,\ldots,k_\varepsilon-1\} k ∈ { 0 , … , k ε − 1 } , ∣ f k + 1 − ( f k + g k s k ) ∣ ≤ s k 2 |f_{k+1}-(f_k+g_ks_k)| \le s_k^2 ∣ f k + 1 − ( f k + g k s k ) ∣ ≤ s k 2 .
Proof. It follows from (36) that { f k } \{f_k\} { f k } is strictly decreasing. To show f k ≥ 0 f_k \ge0 f k ≥ 0 , we sum the total descent from f 0 f_0 f 0 :
f 0 − f k = ∑ i = 0 k − 1 g i 2 ( i + 1 ) p + σ i ≤ ∑ i = 0 k − 1 ε 2 ( 1 + w i ) 2 ( i + 1 ) p . f_0-f_k = \sum_{i=0}^{k-1}\frac{g_i^2}{(i+1)^p+\sigma_i} \le\sum_{i=0}^{k-1}\frac{\varepsilon^2(1+w_i)^2}{(i+1)^p}. f 0 − f k = i = 0 ∑ k − 1 ( i + 1 ) p + σ i g i 2 ≤ i = 0 ∑ k − 1 ( i + 1 ) p ε 2 ( 1 + w i ) 2 .
Because ( 1 + w i ) 2 ≤ 4 (1+w_i)^2 \le4 ( 1 + w i ) 2 ≤ 4 ,
f 0 − f k ≤ 4 ε 2 ∑ i = 0 k − 1 ( i + 1 ) − p ≤ 4 ε 2 ∫ 0 k x − p d x = 4 ε 2 1 − p k 1 − p . f_0-f_k \le4\varepsilon^2\sum_{i=0}^{k-1}(i+1)^{-p} \le4\varepsilon^2\int_0^k x^{-p}\,dx = \frac{4\varepsilon^2}{1-p}k^{1-p}. f 0 − f k ≤ 4 ε 2 i = 0 ∑ k − 1 ( i + 1 ) − p ≤ 4 ε 2 ∫ 0 k x − p d x = 1 − p 4 ε 2 k 1 − p .
Since k ≤ k ε = ⌈ ε − 2 / ( 1 − p ) ⌉ ≤ ε − 2 / ( 1 − p ) + 1 k \le k_\varepsilon=\lceil\varepsilon^{-2/(1-p)}\rceil\le\varepsilon^{-2/(1-p)}+1 k ≤ k ε = ⌈ ε − 2/ ( 1 − p ) ⌉ ≤ ε − 2/ ( 1 − p ) + 1 , k 1 − p ≤ ( ε − 2 / ( 1 − p ) + 1 ) 1 − p k^{1-p}\le(\varepsilon^{-2/(1-p)}+1)^{1-p} k 1 − p ≤ ( ε − 2/ ( 1 − p ) + 1 ) 1 − p . Thus, f 0 − f k ≤ 4 ( 1 + ε 2 / ( 1 − p ) ) / ( 1 − p ) = f 0 f_0-f_k\le4(1+\varepsilon^{2/(1-p)})/(1-p)=f_0 f 0 − f k ≤ 4 ( 1 + ε 2/ ( 1 − p ) ) / ( 1 − p ) = f 0 . Hence, f k ≥ 0 f_k\ge0 f k ≥ 0 .
For the second part, ∣ g k + 1 − g k ∣ = ε / k ε |g_{k+1}-g_k|=\varepsilon/k_\varepsilon ∣ g k + 1 − g k ∣ = ε / k ε . Because the step size 0 < s k < 2 ε / ( k + 1 ) p 0<s_k<2\varepsilon/(k+1)^p 0 < s k < 2 ε / ( k + 1 ) p , there exists κ f \kappa_f κ f such that the interpolation bound is satisfied.
Finally, (36) yields ∣ f k + 1 − f k − g k s k ∣ = 0 |f_{k+1}-f_k-g_ks_k|=0 ∣ f k + 1 − f k − g k s k ∣ = 0 .
Theorem 4 The definitions above ensure existence of f : R → R f:\mathbb{R}\to\mathbb{R} f : R → R continuously differentiable for which exactly k ε = ⌈ ε − 2 / ( 1 − p ) ⌉ k_\varepsilon=\lceil\varepsilon^{-2/(1-p)}\rceil k ε = ⌈ ε − 2/ ( 1 − p ) ⌉ iterations are necessary to produce x k ε x_{k_\varepsilon} x k ε such that ∥ ∇ f ( x k ε ) ∥ ≤ ε \lVert\nabla f(x_{k_\varepsilon})\rVert\le\varepsilon ∥ ∇ f ( x k ε )∥ ≤ ε . Furthermore, along the sequence of iterates generated, we only encounter strictly positive curvature, solve the subproblem exactly, and each iteration is very successful.
Proof. Existence of f f f that interpolates the values f k f_k f k such that ∇ f \nabla f ∇ f interpolates the values g k g_k g k is guaranteed by Lemma 1 and [31 Proposition 6] .
We now show that every iteration is very successful. The predicted reduction is
ϕ ( 0 ; x k ) − ϕ ( s k ; x k ) = − g k s k − 1 2 s k 2 B k = g k 2 ( k + 1 ) p + σ k − 1 2 ( g k ( k + 1 ) p + σ k ) 2 ( k + 1 ) p = g k 2 ( k + 1 ) p + σ k ( 1 − 1 2 ( k + 1 ) p ( k + 1 ) p + σ k ) ≤ g k 2 ( k + 1 ) p + σ k = f k − f k + 1 , \begin{aligned}
\phi(0;x_k)-\phi(s_k;x_k)&=-g_ks_k-\frac{1}{2}s_k^2B_k\\
&=\frac{g_k^2}{(k+1)^p+\sigma_k}-\frac{1}{2}\left(\frac{g_k}{(k+1)^p+\sigma_k}\right)^2(k+1)^p\\
&=\frac{g_k^2}{(k+1)^p+\sigma_k}\left(1-\frac{1}{2}\frac{(k+1)^p}{(k+1)^p+\sigma_k}\right)\\
&\le\frac{g_k^2}{(k+1)^p+\sigma_k}=f_k-f_{k+1},
\end{aligned} ϕ ( 0 ; x k ) − ϕ ( s k ; x k ) = − g k s k − 2 1 s k 2 B k = ( k + 1 ) p + σ k g k 2 − 2 1 ( ( k + 1 ) p + σ k g k ) 2 ( k + 1 ) p = ( k + 1 ) p + σ k g k 2 ( 1 − 2 1 ( k + 1 ) p + σ k ( k + 1 ) p ) ≤ ( k + 1 ) p + σ k g k 2 = f k − f k + 1 ,
where the final value is precisely the actual reduction. Therefore, ρ k ≥ 1 > η 2 \rho_k\ge1>\eta_2 ρ k ≥ 1 > η 2 .
Figure 1 graphs f f f and f ′ f' f ′ over the interval covered by the iterates x k x_k x k . We set ε = 1 4 \varepsilon=\frac{1}{4} ε = 4 1 and p = 1 10 p=\frac{1}{10} p = 10 1 .
Figure 1. Graph of f f f and f ′ f' f ′ in the example of § 9 with ε = 1 4 \varepsilon=\frac{1}{4} ε = 4 1 , and p = 1 10 p=\frac{1}{10} p = 10 1 , which results in ⌈ ε − 2 / ( 1 − p ) ⌉ = 22 \lceil\varepsilon^{-2/(1-p)}\rceil=22 ⌈ ε − 2/ ( 1 − p ) ⌉ = 22 iterations. Circles indicate the 23 iterates x k x_k x k .
Slow Convergence of Algorithm 4.1 in the Presence of Nonpositive Curvature
We now exhibit an example on which Algorithm 4.1 performs exactly a number of successful iterations of the asymptotic order given in Theorem 3 before finding an approximate stationary point. The example is also inspired by similar examples in [16 , 31 ] , but adapted to account for the Armijo-Goldstein line search along nonpositive-curvature directions. Let 0 < ε ≤ 1 2 0<\varepsilon\le\frac{1}{2} 0 < ε ≤ 2 1 . We set k ε : = ⌈ ε − 3 / 2 ⌉ k_\varepsilon:=\lceil\varepsilon^{-3/2}\rceil k ε := ⌈ ε − 3/2 ⌉ . For k = 0 , … , k ε k=0,\ldots,k_\varepsilon k = 0 , … , k ε , we set
w k : = ( k ε − k ) / k ε , g k : = − ε ( 1 + w k ) , B k = − σ 0 < 0. w_k:=(k_\varepsilon-k)/k_\varepsilon,\qquad g_k:=-\varepsilon(1+w_k),\qquad B_k=-\sigma_0<0. w k := ( k ε − k ) / k ε , g k := − ε ( 1 + w k ) , B k = − σ 0 < 0.
It is clear that ∣ g k ∣ > ε |g_k|>\varepsilon ∣ g k ∣ > ε for k = 0 , … , k ε − 1 k=0,\ldots,k_\varepsilon-1 k = 0 , … , k ε − 1 , that ∣ g k ε ∣ = ε |g_{k_\varepsilon}|=\varepsilon ∣ g k ε ∣ = ε , and that B k + σ 0 = 0 B_k+\sigma_0=0 B k + σ 0 = 0 for all k = 0 , … , k ε k=0,\ldots,k_\varepsilon k = 0 , … , k ε . Because the example will ensure that σ k = σ 0 \sigma_k=\sigma_0 σ k = σ 0 for all k k k , nonpositive curvature is detected at every iteration. Because the model curvature is zero, the model φ ( ⋅ ; x k ) \varphi(\cdot;x_k) φ ( ⋅ ; x k ) is linear, so the algorithm takes the descent direction d k = − g k d_k=-g_k d k = − g k , which is simultaneously the Cauchy direction and a direction of nonpositive curvature. Our construction depends on two constants c 0 > 0 c_0>0 c 0 > 0 , and ρ ˉ ∈ ( 0 , 1 ) \bar{\rho}\in(0,1) ρ ˉ ∈ ( 0 , 1 ) . Define
α k : = c 0 ∣ g k ∣ − 1 / 2 , s k = α k d k = c 0 ∣ g k ∣ 1 / 2 , k = 0 , … , k ε − 1. \alpha_k:=c_0|g_k|^{-1/2},\qquad s_k=\alpha_kd_k=c_0|g_k|^{1/2},\qquad k=0,\ldots,k_\varepsilon-1. α k := c 0 ∣ g k ∣ − 1/2 , s k = α k d k = c 0 ∣ g k ∣ 1/2 , k = 0 , … , k ε − 1.
The iterates are generated as x k + 1 : = x k + s k x_{k+1}:=x_k+s_k x k + 1 := x k + s k . We set
f 0 : = ( 2 3 / 2 + 1 ) ρ ˉ c 0 , f k + 1 : = f k − ρ ˉ c 0 ∣ g k ∣ 3 / 2 , k = 0 , … , k ε − 1. (37) f_0:=(2^{3/2}+1)\bar{\rho}c_0,\qquad f_{k+1}:=f_k-\bar{\rho}c_0|g_k|^{3/2},\qquad k=0,\ldots,k_\varepsilon-1. \tag*{(37)} f 0 := ( 2 3/2 + 1 ) ρ ˉ c 0 , f k + 1 := f k − ρ ˉ c 0 ∣ g k ∣ 3/2 , k = 0 , … , k ε − 1. (37)
Finally, we arrange so the Hessian of the interpolant is H k : = − σ 0 H_k:=-\sigma_0 H k := − σ 0 , and we set B k = H k B_k=H_k B k = H k in the model.
Lemma 2 The definitions of g k g_k g k , s k s_k s k , H k H_k H k , and (37) ensure that there is κ f > 0 \kappa_f>0 κ f > 0 such that
(1). { f k } \{f_k\} { f k } is strictly decreasing and f k ≥ 0 f_k\geq0 f k ≥ 0 for all k ∈ { 0 , … , k ε } k\in\{0,\ldots,k_\varepsilon\} k ∈ { 0 , … , k ε } ;
(2). ∣ f k + 1 − ( f k + g k s k + 1 2 H k s k 2 ) ∣ ≤ κ f s k 3 |f_{k+1}-(f_k+g_ks_k+\frac{1}{2}H_ks_k^2)|\leq\kappa_fs_k^3 ∣ f k + 1 − ( f k + g k s k + 2 1 H k s k 2 ) ∣ ≤ κ f s k 3 for all k ∈ { 0 , … , k ε − 1 } k\in\{0,\ldots,k_\varepsilon-1\} k ∈ { 0 , … , k ε − 1 } ;
(3). ∣ g k + 1 − ( g k + H k s k ) ∣ ≤ κ f s k 2 |g_{k+1}-(g_k+H_ks_k)|\leq\kappa_fs_k^2 ∣ g k + 1 − ( g k + H k s k ) ∣ ≤ κ f s k 2 for all k ∈ { 0 , … , k ε − 1 } k\in\{0,\ldots,k_\varepsilon-1\} k ∈ { 0 , … , k ε − 1 } ;
(4). ∣ H k + 1 − H k ∣ ≤ κ f s k |H_{k+1}-H_k|\leq\kappa_fs_k ∣ H k + 1 − H k ∣ ≤ κ f s k for all k ∈ { 0 , … , k ε − 1 } k\in\{0,\ldots,k_\varepsilon-1\} k ∈ { 0 , … , k ε − 1 } .
Proof. It follows from (37) that { f k } \{f_k\} { f k } is strictly decreasing. By definition, f 0 > 0 f_0>0 f 0 > 0 . Let 0 < k ≤ k ε 0<k\leq k_\varepsilon 0 < k ≤ k ε . For i = 0 , … , k − 1 i=0,\ldots,k-1 i = 0 , … , k − 1 , ∣ g i ∣ ≤ 2 ε |g_i|\leq2\varepsilon ∣ g i ∣ ≤ 2 ε . Hence, because
f 0 − f k = ∑ i = 0 k − 1 ( f i − f i + 1 ) = ρ ˉ c 0 ∑ i = 0 k − 1 ∣ g i ∣ 3 / 2 ≤ ρ ˉ c 0 ( 2 ε ) 3 / 2 k ε ≤ ρ ˉ c 0 2 3 / 2 ( 1 + ε 3 / 2 ) ≤ ( 2 3 / 2 + 1 ) ρ ˉ c 0 = f 0 , \begin{aligned}
f_0-f_k=\sum_{i=0}^{k-1}(f_i-f_{i+1})=\bar{\rho}c_0\sum_{i=0}^{k-1}|g_i|^{3/2}\leq\bar{\rho}c_0(2\varepsilon)^{3/2}k_\varepsilon\leq\bar{\rho}c_0 2^{3/2}(1+\varepsilon^{3/2}) \\
&\leq(2^{3/2}+1)\bar{\rho}c_0=f_0,
\end{aligned} f 0 − f k = i = 0 ∑ k − 1 ( f i − f i + 1 ) = ρ ˉ c 0 i = 0 ∑ k − 1 ∣ g i ∣ 3/2 ≤ ρ ˉ c 0 ( 2 ε ) 3/2 k ε ≤ ρ ˉ c 0 2 3/2 ( 1 + ε 3/2 ) ≤ ( 2 3/2 + 1 ) ρ ˉ c 0 = f 0 ,
where we used the inequalities k ε ≤ ε − 3 / 2 + 1 k_\varepsilon\leq\varepsilon^{-3/2}+1 k ε ≤ ε − 3/2 + 1 , and ε 3 / 2 ≤ 2 − 3 / 2 \varepsilon^{3/2}\leq2^{-3/2} ε 3/2 ≤ 2 − 3/2 . Thus, f k ≥ 0 f_k\geq0 f k ≥ 0 , which establishes (1). For (2) , let 0 ≤ k < k ε 0 \le k < k_{\varepsilon} 0 ≤ k < k ε . Because g k < 0 g_k < 0 g k < 0 , s k = c 0 ∣ g k ∣ 1 / 2 s_k = c_0|g_k|^{1/2} s k = c 0 ∣ g k ∣ 1/2 , and H k = − σ 0 H_k = -\sigma_0 H k = − σ 0 , (37) yields
∣ f k + 1 − ( f k + g k s k + 1 2 H k s k 2 ) ∣ = ∣ − ρ ˉ c 0 ∣ g k ∣ 3 / 2 + c 0 ∣ g k ∣ 3 / 2 + 1 2 σ 0 s k 2 ∣ = ( 1 − ρ ˉ ) c 0 ∣ g k ∣ 3 / 2 + 1 2 σ 0 s k 2 = 1 − ρ ˉ c 0 2 s k 3 + 1 2 σ 0 s k 2 . \begin{aligned}
\left|f_{k+1} - \left(f_k + g_ks_k + \frac{1}{2}H_ks_k^2\right)\right| = \left|-\bar{\rho}c_0|g_k|^{3/2} + c_0|g_k|^{3/2} + \frac{1}{2}\sigma_0s_k^2\right| \\
&= (1-\bar{\rho})c_0|g_k|^{3/2} + \frac{1}{2}\sigma_0s_k^2 \\
&= \frac{1-\bar{\rho}}{c_0^2}s_k^3 + \frac{1}{2}\sigma_0s_k^2.
\end{aligned} f k + 1 − ( f k + g k s k + 2 1 H k s k 2 ) = − ρ ˉ c 0 ∣ g k ∣ 3/2 + c 0 ∣ g k ∣ 3/2 + 2 1 σ 0 s k 2 = ( 1 − ρ ˉ ) c 0 ∣ g k ∣ 3/2 + 2 1 σ 0 s k 2 = c 0 2 1 − ρ ˉ s k 3 + 2 1 σ 0 s k 2 .
Because ∣ g k ∣ > ε |g_k| > \varepsilon ∣ g k ∣ > ε , s k > c 0 ε 1 / 2 s_k > c_0\varepsilon^{1/2} s k > c 0 ε 1/2 , i.e., 1 < s k / ( c 0 ε ) 1 < s_k/(c_0\sqrt{\varepsilon}) 1 < s k / ( c 0 ε ) . We multiply both sides of the latter inequality by 1 2 σ 0 s k 2 \frac{1}{2}\sigma_0s_k^2 2 1 σ 0 s k 2 , and insert into the final equality above to obtain
∣ f k + 1 − ( f k + g k s k + 1 2 H k s k 2 ) ∣ < ( 1 − ρ ˉ c 0 2 + σ 0 2 c 0 ε ) s k 3 . \left|f_{k+1} - \left(f_k + g_ks_k + \frac{1}{2}H_ks_k^2\right)\right| < \left(\frac{1-\bar{\rho}}{c_0^2} + \frac{\sigma_0}{2c_0\sqrt{\varepsilon}}\right)s_k^3. f k + 1 − ( f k + g k s k + 2 1 H k s k 2 ) < ( c 0 2 1 − ρ ˉ + 2 c 0 ε σ 0 ) s k 3 .
We now turn to (3) . By construction, ∣ g k + 1 − g k ∣ = ε / k ε |g_{k+1}-g_k| = \varepsilon/k_{\varepsilon} ∣ g k + 1 − g k ∣ = ε / k ε . The definitions of s k s_k s k and H k H_k H k , and the inequality k ε ≥ ε − 3 / 2 k_{\varepsilon} \ge\varepsilon^{-3/2} k ε ≥ ε − 3/2 yield
∣ g k + 1 − ( g k + H k s k ) ∣ = ∣ g k + 1 − g k + σ 0 s k ∣ = ε k ε + σ 0 s k ≤ ε ε 3 / 2 + σ 0 s k . |g_{k+1}-(g_k+H_ks_k)| = |g_{k+1}-g_k+\sigma_0s_k| = \frac{\varepsilon}{k_{\varepsilon}}+\sigma_0s_k \le\varepsilon\varepsilon^{3/2}+\sigma_0s_k. ∣ g k + 1 − ( g k + H k s k ) ∣ = ∣ g k + 1 − g k + σ 0 s k ∣ = k ε ε + σ 0 s k ≤ ε ε 3/2 + σ 0 s k .
Since ∣ g k ∣ ≥ ε |g_k|\ge\varepsilon ∣ g k ∣ ≥ ε , and s k ≥ c 0 ε s_k\ge c_0\sqrt{\varepsilon} s k ≥ c 0 ε , i.e., ε ≤ s k 2 / c 0 2 \varepsilon\le s_k^2/c_0^2 ε ≤ s k 2 / c 0 2 . In addition, using an observation similar to that for part (2) , what precedes can be written 1 ≤ s k / ( c 0 ε ) 1\le s_k/(c_0\sqrt{\varepsilon}) 1 ≤ s k / ( c 0 ε ) , and we multiply both sides of the latter inequality by σ 0 s k \sigma_0s_k σ 0 s k to obtain σ 0 s k ≤ σ 0 s k 2 / ( c 0 ε ) \sigma_0s_k\le\sigma_0s_k^2/(c_0\sqrt{\varepsilon}) σ 0 s k ≤ σ 0 s k 2 / ( c 0 ε ) . Thus,
∣ g k + 1 − ( g k + H k s k ) ∣ ≤ ( ε 3 / 2 c 0 2 + σ 0 c 0 ε ) s k 2 . |g_{k+1}-(g_k+H_ks_k)| \le\left(\frac{\varepsilon^{3/2}}{c_0^2}+\frac{\sigma_0}{c_0\sqrt{\varepsilon}}\right)s_k^2. ∣ g k + 1 − ( g k + H k s k ) ∣ ≤ ( c 0 2 ε 3/2 + c 0 ε σ 0 ) s k 2 .
Finally, part (4) holds because H k = H k + 1 H_k=H_{k+1} H k = H k + 1 for all k k k .
The result follows with κ f : = max ( ε 3 / 2 c 0 2 + σ 0 c 0 ε , 1 − ρ ˉ c 0 2 + σ 0 2 c 0 ε ) \kappa_f := \max\left(\frac{\varepsilon^{3/2}}{c_0^2}+\frac{\sigma_0}{c_0\sqrt{\varepsilon}},\frac{1-\bar{\rho}}{c_0^2}+\frac{\sigma_0}{2c_0\sqrt{\varepsilon}}\right) κ f := max ( c 0 2 ε 3/2 + c 0 ε σ 0 , c 0 2 1 − ρ ˉ + 2 c 0 ε σ 0 ) .
Among others, Lemma 2 shows that Problem Assumption 2 holds. The next result establishes that our construction is consistent with Algorithm 4.1 .
Theorem 5 Assume ρ U > max ( ρ L , η 2 ) \rho_U > \max(\rho_L,\eta_2) ρ U > max ( ρ L , η 2 ) , γ 3 = 1 \gamma_3=1 γ 3 = 1 , and choose ρ ˉ ∈ ( max ( ρ L , η 2 ) , ρ U ) \bar{\rho}\in(\max(\rho_L,\eta_2),\rho_U) ρ ˉ ∈ ( max ( ρ L , η 2 ) , ρ U ) in (37) . Assume further that σ 0 \sigma_0 σ 0 and c 0 c_0 c 0 are chosen such that
σ 0 ≤ min ( θ 1 θ 2 2 , 2 ( ρ ˉ η 2 − 1 ) ) ε c 0 . \sigma_0 \le\min\left(\frac{\theta_1\theta_2}{2},2\left(\frac{\bar{\rho}}{\eta_2}-1\right)\right)\frac{\sqrt{\varepsilon}}{c_0}. σ 0 ≤ min ( 2 θ 1 θ 2 , 2 ( η 2 ρ ˉ − 1 ) ) c 0 ε . Then, the definitions of f k f_k f k , g k g_k g k , H k H_k H k , B k B_k B k , and s k s_k s k above ensure existence of f : R → R f:\mathbb{R}\to\mathbb{R} f : R → R with f ∈ C 2 f\in C^2 f ∈ C 2 whose gradient and Hessian satisfy Problem Assumption 1 and Problem Assumption 2, respectively, and for which exactly k ε = ⌈ ε − 3 / 2 ⌉ k_{\varepsilon}=\lceil\varepsilon^{-3/2}\rceil k ε = ⌈ ε − 3/2 ⌉ iterations of Algorithm 4.1 are necessary to produce x k ε x_{k_{\varepsilon}} x k ε such that ∣ ∇ f ( x k ε ) ∣ ≤ ε |\nabla f(x_{k_{\varepsilon}})|\le\varepsilon ∣∇ f ( x k ε ) ∣ ≤ ε . Along the sequence of iterates, nonpositive curvature is detected at every iteration, s k s_k s k is never reset to the Cauchy step, and every iteration is very successful.
Proof. Existence of f ∈ C 2 f \in C^2 f ∈ C 2 that interpolates the values f k f_k f k with ∇ f ( x k ) = g k \nabla f(x_k)=g_k ∇ f ( x k ) = g k and ∇ 2 f ( x k ) = H k \nabla^2 f(x_k)=H_k ∇ 2 f ( x k ) = H k follows from Lemma 2 and [16 ] , Theorem A.9.2. Because ∣ g k ∣ > ε |g_k|>\varepsilon ∣ g k ∣ > ε for k < k ε k<k_\varepsilon k < k ε and ∣ g k ε ∣ = ε |g_{k_\varepsilon}|=\varepsilon ∣ g k ε ∣ = ε , exactly k ε k_\varepsilon k ε iterations are required to reach the stopping criterion. Since B k + σ 0 = 0 B_k+\sigma_0=0 B k + σ 0 = 0 , the model φ ( ⋅ ; x k ) \varphi(\cdot;x_k) φ ( ⋅ ; x k ) is linear and any descent direction is a direction of nonpositive curvature. The algorithm therefore takes d k : = − g k d_k:=-g_k d k := − g k , which is simultaneously the Cauchy direction and gradient-related with κ 1 = κ 2 = 1 \kappa_1=\kappa_2=1 κ 1 = κ 2 = 1 , and performs the Armijo-Goldstein line search along d k d_k d k . Using g k d k = − ∣ g k ∣ 2 g_kd_k=-|g_k|^2 g k d k = − ∣ g k ∣ 2 and α k ∣ g k ∣ 2 = c 0 ∣ g k ∣ 3 / 2 \alpha_k|g_k|^2=c_0|g_k|^{3/2} α k ∣ g k ∣ 2 = c 0 ∣ g k ∣ 3/2 , the Armijo-Goldstein condition for α k : = c 0 ∣ g k ∣ − 1 / 2 \alpha_k:=c_0|g_k|^{-1/2} α k := c 0 ∣ g k ∣ − 1/2 reads
f k − ρ U c 0 ∣ g k ∣ 3 / 2 ≤ f k + 1 ≤ f k − ρ L c 0 ∣ g k ∣ 3 / 2 . f_k-\rho_Uc_0|g_k|^{3/2}\le f_{k+1}\le f_k-\rho_Lc_0|g_k|^{3/2}. f k − ρ U c 0 ∣ g k ∣ 3/2 ≤ f k + 1 ≤ f k − ρ L c 0 ∣ g k ∣ 3/2 .
By (35) and the fact that ρ ˉ ∈ [ ρ L , ρ U ] \bar{\rho}\in[\rho_L,\rho_U] ρ ˉ ∈ [ ρ L , ρ U ] , both inequalities hold and α k \alpha_k α k is admissible. Since g k T ( B k + σ 0 I ) g k = 0 g_k^T(B_k+\sigma_0I)g_k=0 g k T ( B k + σ 0 I ) g k = 0 , Algorithm 4.2 of Algorithm 4.2 sets α k , c p = θ 1 / ( ∥ B k ∥ + σ 0 ) = θ 1 / ( 2 σ 0 ) \alpha_{k,\mathrm{cp}}=\theta_1/(\|B_k\|+\sigma_0)=\theta_1/(2\sigma_0) α k , cp = θ 1 / ( ∥ B k ∥ + σ 0 ) = θ 1 / ( 2 σ 0 ) , so ∥ s k , c p ∥ = θ 1 ∣ g k ∣ / ( 2 σ 0 ) \|s_{k,\mathrm{cp}}\|=\theta_1|g_k|/(2\sigma_0) ∥ s k , cp ∥ = θ 1 ∣ g k ∣/ ( 2 σ 0 ) . The reset at Algorithm 4.1 of Algorithm 4.1 is triggered if ∥ s k ∥ > θ 2 ∥ s k , c p ∥ \|s_k\|>\theta_2\|s_{k,\mathrm{cp}}\| ∥ s k ∥ > θ 2 ∥ s k , cp ∥ , i.e., c 0 ∣ g k ∣ 1 / 2 > θ 1 θ 2 ∣ g k ∣ / ( 2 σ 0 ) c_0|g_k|^{1/2}>\theta_1\theta_2|g_k|/(2\sigma_0) c 0 ∣ g k ∣ 1/2 > θ 1 θ 2 ∣ g k ∣/ ( 2 σ 0 ) , i.e., 2 c 0 σ 0 > θ 1 θ 2 ∣ g k ∣ 1 / 2 2c_0\sigma_0>\theta_1\theta_2|g_k|^{1/2} 2 c 0 σ 0 > θ 1 θ 2 ∣ g k ∣ 1/2 . Because ∣ g k ∣ 1 / 2 ≥ ε |g_k|^{1/2}\ge\sqrt{\varepsilon} ∣ g k ∣ 1/2 ≥ ε , the initialization of σ 0 \sigma_0 σ 0 directly ensures 2 c 0 σ 0 ≤ θ 1 θ 2 ε ≤ θ 1 θ 2 ∣ g k ∣ 1 / 2 2c_0\sigma_0\le\theta_1\theta_2\sqrt{\varepsilon}\le\theta_1\theta_2|g_k|^{1/2} 2 c 0 σ 0 ≤ θ 1 θ 2 ε ≤ θ 1 θ 2 ∣ g k ∣ 1/2 for all k k k , so no reset occurs.
Because B k = − σ 0 B_k=-\sigma_0 B k = − σ 0 and s k = c 0 ∣ g k ∣ s_k=c_0|g_k| s k = c 0 ∣ g k ∣ , the predicted and actual reductions are
φ ( 0 ; x k ) − φ ( s k ; x k ) = − g k s k − 1 2 H k s k 2 = c 0 ∣ g k ∣ 3 / 2 + 1 2 σ 0 c 0 2 ∣ g k ∣ , \varphi(0;x_k)-\varphi(s_k;x_k)=-g_ks_k-\frac{1}{2}H_ks_k^2=c_0|g_k|^{3/2}+\frac{1}{2}\sigma_0c_0^2|g_k|, φ ( 0 ; x k ) − φ ( s k ; x k ) = − g k s k − 2 1 H k s k 2 = c 0 ∣ g k ∣ 3/2 + 2 1 σ 0 c 0 2 ∣ g k ∣ ,
f k − f k + 1 = ρ ˉ c 0 ∣ g k ∣ 3 / 2 . f_k-f_{k+1}=\bar{\rho}c_0|g_k|^{3/2}. f k − f k + 1 = ρ ˉ c 0 ∣ g k ∣ 3/2 .
Because ∣ g k ∣ 1 / 2 ≥ ε |g_k|^{1/2}\ge\sqrt{\varepsilon} ∣ g k ∣ 1/2 ≥ ε , ρ k = ρ ˉ 1 + 1 2 c 0 σ 0 ∣ g k ∣ − 1 / 2 ≥ ρ ˉ 1 + 1 2 c 0 σ 0 ε − 1 / 2 \rho_k=\frac{\bar{\rho}}{1+\frac{1}{2}c_0\sigma_0|g_k|^{-1/2}}\ge\frac{\bar{\rho}}{1+\frac{1}{2}c_0\sigma_0\varepsilon^{-1/2}} ρ k = 1 + 2 1 c 0 σ 0 ∣ g k ∣ − 1/2 ρ ˉ ≥ 1 + 2 1 c 0 σ 0 ε − 1/2 ρ ˉ . Our assumption on σ 0 \sigma_0 σ 0 guarantees that 1 2 c 0 σ 0 ε − 1 / 2 ≤ ρ ˉ / η 2 − 1 \frac{1}{2}c_0\sigma_0\varepsilon^{-1/2}\le\bar{\rho}/\eta_2-1 2 1 c 0 σ 0 ε − 1/2 ≤ ρ ˉ / η 2 − 1 , which gives ρ k ≥ η 2 \rho_k\ge\eta_2 ρ k ≥ η 2 at every iteration. Because we set γ 3 = 1 \gamma_3=1 γ 3 = 1 , the update rules of Algorithm 4.1 set σ k + 1 = σ k = σ 0 \sigma_{k+1}=\sigma_k=\sigma_0 σ k + 1 = σ k = σ 0 for all k k k , which confirms that the assumption σ k = σ 0 \sigma_k=\sigma_0 σ k = σ 0 is consistent.
Figure 2 graphs f f f and f ′ f' f ′ over the interval covered by the iterates x k x_k x k . We use the values ε = 1 4 \varepsilon=\frac{1}{4} ε = 4 1 , c 0 = 1 c_0=1 c 0 = 1 , σ 0 = 1 \sigma_0=1 σ 0 = 1 . The assumptions of Theorem 5 are satisfied by choosing any 0 < θ 1 < 1 0<\theta_1<1 0 < θ 1 < 1 , θ 2 = 4 / θ 1 \theta_2=4/\theta_1 θ 2 = 4/ θ 1 , 0 < η 1 ≤ η 2 < 1 2 0<\eta_1\le\eta_2<\frac{1}{2} 0 < η 1 ≤ η 2 < 2 1 , ρ ˉ = 2 η 2 \bar{\rho}=2\eta_2 ρ ˉ = 2 η 2 , 0 < ρ L ≤ η 2 0<\rho_L\le\eta_2 0 < ρ L ≤ η 2 , and ρ ˉ < ρ U < 1 \bar{\rho}<\rho_U<1 ρ ˉ < ρ U < 1 .
Figure 2. Graph of f f f and f ′ f' f ′ in the example of § 10 with ϵ = 1 4 \epsilon=\frac{1}{4} ϵ = 4 1 , which results in ϵ − 3 / 2 = 8 \epsilon^{-3/2}=8 ϵ − 3/2 = 8 iterations. We use σ 0 = c 0 = 1 \sigma_0=c_0=1 σ 0 = c 0 = 1 , and ρ ˉ = 0.095 = 2 η 2 \bar{\rho}=0.095=2\eta_2 ρ ˉ = 0.095 = 2 η 2 . Circles indicate the 9 iterates x k x_k x k .
On Figure 2 , observe that the steps are chosen so that the algorithm makes minimal progress in f ( x ) f(x) f ( x ) , and that negative curvature is observed at each iteration. The iterates are located just to the left of the local minima of f ′ f' f ′ , where f ′ f' f ′ is decreasing.
The interpolant is constructed using a piecewise Hermite spline of degree 5, which is C 2 C^2 C 2 . The domain is partitioned into the intervals [ x k , x k + 1 ] [x_k,x_{k+1}] [ x k , x k + 1 ] , k = 0 , … , k ε − 1 k=0,\ldots,k_\varepsilon-1 k = 0 , … , k ε − 1 , and the extra intervals [ x 0 − 1 , x 0 ] [x_0-1,x_0] [ x 0 − 1 , x 0 ] and [ x k ε , x k ε + 1 ] [x_{k_\varepsilon},x_{k_\varepsilon+1}] [ x k ε , x k ε + 1 ] . On each interval except the leftmost and rightmost intervals, the function value, first derivative, and second derivative match f k f_k f k , g k g_k g k , H k H_k H k at both endpoints. On the leftmost and rightmost intervals, these three quantities match the sequence at the interior endpoint, while the first and second derivatives vanish and the function value equals the adjacent f k f_k f k at the far endpoint. Outside all intervals, f f f equals f 0 f_0 f 0 on ( − ∞ , x 0 − 1 ) (-\infty,x_0-1) ( − ∞ , x 0 − 1 ) and f k ε f_{k_\varepsilon} f k ε on ( x k ε + 1 , + ∞ ) (x_{k_\varepsilon}+1,+\infty) ( x k ε + 1 , + ∞ ) . The next result gives the explicit Hermite interpolant.
Lemma 3 (Hermite Interpolation). For each interval [ x k , x k + 1 ] [x_k,x_{k+1}] [ x k , x k + 1 ] , the unique degree-5 polynomial π k ( x ) = ∑ i = 0 5 p i ( x − x k ) i \pi_k(x)=\sum_{i=0}^{5}p_i(x-x_k)^i π k ( x ) = ∑ i = 0 5 p i ( x − x k ) i satisfying
π k ( x k ) = f k , π k ′ ( x k ) = g k , π k ′ ′ ( x k ) = − σ 0 , π k ( x k + 1 ) = f k + 1 , π k ′ ( x k + 1 ) = g k + 1 , π k ′ ′ ( x k + 1 ) = − σ 0 , \begin{aligned}
\pi_k(x_k)&=f_k, & \pi_k'(x_k)&=g_k, & \pi_k''(x_k)&=-\sigma_0,\\
\pi_k(x_{k+1})&=f_{k+1}, & \pi_k'(x_{k+1})&=g_{k+1}, & \pi_k''(x_{k+1})&=-\sigma_0,
\end{aligned} π k ( x k ) π k ( x k + 1 ) = f k , = f k + 1 , π k ′ ( x k ) π k ′ ( x k + 1 ) = g k , = g k + 1 , π k ′′ ( x k ) π k ′′ ( x k + 1 ) = − σ 0 , = − σ 0 , has coefficients p 0 = f k p_0=f_k p 0 = f k , p 1 = g k p_1=g_k p 1 = g k , p 2 = − 1 2 σ 0 p_2=-\frac{1}{2}\sigma_0 p 2 = − 2 1 σ 0 , and
p 3 = 10 E f , k − 4 s k E g , k s k 3 , p 4 = − 15 E f , k + 7 s k E g , k s k 4 , p 5 = 6 E f , k − 3 s k E g , k s k 5 , p_3=\frac{10E_{f,k}-4s_kE_{g,k}}{s_k^3},\qquad p_4=\frac{-15E_{f,k}+7s_kE_{g,k}}{s_k^4},\qquad p_5=\frac{6E_{f,k}-3s_kE_{g,k}}{s_k^5}, p 3 = s k 3 10 E f , k − 4 s k E g , k , p 4 = s k 4 − 15 E f , k + 7 s k E g , k , p 5 = s k 5 6 E f , k − 3 s k E g , k , where E f , k ≔ f k + 1 − ( f k + g k s k − 1 2 σ 0 s k 2 ) E_{f,k}\coloneqq f_{k+1}-(f_k+g_ks_k-\frac{1}{2}\sigma_0s_k^2) E f , k : = f k + 1 − ( f k + g k s k − 2 1 σ 0 s k 2 ) and E g , k ≔ g k + 1 − ( g k − σ 0 s k ) E_{g,k}\coloneqq g_{k+1}-(g_k-\sigma_0s_k) E g , k : = g k + 1 − ( g k − σ 0 s k ) .
Proof. Set t = x − x k ∈ [ 0 , s k ] t=x-x_k\in[0,s_k] t = x − x k ∈ [ 0 , s k ] . At t = 0 t=0 t = 0 , we obtain p 0 = f k p_0=f_k p 0 = f k , p 1 = g k p_1=g_k p 1 = g k , and p 2 = − σ 0 / 2 p_2=-\sigma_0/2 p 2 = − σ 0 /2 . Setting u j ≔ p j + 3 s k j + 3 u_j\coloneqq p_{j+3}s_k^{j+3} u j : = p j + 3 s k j + 3 for j = 0 , 1 , 2 j=0,1,2 j = 0 , 1 , 2 , the boundary conditions at t = s k t=s_k t = s k reduce to
( 1 1 1 3 4 5 6 12 20 ) ( u 0 u 1 u 2 ) = ( E f , k s k E g , k 0 ) , \begin{pmatrix}
1&1&1\\
3&4&5\\
6&12&20
\end{pmatrix}
\begin{pmatrix}
u_0\\
u_1\\
u_2
\end{pmatrix}
=
\begin{pmatrix}
E_{f,k}\\
s_kE_{g,k}\\
0
\end{pmatrix}, 1 3 6 1 4 12 1 5 20 u 0 u 1 u 2 = E f , k s k E g , k 0 ,
where the third right-hand side vanishes because H k = − σ 0 H_k=-\sigma_0 H k = − σ 0 is constant. The coefficients given in the statement of the lemma solve the latter linear system. □ \square □
A Variant with Fast Local Convergence
In the vicinity of an isolated minimizer, we show below that all iterations are eventually very successful, i.e., ρ k ≥ η 2 \rho_k\ge\eta_2 ρ k ≥ η 2 . As stated, however, Algorithm 4.1 does not permit fast local convergence, because it prevents σ k \sigma_k σ k from decaying sufficiently fast. Variants have been proposed in the literature that enjoy fast local convergence and a favorable worst-case complexity bound. For instance, instead of updating σ k \sigma_k σ k as in Algorithm 4.1 , Bergou et al. [4 ] set σ k = μ k ∥ ∇ f ( x k ) ∥ 2 \sigma_k=\mu_k\lVert\nabla f(x_k)\rVert^2 σ k = μ k ∥ ∇ f ( x k ) ∥ 2 and update μ k \mu_k μ k as in Algorithm 4.1 . Bergou et al. [5 ] proceed similarly with σ k = μ k ∥ ∇ f ( x k ) ∥ \sigma_k=\mu_k\lVert\nabla f(x_k)\rVert σ k = μ k ∥ ∇ f ( x k )∥ .
We now examine a minimal change to Algorithm 4.1 that still allows us to obtain a worst-case complexity bound and permits fast local convergence. To that end, we modify the update of σ k \sigma_k σ k when ρ k ≥ η 2 \rho_k\ge\eta_2 ρ k ≥ η 2 as in Algorithm 10.1.
Algorithm 10.1 R2N with Fast Local Convergence.
Apply Algorithm 4.1 with the alternative update
σ k + 1 = γ 3 min ( σ k , ∥ ∇ f ( x k + 1 ) ∥ ) if ρ k ≥ η 2 \sigma_{k+1}=\gamma_3\min(\sigma_k,\lVert\nabla f(x_{k+1})\rVert)\quad\text{if}\quad\rho_k\ge\eta_2 σ k + 1 = γ 3 min ( σ k , ∥ ∇ f ( x k + 1 )∥) if ρ k ≥ η 2 in Algorithm 4.1 .
Proposition 13 is unaffected by the change in Algorithm 10.1. Indeed, [15 Theorem 6.2] continues to hold, and is the only prerequisite to [15 Theorem 6.4] . Similarly, Theorem 3 is also unaffected. In particular, lim inf ∥ ∇ f ( x k ) ∥ = 0 \liminf\lVert\nabla f(x_k)\rVert=0 lim inf ∥ ∇ f ( x k )∥ = 0 continues to hold. The role of the update of σ k \sigma_k σ k when ρ k ≥ η 2 \rho_k\ge\eta_2 ρ k ≥ η 2 in the complexity analysis is confined to (35) . We now seek a bound on ∣ U ( ε ) ∣ \lvert\mathcal{U}(\varepsilon)\rvert ∣ U ( ε )∣ for Algorithm 10.1. Unfortunately, the proof technique of [15 Theorem 6.5] no longer applies to the modified update.
We first state the following straightforward variation of [15 Lemma 6.1] .
Lemma 4 Let the assumptions of Proposition 13 and Theorem 3 be satisfied. Define b ~ s u c c : = 2 κ m / ( 1 − η 1 ) \widetilde b_{\mathrm{succ}}:=2\kappa_m/(1-\eta_1) b succ := 2 κ m / ( 1 − η 1 ) . If x k x_k x k is not stationary and σ k ( 1 + max 0 ≤ j ≤ k ∥ B j ∥ ) − 1 ≥ b ~ s u c c \sigma_k(1+\max_{0\le j\le k}\lVert B_j\rVert)^{-1}\ge\widetilde b_{\mathrm{succ}} σ k ( 1 + max 0 ≤ j ≤ k ∥ B j ∥ ) − 1 ≥ b succ , iteration k k k is successful.
The threshold b ~ s u c c \widetilde b_{\mathrm{succ}} b succ of Lemma 4 is used below to bound the total number of unsuccessful iterations.
Observe that necessarily, k ε ∈ S ( ε ) k_\varepsilon\in\mathcal{S}(\varepsilon) k ε ∈ S ( ε ) because ∥ ∇ f ( x k ε ) ∥ ≤ ε < ∥ ∇ f ( x k ε − 1 ) ∥ \lVert\nabla f(x_{k_\varepsilon})\rVert\le\varepsilon<\lVert\nabla f(x_{k_\varepsilon-1})\rVert ∥ ∇ f ( x k ε )∥ ≤ ε < ∥ ∇ f ( x k ε − 1 )∥ , and hence, x k ε − 1 ≠ x k ε x_{k_\varepsilon-1}\ne x_{k_\varepsilon} x k ε − 1 = x k ε . Let
S ( ε ) = { k 0 , k 1 , … , k t = k ε } (38) \mathcal{S}(\varepsilon)=\{k_0,k_1,\ldots,k_t=k_\varepsilon\} \tag*{(38)} S ( ε ) = { k 0 , k 1 , … , k t = k ε } (38)
be an enumeration of the successful iterations, where 0 ≤ k 0 < k 1 < ⋯ < k t 0\le k_0<k_1<\cdots<k_t 0 ≤ k 0 < k 1 < ⋯ < k t . The proof of the following result is inspired from that of [4 Lemma 3.3] .
Theorem 6 Under the assumptions of Proposition 13 and Theorem 3,
∣ U ( ε ) ∣ ≤ 1 + log γ 1 ( b ~ s u c c ( 1 + μ ) σ 0 ) + ∑ i = 0 t − 1 log γ 1 [ 1 γ 3 min ( σ k i , ε ) ] + ( ∣ S ( ε ) ∣ − 1 ) log γ 1 [ b ~ s u c c ( 1 + μ ( 1 + ( ∣ S ( ε ) ∣ − 1 ) ρ ) ) ] , \lvert\mathcal{U}(\varepsilon)\rvert\le1+\log_{\gamma_1}\left(\frac{\widetilde b_{\mathrm{succ}}(1+\mu)}{\sigma_0}\right)+\sum_{i=0}^{t-1}\log_{\gamma_1}\left[\frac{1}{\gamma_3\min(\sigma_{k_i},\varepsilon)}\right]+(\lvert\mathcal{S}(\varepsilon)\rvert-1)\log_{\gamma_1}\left[\widetilde b_{\mathrm{succ}}\left(1+\mu\left(1+(\lvert\mathcal{S}(\varepsilon)\rvert-1)^\rho\right)\right)\right], ∣ U ( ε )∣ ≤ 1 + log γ 1 ( σ 0 b succ ( 1 + μ ) ) + i = 0 ∑ t − 1 log γ 1 [ γ 3 min ( σ k i , ε ) 1 ] + (∣ S ( ε )∣ − 1 ) log γ 1 [ b succ ( 1 + μ ( 1 + (∣ S ( ε )∣ − 1 ) ρ ) ) ] , where b ~ s u c c \widetilde b_{\mathrm{succ}} b succ is defined in Lemma 4, and t t t is defined in (38) .
Proof. Let i ∈ { 0 , … , t − 1 } i\in\{0,\ldots,t-1\} i ∈ { 0 , … , t − 1 } , where t t t is defined in (38) . We proceed in two steps: firstly, we bound the number k i + 1 − k i − 1 k_{i+1}-k_i-1 k i + 1 − k i − 1 of unsuccessful iterations between two consecutive successful iterations, and secondly, we bound the number k 0 k_0 k 0 of unsuccessful iterations before the first successful iteration. For any unsuccessful iteration k ∈ { k i + 1 , … , k i + 1 − 1 } k \in\{k_i+1,\ldots,k_{i+1}-1\} k ∈ { k i + 1 , … , k i + 1 − 1 } , Lemma 4 implies
σ k ( 1 + max 0 ≤ j ≤ k ∥ B j ∥ ) − 1 < b ~ s u c c . \sigma_k\left(1+\max_{0\le j\le k}\lVert B_j\rVert\right)^{-1}<\tilde b_{\mathrm{succ}}. σ k ( 1 + 0 ≤ j ≤ k max ∥ B j ∥ ) − 1 < b ~ succ .
Algorithm 10.1 ensures that σ k + 1 ≥ γ 1 σ k \sigma_{k+1}\ge\gamma_1\sigma_k σ k + 1 ≥ γ 1 σ k when ρ k < η 1 \rho_k<\eta_1 ρ k < η 1 , σ k + 1 ≥ σ k \sigma_{k+1}\ge\sigma_k σ k + 1 ≥ σ k when η 1 ≤ ρ k < η 2 \eta_1\le\rho_k<\eta_2 η 1 ≤ ρ k < η 2 , and σ k + 1 = γ 3 min ( σ k , ∥ ∇ f ( x k + 1 ) ∥ ) \sigma_{k+1}=\gamma_3\min(\sigma_k,\lVert\nabla f(x_{k+1})\rVert) σ k + 1 = γ 3 min ( σ k , ∥ ∇ f ( x k + 1 )∥) when ρ k ≥ η 2 \rho_k\ge\eta_2 ρ k ≥ η 2 . Because ∥ ∇ f ( x k i + 1 ) ∥ > ε \lVert\nabla f(x_{k_i+1})\rVert>\varepsilon ∥ ∇ f ( x k i + 1 )∥ > ε ,
σ k ≥ γ 1 k − k i − 1 σ k i + 1 ≥ γ 1 k − k i − 1 γ 3 min ( σ k i , ∥ ∇ f ( x k i + 1 ) ∥ ) ≥ γ 1 k − k i − 1 γ 3 min ( σ k i , ε ) . \sigma_k\ge\gamma_1^{k-k_i-1}\sigma_{k_i+1}\ge\gamma_1^{k-k_i-1}\gamma_3\min(\sigma_{k_i},\lVert\nabla f(x_{k_i+1})\rVert)\ge\gamma_1^{k-k_i-1}\gamma_3\min(\sigma_{k_i},\varepsilon). σ k ≥ γ 1 k − k i − 1 σ k i + 1 ≥ γ 1 k − k i − 1 γ 3 min ( σ k i , ∥ ∇ f ( x k i + 1 )∥) ≥ γ 1 k − k i − 1 γ 3 min ( σ k i , ε ) .
We combine the two observations above with Model Assumption 3 and obtain
γ 1 k − k i − 1 γ 3 min ( σ k i , ε ) ≤ b ~ s u c c ( 1 + max 0 ≤ j ≤ k ∥ B j ∥ ) ≤ b ~ s u c c ( 1 + μ ( 1 + ∣ S > 0 , k ∣ p ) ) , \gamma_1^{k-k_i-1}\gamma_3\min(\sigma_{k_i},\varepsilon)\le\tilde b_{\mathrm{succ}}\left(1+\max_{0\le j\le k}\lVert B_j\rVert\right)\le\tilde b_{\mathrm{succ}}\left(1+\mu\left(1+\lvert\mathcal{S}_{>0,k}\rvert^p\right)\right), γ 1 k − k i − 1 γ 3 min ( σ k i , ε ) ≤ b ~ succ ( 1 + 0 ≤ j ≤ k max ∥ B j ∥ ) ≤ b ~ succ ( 1 + μ ( 1 + ∣ S > 0 , k ∣ p ) ) ,
where S > 0 , k \mathcal{S}_{>0,k} S > 0 , k is the set of successful iterations corresponding to positive-curvature steps up to iteration k k k . By (38) , ∣ S > 0 , k ∣ = i + 1 \lvert\mathcal{S}_{>0,k}\rvert=i+1 ∣ S > 0 , k ∣ = i + 1 . Thus,
k i + 1 − k i − 1 ≤ log γ 1 [ b ~ s u c c ( 1 + μ ( 1 + ( i + 1 ) p ) ) γ 3 min ( σ k i , ε ) ] . k_{i+1}-k_i-1\le\log_{\gamma_1}\left[\frac{\tilde b_{\mathrm{succ}}\left(1+\mu\left(1+(i+1)^p\right)\right)}{\gamma_3\min(\sigma_{k_i},\varepsilon)}\right]. k i + 1 − k i − 1 ≤ log γ 1 [ γ 3 min ( σ k i , ε ) b ~ succ ( 1 + μ ( 1 + ( i + 1 ) p ) ) ] .
We sum the above inequalities to bound the total number of unsuccessful iterations between iterations k 0 k_0 k 0 and k t k_t k t :
∑ i = 0 t − 1 k i + 1 − k i − 1 ≤ ∑ i = 0 t − 1 log γ 1 [ 1 γ 3 min ( σ k i , ε ) ] + ∑ i = 0 t − 1 log γ 1 [ b ~ s u c c ( 1 + μ ( 1 + ( i + 1 ) p ) ) ] . \sum_{i=0}^{t-1}k_{i+1}-k_i-1\le\sum_{i=0}^{t-1}\log_{\gamma_1}\left[\frac{1}{\gamma_3\min(\sigma_{k_i},\varepsilon)}\right]+\sum_{i=0}^{t-1}\log_{\gamma_1}\left[\tilde b_{\mathrm{succ}}\left(1+\mu\left(1+(i+1)^p\right)\right)\right]. i = 0 ∑ t − 1 k i + 1 − k i − 1 ≤ i = 0 ∑ t − 1 log γ 1 [ γ 3 min ( σ k i , ε ) 1 ] + i = 0 ∑ t − 1 log γ 1 [ b ~ succ ( 1 + μ ( 1 + ( i + 1 ) p ) ) ] .
In the last term on the right-hand side, i + 1 ≤ t = ∣ S ( ε ) ∣ − 1 i+1\le t=\lvert\mathcal{S}(\varepsilon)\rvert-1 i + 1 ≤ t = ∣ S ( ε )∣ − 1 . Thus,
∑ i = 0 t − 1 k i + 1 − k i − 1 ≤ ∑ i = 0 t − 1 log γ 1 [ 1 γ 3 min ( σ k i , ε ) ] + ( ∣ S ( ε ) ∣ − 1 ) log γ 1 [ b ~ s u c c ( 1 + μ ( 1 + ( ∣ S ( ε ) ∣ − 1 ) p ) ) ] . \sum_{i=0}^{t-1}k_{i+1}-k_i-1\le\sum_{i=0}^{t-1}\log_{\gamma_1}\left[\frac{1}{\gamma_3\min(\sigma_{k_i},\varepsilon)}\right]+(\lvert\mathcal{S}(\varepsilon)\rvert-1)\log_{\gamma_1}\left[\tilde b_{\mathrm{succ}}\left(1+\mu\left(1+(\lvert\mathcal{S}(\varepsilon)\rvert-1)^p\right)\right)\right]. i = 0 ∑ t − 1 k i + 1 − k i − 1 ≤ i = 0 ∑ t − 1 log γ 1 [ γ 3 min ( σ k i , ε ) 1 ] + (∣ S ( ε )∣ − 1 ) log γ 1 [ b ~ succ ( 1 + μ ( 1 + (∣ S ( ε )∣ − 1 ) p ) ) ] .
There remains to bound the number of unsuccessful iterations before k 0 k_0 k 0 . Let k ∈ { 0 , … , k 0 − 1 } k\in\{0,\ldots,k_0-1\} k ∈ { 0 , … , k 0 − 1 } . The update of σ k \sigma_k σ k on unsuccessful iterations now yields σ k ≥ σ 0 γ 1 k \sigma_k\ge\sigma_0\gamma_1^k σ k ≥ σ 0 γ 1 k . Again, Lemma 4 and Model Assumption 3 yield
σ k ≤ b ~ s u c c ( 1 + μ ( 1 + ∣ S > 0 , k ∣ p ) ) = b ~ s u c c ( 1 + μ ) , \sigma_k\le\tilde b_{\mathrm{succ}}\left(1+\mu\left(1+\lvert\mathcal{S}_{>0,k}\rvert^p\right)\right)=\tilde b_{\mathrm{succ}}(1+\mu), σ k ≤ b ~ succ ( 1 + μ ( 1 + ∣ S > 0 , k ∣ p ) ) = b ~ succ ( 1 + μ ) ,
because S > 0 , k = ∅ \mathcal{S}_{>0,k}=\varnothing S > 0 , k = ∅ . Thus, with k = k 0 − 1 k=k_0-1 k = k 0 − 1 , we obtain
k 0 ≤ 1 + log γ 1 ( b ~ s u c c ( 1 + μ ) σ 0 ) . k_0\le1+\log_{\gamma_1}\left(\frac{\tilde b_{\mathrm{succ}}(1+\mu)}{\sigma_0}\right). k 0 ≤ 1 + log γ 1 ( σ 0 b ~ succ ( 1 + μ ) ) .
Combining the two bounds gives the desired result. □ \square □
We may expect that, for ε \varepsilon ε small enough, min ( σ k i , ε ) = ε \min(\sigma_{k_i},\varepsilon)=\varepsilon min ( σ k i , ε ) = ε for i = 0 , … , t − 1 i=0,\ldots,t-1 i = 0 , … , t − 1 . Hence, the bound given by Theorem 6 is worse than that of [15 Theorem 6.5] by an asymptotic factor of the form ∣ S ( ε ) ∣ log γ 1 ( 1 / ( γ 3 ε ) ) |\mathcal{S}(\varepsilon)|\log_{\gamma_1}(1/(\gamma_3\varepsilon)) ∣ S ( ε ) ∣ log γ 1 ( 1/ ( γ 3 ε )) , which, although it deteriorates the worst case, only affects unsuccessful iterations, and remains modest in practice. We stress again that our interest here is to minimally alter Algorithm 4.1 to preserve favorable complexity bounds and guarantee fast local convergence.
We now examine the behavior of Algorithm 10.1 near an isolated minimizer.
Assumption 1 f f f is C 2 C^2 C 2 and { x k } → x ⋆ \{x_k\}\to x^\star { x k } → x ⋆ where ∇ f ( x ⋆ ) = 0 \nabla f(x_\star)=0 ∇ f ( x ⋆ ) = 0 and ∇ 2 f ( x ⋆ ) ≻ 0 \nabla^2 f(x_\star)\succ0 ∇ 2 f ( x ⋆ ) ≻ 0 .
Assumption 1 and continuity ensure that s k → 0 s_k\to0 s k → 0 , ∇ f ( x k ) → 0 \nabla f(x_k)\to0 ∇ f ( x k ) → 0 , ∇ 2 f ( x k ) ≻ 0 \nabla^2 f(x_k)\succ0 ∇ 2 f ( x k ) ≻ 0 for all large enough k k k , and that there exists M > 0 M>0 M > 0 such that ∥ ∇ 2 f ( x k ) ∥ ≤ M \|\nabla^2 f(x_k)\|\le M ∥ ∇ 2 f ( x k ) ∥ ≤ M for all k k k .
To quantify the local convergence rate of Algorithm 10.1, we assume Lipschitz continuity of ∇ 2 f \nabla^2 f ∇ 2 f instead of Problem Assumption 2, and that the bound of Model Assumption 2 holds at every iteration instead of only for k ∈ S ≤ 0 k\in\mathcal{S}_{\leq0} k ∈ S ≤ 0 .
Problem Assumption 3 ∇ 2 f \nabla^2 f ∇ 2 f is globally Lipschitz-continuous, i.e., there exists L H ≥ 0 L_H\ge0 L H ≥ 0 such that ∥ ∇ 2 f ( x ) − ∇ 2 f ( y ) ∥ ≤ L H ∥ x − y ∥ \|\nabla^2 f(x)-\nabla^2 f(y)\|\le L_H\|x-y\| ∥ ∇ 2 f ( x ) − ∇ 2 f ( y ) ∥ ≤ L H ∥ x − y ∥ for all x , y ∈ R n x,y\in\mathbb{R}^n x , y ∈ R n .
Model Assumption 4 There exist C H > 0 C_H>0 C H > 0 and 0 < ζ ≤ 1 0<\zeta\le1 0 < ζ ≤ 1 such that, for all k ∈ N k\in\mathbb{N} k ∈ N , ∥ ( ∇ 2 f ( x k ) − B k ) s k ∥ ≤ C H ∥ s k ∥ 1 + ζ \|(\nabla^2 f(x_k)-B_k)s_k\|\le C_H\|s_k\|^{1+\zeta} ∥ ( ∇ 2 f ( x k ) − B k ) s k ∥ ≤ C H ∥ s k ∥ 1 + ζ , where x k x_k x k and s k s_k s k are the iterate and the trial step generated at iteration k k k of Algorithm 10.1.
To quantify the local convergence rate, we must specify how accurately (21) is solved at each iteration. Define
r k : = ( B k + σ k I ) s k + ∇ f ( x k ) , (39) r_k := (B_k+\sigma_k I)s_k+\nabla f(x_k), \tag*{(39)} r k := ( B k + σ k I ) s k + ∇ f ( x k ) , (39)
the residual at iteration k k k .
Lemma 5 Let Model Assumption 4 and Assumption 1 be satisfied. If { r k } → 0 \{r_k\}\to0 { r k } → 0 , σ k ∥ s k ∥ = O ( ∥ r k ∥ + ∥ ∇ f ( x k ) ∥ + ∥ s k ∥ ) \sigma_k\|s_k\|=O(\|r_k\|+\|\nabla f(x_k)\|+\|s_k\|) σ k ∥ s k ∥ = O ( ∥ r k ∥ + ∥∇ f ( x k ) ∥ + ∥ s k ∥ ) . In particular, { σ k s k } → 0 \{\sigma_k s_k\}\to0 { σ k s k } → 0 .
Proof. The triangle inequality, (39) and Model Assumption 4 yield
∥ σ k s k ∥ = ∥ r k − ∇ f ( x k ) − B k s k ∥ = ∥ r k − ∇ f ( x k ) − ∇ 2 f ( x k ) s k − ( B k − ∇ 2 f ( x k ) ) s k ∥ ≤ ∥ r k ∥ + ∥ ∇ f ( x k ) ∥ + M ∥ s k ∥ + C H ∥ s k ∥ 1 + ζ . \|\sigma_k s_k\|=\|r_k-\nabla f(x_k)-B_k s_k\|
=\|r_k-\nabla f(x_k)-\nabla^2 f(x_k)s_k-(B_k-\nabla^2 f(x_k))s_k\|
\le\|r_k\|+\|\nabla f(x_k)\|+M\|s_k\|+C_H\|s_k\|^{1+\zeta}. ∥ σ k s k ∥ = ∥ r k − ∇ f ( x k ) − B k s k ∥ = ∥ r k − ∇ f ( x k ) − ∇ 2 f ( x k ) s k − ( B k − ∇ 2 f ( x k )) s k ∥ ≤ ∥ r k ∥ + ∥∇ f ( x k ) ∥ + M ∥ s k ∥ + C H ∥ s k ∥ 1 + ζ .
For all large enough k k k , C H ∥ s k ∥ 1 + ζ ≤ M ∥ s k ∥ C_H\|s_k\|^{1+\zeta}\le M\|s_k\| C H ∥ s k ∥ 1 + ζ ≤ M ∥ s k ∥ , which concludes the proof. □ \square □
Lemma 6 Let Model Assumption 4 and Assumption 1 be satisfied. If { r k } → 0 \{r_k\}\to0 { r k } → 0 , ∥ ∇ f ( x k ) ∥ = O ( ∥ r k ∥ + σ k ∥ s k ∥ + ∥ s k ∥ ) \|\nabla f(x_k)\|=O(\|r_k\|+\sigma_k\|s_k\|+\|s_k\|) ∥∇ f ( x k ) ∥ = O ( ∥ r k ∥ + σ k ∥ s k ∥ + ∥ s k ∥ ) .
Proof. For all large enough k k k , C H ∥ s k ∥ 1 + ζ ≤ M ∥ s k ∥ C_H\lVert s_k\rVert^{1+\zeta}\leq M\lVert s_k\rVert C H ∥ s k ∥ 1 + ζ ≤ M ∥ s k ∥ . Thus, the triangle inequality, (39) and Model Assumption 4 ensure that for all large enough k k k ,
∥ r k − ∇ f ( x k ) ∥ = ∥ ∇ 2 f ( x k ) s k + ( B k − ∇ 2 f ( x k ) ) s k + σ k s k ∥ ≤ M ∥ s k ∥ + C H ∥ s k ∥ 1 + ζ + σ k ∥ s k ∥ ≤ 2 M ∥ s k ∥ + σ k ∥ s k ∥ . \begin{aligned}
\lVert r_k-\nabla f(x_k)\rVert
&=\lVert\nabla^2 f(x_k)s_k+(B_k-\nabla^2 f(x_k))s_k+\sigma_k s_k\rVert\\
&\leq M\lVert s_k\rVert+C_H\lVert s_k\rVert^{1+\zeta}+\sigma_k\lVert s_k\rVert\\
&\leq2M\lVert s_k\rVert+\sigma_k\lVert s_k\rVert.
\end{aligned} ∥ r k − ∇ f ( x k )∥ = ∥ ∇ 2 f ( x k ) s k + ( B k − ∇ 2 f ( x k )) s k + σ k s k ∥ ≤ M ∥ s k ∥ + C H ∥ s k ∥ 1 + ζ + σ k ∥ s k ∥ ≤ 2 M ∥ s k ∥ + σ k ∥ s k ∥ .
The triangle inequality ensures that ∥ r k − ∇ f ( x k ) ∥ ≥ ∥ ∇ f ( x k ) ∥ − ∥ r k ∥ \lVert r_k-\nabla f(x_k)\rVert\geq\lVert\nabla f(x_k)\rVert-\lVert r_k\rVert ∥ r k − ∇ f ( x k )∥ ≥ ∥ ∇ f ( x k )∥ − ∥ r k ∥ . Therefore, ∥ ∇ f ( x k ) ∥ ≤ ∥ r k ∥ + 2 M ∥ s k ∥ + σ k ∥ s k ∥ \lVert\nabla f(x_k)\rVert\leq\lVert r_k\rVert+2M\lVert s_k\rVert+\sigma_k\lVert s_k\rVert ∥ ∇ f ( x k )∥ ≤ ∥ r k ∥ + 2 M ∥ s k ∥ + σ k ∥ s k ∥ .
Lemma 7 Let Problem Assumption 3 and Model Assumption 4 and Assumption 1 be satisfied. If { r k } → 0 \{r_k\}\to0 { r k } → 0 , ∥ ∇ f ( x k + s k ) ∥ = O ( ∥ r k ∥ + ∥ s k ∥ 1 + ζ + σ k ∥ s k ∥ ) \lVert\nabla f(x_k+s_k)\rVert=O(\lVert r_k\rVert+\lVert s_k\rVert^{1+\zeta}+\sigma_k\lVert s_k\rVert) ∥ ∇ f ( x k + s k )∥ = O (∥ r k ∥ + ∥ s k ∥ 1 + ζ + σ k ∥ s k ∥) .
Proof. Problem Assumption 3 and Model Assumption 4 and (39) yield
∇ f ( x k + s k ) = ∇ f ( x k ) + ∫ 0 1 ∇ 2 f ( x k + τ s k ) s k d τ = ∫ 0 1 ∇ 2 f ( x k + τ s k ) s k d τ + r k − ∇ 2 f ( x k ) s k − ( B k − ∇ 2 f ( x k ) ) s k − σ k s k = ∫ 0 1 ( ∇ 2 f ( x k + τ s k ) − ∇ 2 f ( x k ) ) s k d τ + r k − ( B k − ∇ 2 f ( x k ) ) s k − σ k s k . \begin{aligned}
\nabla f(x_k+s_k)=\nabla f(x_k)+\int_0^1\nabla^2 f(x_k+\tau s_k)s_k\,\mathrm{d}\tau\\
&=\int_0^1\nabla^2 f(x_k+\tau s_k)s_k\,\mathrm{d}\tau+r_k-\nabla^2 f(x_k)s_k-(B_k-\nabla^2 f(x_k))s_k-\sigma_k s_k \\
&=\int_0^1\left(\nabla^2 f(x_k+\tau s_k)-\nabla^2 f(x_k)\right)s_k\,\mathrm{d}\tau+r_k-(B_k-\nabla^2 f(x_k))s_k-\sigma_k s_k.
\end{aligned} ∇ f ( x k + s k ) = ∇ f ( x k ) + ∫ 0 1 ∇ 2 f ( x k + τ s k ) s k d τ = ∫ 0 1 ∇ 2 f ( x k + τ s k ) s k d τ + r k − ∇ 2 f ( x k ) s k − ( B k − ∇ 2 f ( x k )) s k − σ k s k = ∫ 0 1 ( ∇ 2 f ( x k + τ s k ) − ∇ 2 f ( x k ) ) s k d τ + r k − ( B k − ∇ 2 f ( x k )) s k − σ k s k .
The triangle inequality and Problem Assumption 3 give
∥ ∇ f ( x k + s k ) ∥ ≤ ∫ 0 1 L H τ ∥ s k ∥ 2 d τ + ∥ r k ∥ + C H ∥ s k ∥ 1 + ζ + σ k ∥ s k ∥ = 1 2 L H ∥ s k ∥ 2 + ∥ r k ∥ + C H ∥ s k ∥ 1 + ζ + σ k ∥ s k ∥ . \begin{aligned}
\lVert\nabla f(x_k+s_k)\rVert
&\leq\int_0^1L_H\tau\lVert s_k\rVert^2\,\mathrm{d}\tau+\lVert r_k\rVert+C_H\lVert s_k\rVert^{1+\zeta}+\sigma_k\lVert s_k\rVert\\
&=\tfrac{1}{2}L_H\lVert s_k\rVert^2+\lVert r_k\rVert+C_H\lVert s_k\rVert^{1+\zeta}+\sigma_k\lVert s_k\rVert.
\end{aligned} ∥ ∇ f ( x k + s k )∥ ≤ ∫ 0 1 L H τ ∥ s k ∥ 2 d τ + ∥ r k ∥ + C H ∥ s k ∥ 1 + ζ + σ k ∥ s k ∥ = 2 1 L H ∥ s k ∥ 2 + ∥ r k ∥ + C H ∥ s k ∥ 1 + ζ + σ k ∥ s k ∥ .
Because 0 < ζ ≤ 1 0<\zeta\leq1 0 < ζ ≤ 1 and s k → 0 s_k\to0 s k → 0 , 1 2 L H ∥ s k ∥ 2 = O ( ∥ s k ∥ 1 + ζ ) \tfrac{1}{2}L_H\lVert s_k\rVert^2=O(\lVert s_k\rVert^{1+\zeta}) 2 1 L H ∥ s k ∥ 2 = O (∥ s k ∥ 1 + ζ ) . The result follows.
Lemma 8 Let Model Assumption 4 and Assumption 1 be satisfied. Assume that ∥ r k ∥ = O ( ∥ ∇ f ( x k ) ∥ ) \lVert r_k\rVert=O(\lVert\nabla f(x_k)\rVert) ∥ r k ∥ = O (∥ ∇ f ( x k )∥) . Then, ∥ s k ∥ = O ( ∥ ∇ f ( x k ) ∥ ) \lVert s_k\rVert=O(\lVert\nabla f(x_k)\rVert) ∥ s k ∥ = O (∥ ∇ f ( x k )∥) and σ k ∥ s k ∥ = O ( ∥ ∇ f ( x k ) ∥ ) \sigma_k\lVert s_k\rVert=O(\lVert\nabla f(x_k)\rVert) σ k ∥ s k ∥ = O (∥ ∇ f ( x k )∥) .
Proof. Let λ min > 0 \lambda_{\min}>0 λ m i n > 0 be the smallest eigenvalue of ∇ 2 f ( x ⋆ ) \nabla^2 f(x_\star) ∇ 2 f ( x ⋆ ) . Assumption 1 implies that for all large enough k k k , the smallest eigenvalue of ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇ 2 f ( x k ) is at least 1 2 λ min > 0 \frac{1}{2}\lambda_{\min}>0 2 1 λ m i n > 0 . Thus, for all large enough k k k , Model Assumption 4, (39) and the triangle inequality yield
∥ r k − ∇ f ( x k ) ∥ = ∥ ∇ 2 f ( x k ) s k + ( B k − ∇ 2 f ( x k ) ) s k + σ k s k ∥ ≥ ∥ ( ∇ 2 f ( x k ) + σ k I ) s k ∥ − ∥ ( B k − ∇ 2 f ( x k ) ) s k ∥ ≥ ( 1 2 λ min + σ k ) ∥ s k ∥ − C H ∥ s k ∥ 1 + ζ . \begin{aligned}
\lVert r_k-\nabla f(x_k)\rVert
&=\lVert\nabla^2 f(x_k)s_k+(B_k-\nabla^2 f(x_k))s_k+\sigma_k s_k\rVert\\
&\geq\lVert(\nabla^2 f(x_k)+\sigma_k I)s_k\rVert-\lVert(B_k-\nabla^2 f(x_k))s_k\rVert\\
&\geq\left(\tfrac{1}{2}\lambda_{\min}+\sigma_k\right)\lVert s_k\rVert-C_H\lVert s_k\rVert^{1+\zeta}.
\end{aligned} ∥ r k − ∇ f ( x k )∥ = ∥ ∇ 2 f ( x k ) s k + ( B k − ∇ 2 f ( x k )) s k + σ k s k ∥ ≥ ∥( ∇ 2 f ( x k ) + σ k I ) s k ∥ − ∥( B k − ∇ 2 f ( x k )) s k ∥ ≥ ( 2 1 λ m i n + σ k ) ∥ s k ∥ − C H ∥ s k ∥ 1 + ζ .
Because s k → 0 s_k\to0 s k → 0 , for all large enough k k k , C H ∥ s k ∥ 1 + ζ ≤ 1 4 λ min ∥ s k ∥ C_H\lVert s_k\rVert^{1+\zeta}\leq\frac{1}{4}\lambda_{\min}\lVert s_k\rVert C H ∥ s k ∥ 1 + ζ ≤ 4 1 λ m i n ∥ s k ∥ . Substituting this into the inequality yields:
∥ r k − ∇ f ( x k ) ∥ ≥ ( 1 4 λ min + σ k ) ∥ s k ∥ . (40) \lVert r_k-\nabla f(x_k)\rVert\geq\left(\tfrac{1}{4}\lambda_{\min}+\sigma_k\right)\lVert s_k\rVert. \tag*{(40)} ∥ r k − ∇ f ( x k )∥ ≥ ( 4 1 λ m i n + σ k ) ∥ s k ∥ . (40)
The triangle inequality and our assumption imply ∥ r k − ∇ f ( x k ) ∥ ≤ ∥ r k ∥ + ∥ ∇ f ( x k ) ∥ \lVert r_k-\nabla f(x_k)\rVert\leq\lVert r_k\rVert+\lVert\nabla f(x_k)\rVert ∥ r k − ∇ f ( x k )∥ ≤ ∥ r k ∥ + ∥ ∇ f ( x k )∥ . On the one hand, (40) gives 1 4 λ min ∥ s k ∥ ≤ ( 1 4 λ min + σ k ) ∥ s k ∥ ≤ ∥ r k ∥ + ∥ ∇ f ( x k ) ∥ = O ( ∥ ∇ f ( x k ) ∥ ) \frac{1}{4}\lambda_{\min}\lVert s_k\rVert\leq\left(\frac{1}{4}\lambda_{\min}+\sigma_k\right)\lVert s_k\rVert\leq\lVert r_k\rVert+\lVert\nabla f(x_k)\rVert=O(\lVert\nabla f(x_k)\rVert) 4 1 λ m i n ∥ s k ∥ ≤ ( 4 1 λ m i n + σ k ) ∥ s k ∥ ≤ ∥ r k ∥ + ∥ ∇ f ( x k )∥ = O (∥ ∇ f ( x k )∥) . Similarly, (40) gives σ k ∥ s k ∥ ≤ ( 1 4 λ min + σ k ) ∥ s k ∥ = O ( ∥ ∇ f ( x k ) ∥ ) \sigma_k\lVert s_k\rVert\leq\left(\frac{1}{4}\lambda_{\min}+\sigma_k\right)\lVert s_k\rVert=O(\lVert\nabla f(x_k)\rVert) σ k ∥ s k ∥ ≤ ( 4 1 λ m i n + σ k ) ∥ s k ∥ = O (∥ ∇ f ( x k )∥) .
Corollary 2 Let Problem Assumption 3 and Model Assumption 4 and Assumption 1 be satisfied. If ∥ r k ∥ = O ( ∥ ∇ f ( x k ) ∥ 1 + ζ ) \lVert r_k\rVert= O(\lVert\nabla f(x_k)\rVert^{1+\zeta}) ∥ r k ∥ = O (∥ ∇ f ( x k ) ∥ 1 + ζ ) and σ k = O ( ∥ ∇ f ( x k ) ∥ ζ ) \sigma_k = O(\lVert\nabla f(x_k)\rVert^\zeta) σ k = O (∥ ∇ f ( x k ) ∥ ζ ) , ∥ ∇ f ( x k + s k ) ∥ = O ( ∥ ∇ f ( x k ) ∥ 1 + ζ ) \lVert\nabla f(x_k+s_k)\rVert= O(\lVert\nabla f(x_k)\rVert^{1+\zeta}) ∥ ∇ f ( x k + s k )∥ = O (∥ ∇ f ( x k ) ∥ 1 + ζ ) .
Proof. The result follows directly from Lemmas 7 and 8 .
Corollary 3 Let Model Assumption 4 and Assumption 1 be satisfied. If ∥ r k ∥ = O ( ∥ s k ∥ ) \lVert r_k\rVert= O(\lVert s_k\rVert) ∥ r k ∥ = O (∥ s k ∥) and σ k = O ( 1 ) \sigma_k = O(1) σ k = O ( 1 ) , ∥ ∇ f ( x k ) ∥ = O ( ∥ s k ∥ ) \lVert\nabla f(x_k)\rVert= O(\lVert s_k\rVert) ∥ ∇ f ( x k )∥ = O (∥ s k ∥) . Thus, if ∥ r k ∥ = O ( max ( ∥ ∇ f ( x k ) ∥ , ∥ s k ∥ ) ) \lVert r_k\rVert= O(\max(\lVert\nabla f(x_k)\rVert,\lVert s_k\rVert)) ∥ r k ∥ = O ( max (∥ ∇ f ( x k )∥ , ∥ s k ∥)) and σ k = O ( 1 ) \sigma_k = O(1) σ k = O ( 1 ) , ∥ ∇ f ( x k ) ∥ = Θ ( ∥ s k ∥ ) \lVert\nabla f(x_k)\rVert= \Theta(\lVert s_k\rVert) ∥ ∇ f ( x k )∥ = Θ (∥ s k ∥) .
Proof. The first part follows directly from Lemma 6 . The second part follows from the first part and Lemma 8 .
Lemma 9 Let Problem Assumption 3 , Model Assumption 4 and Assumption 1 be satisfied. If B k s k = ∇ 2 f ( x k ) s k B_ks_k=\nabla^2 f(x_k)s_k B k s k = ∇ 2 f ( x k ) s k for all k k k , assume also that ∥ r k ∥ = O ( 1 ) \lVert r_k\rVert= O(1) ∥ r k ∥ = O ( 1 ) . Otherwise, assume that ∥ r k ∥ = O ( ∥ s k ∥ 1 + ζ ) \lVert r_k\rVert= O(\lVert s_k\rVert^{1+\zeta}) ∥ r k ∥ = O (∥ s k ∥ 1 + ζ ) and σ k = O ( ∥ s k ∥ ζ ) \sigma_k = O(\lVert s_k\rVert^\zeta) σ k = O (∥ s k ∥ ζ ) . Then, ρ k ≥ η 2 \rho_k \ge\eta_2 ρ k ≥ η 2 for all large enough k k k .
Proof. Problem Assumption 3 ensures that
∣ f ( x k + s k ) − f ( x k ) − ∇ f ( x k ) T s k − 1 2 s k T ∇ 2 f ( x k ) s k ∣ ≤ 1 3 ! L H ∥ s k ∥ 3 \left|f(x_k+s_k)-f(x_k)-\nabla f(x_k)^T s_k-\frac{1}{2}s_k^T\nabla^2 f(x_k)s_k\right|\le\frac{1}{3!}L_H\lVert s_k\rVert^3 f ( x k + s k ) − f ( x k ) − ∇ f ( x k ) T s k − 2 1 s k T ∇ 2 f ( x k ) s k ≤ 3 ! 1 L H ∥ s k ∥ 3 Thus, Model Assumption 4 yields
f ( x k + s k ) − φ ( s k ; x k ) ≤ 1 3 ! L H ∥ s k ∥ 3 − 1 2 s k T ( B k − ∇ 2 f ( x k ) ) s k f(x_k+s_k)-\varphi(s_k;x_k)\le\frac{1}{3!}L_H\lVert s_k\rVert^3-\frac{1}{2}s_k^T(B_k-\nabla^2 f(x_k))s_k f ( x k + s k ) − φ ( s k ; x k ) ≤ 3 ! 1 L H ∥ s k ∥ 3 − 2 1 s k T ( B k − ∇ 2 f ( x k )) s k ≤ 1 3 ! L H ∥ s k ∥ 3 + 1 2 C H ∥ s k ∥ 2 + ζ . \le\frac{1}{3!}L_H\lVert s_k\rVert^3+\frac{1}{2}C_H\lVert s_k\rVert^{2+\zeta}. ≤ 3 ! 1 L H ∥ s k ∥ 3 + 2 1 C H ∥ s k ∥ 2 + ζ . Let λ min > 0 \lambda_{\min}>0 λ m i n > 0 be the smallest eigenvalue of ∇ 2 f ( x ⋆ ) \nabla^2 f(x_\star) ∇ 2 f ( x ⋆ ) . Assumption 1 ensures that ∇ 2 f ( x k ) ≻ 0 \nabla^2 f(x_k)\succ0 ∇ 2 f ( x k ) ≻ 0 for all large enough k k k , and, in particular, that its smallest eigenvalue is larger than 1 2 λ min \frac{1}{2}\lambda_{\min} 2 1 λ m i n . We take the inner product of (39) with s k s_k s k and obtain
φ ( 0 ; x k ) − φ ( s k ; x k ) = − ∇ f ( x k ) T s k − 1 2 s k T B k s k = 1 2 s k T B k s k + σ k ∥ s k ∥ 2 − r k T s k = 1 2 s k T ∇ 2 f ( x k ) s k + 1 2 s k T ( B k − ∇ 2 f ( x k ) ) s k + σ k ∥ s k ∥ 2 − r k T s k ≥ 1 4 λ min ∥ s k ∥ 2 − 1 2 ∥ s k ∥ ∥ ( B k − ∇ 2 f ( x k ) ) s k ∥ + σ k ∥ s k ∥ 2 − ∥ r k ∥ ∥ s k ∥ ≥ 1 4 λ min ∥ s k ∥ 2 − 1 2 C H ∥ s k ∥ 2 + ζ + σ k ∥ s k ∥ 2 − ∥ r k ∥ ∥ s k ∥ . \begin{aligned}
\varphi(0;x_k)-\varphi(s_k;x_k)
&=-\nabla f(x_k)^Ts_k-\frac{1}{2}s_k^TB_ks_k\\
&=\frac{1}{2}s_k^TB_ks_k+\sigma_k\lVert s_k\rVert^2-r_k^Ts_k\\
&=\frac{1}{2}s_k^T\nabla^2 f(x_k)s_k+\frac{1}{2}s_k^T(B_k-\nabla^2 f(x_k))s_k+\sigma_k\lVert s_k\rVert^2-r_k^Ts_k\\
&\ge\frac{1}{4}\lambda_{\min}\lVert s_k\rVert^2-\frac{1}{2}\lVert s_k\rVert\lVert(B_k-\nabla^2 f(x_k))s_k\rVert+\sigma_k\lVert s_k\rVert^2-\lVert r_k\rVert\lVert s_k\rVert\\
&\ge\frac{1}{4}\lambda_{\min}\lVert s_k\rVert^2-\frac{1}{2}C_H\lVert s_k\rVert^{2+\zeta}+\sigma_k\lVert s_k\rVert^2-\lVert r_k\rVert\lVert s_k\rVert.
\end{aligned} φ ( 0 ; x k ) − φ ( s k ; x k ) = − ∇ f ( x k ) T s k − 2 1 s k T B k s k = 2 1 s k T B k s k + σ k ∥ s k ∥ 2 − r k T s k = 2 1 s k T ∇ 2 f ( x k ) s k + 2 1 s k T ( B k − ∇ 2 f ( x k )) s k + σ k ∥ s k ∥ 2 − r k T s k ≥ 4 1 λ m i n ∥ s k ∥ 2 − 2 1 ∥ s k ∥ ∥( B k − ∇ 2 f ( x k )) s k ∥ + σ k ∥ s k ∥ 2 − ∥ r k ∥ ∥ s k ∥ ≥ 4 1 λ m i n ∥ s k ∥ 2 − 2 1 C H ∥ s k ∥ 2 + ζ + σ k ∥ s k ∥ 2 − ∥ r k ∥ ∥ s k ∥ . The above combine to yield
ρ k = 1 + φ ( s k ; x k ) − f ( x k + s k ) φ ( 0 ; x k ) − φ ( s k ; x k ) ≥ 1 − 1 3 ! L H ∥ s k ∥ 3 + 1 2 C H ∥ s k ∥ 2 + ζ 1 4 λ min ∥ s k ∥ 2 − 1 2 C H ∥ s k ∥ 2 + ζ − ∥ r k ∥ ∥ s k ∥ + σ k ∥ s k ∥ 2 . \rho_k=1+\frac{\varphi(s_k;x_k)-f(x_k+s_k)}{\varphi(0;x_k)-\varphi(s_k;x_k)}
\ge1-\frac{\frac{1}{3!}L_H\lVert s_k\rVert^3+\frac{1}{2}C_H\lVert s_k\rVert^{2+\zeta}}{\frac{1}{4}\lambda_{\min}\lVert s_k\rVert^2-\frac{1}{2}C_H\lVert s_k\rVert^{2+\zeta}-\lVert r_k\rVert\lVert s_k\rVert+\sigma_k\lVert s_k\rVert^2}. ρ k = 1 + φ ( 0 ; x k ) − φ ( s k ; x k ) φ ( s k ; x k ) − f ( x k + s k ) ≥ 1 − 4 1 λ m i n ∥ s k ∥ 2 − 2 1 C H ∥ s k ∥ 2 + ζ − ∥ r k ∥ ∥ s k ∥ + σ k ∥ s k ∥ 2 3 ! 1 L H ∥ s k ∥ 3 + 2 1 C H ∥ s k ∥ 2 + ζ . Our assumptions ensure that the numerator above is Θ ( ∥ s k ∥ 2 + ζ ) \Theta(\lVert s_k\rVert^{2+\zeta}) Θ (∥ s k ∥ 2 + ζ ) while the denominator is Θ ( ∥ s k ∥ 2 ) \Theta(\lVert s_k\rVert^2) Θ (∥ s k ∥ 2 ) . Therefore, ρ k ≥ η 2 \rho_k\ge\eta_2 ρ k ≥ η 2 for all large enough k k k .
If B k s k = ∇ 2 f ( x k ) s k B_k s_k = \nabla^2 f(x_k)s_k B k s k = ∇ 2 f ( x k ) s k for all k k k , the terms involving ζ \zeta ζ above are simply absent, i.e., f ( x k + s k ) − ϕ ( s k ; x k ) ≤ 1 3 ! L H ∥ s k ∥ 3 f(x_k+s_k)-\phi(s_k;x_k) \le\frac{1}{3!}L_H\|s_k\|^3 f ( x k + s k ) − ϕ ( s k ; x k ) ≤ 3 ! 1 L H ∥ s k ∥ 3 , and ϕ ( 0 ; x k ) − ϕ ( s k ; x k ) > ( 1 4 λ min + σ k ) ∥ s k ∥ 2 − ∥ r k ∥ ∥ s k ∥ \phi(0;x_k)-\phi(s_k;x_k) > \left(\frac{1}{4}\lambda_{\min}+\sigma_k\right)\|s_k\|^2-\|r_k\|\|s_k\| ϕ ( 0 ; x k ) − ϕ ( s k ; x k ) > ( 4 1 λ m i n + σ k ) ∥ s k ∥ 2 − ∥ r k ∥∥ s k ∥ . Hence, ρ k → 1 \rho_k \to1 ρ k → 1 , and the result continues to hold. □ \square □
We compile the conclusions of this section into the following result.
Theorem 7 Let Problem Assumption 3, Model Assumption 4 and Assumption 1 be satisfied. For all large enough k k k , ρ k ≥ η 2 \rho_k \ge\eta_2 ρ k ≥ η 2 and every iteration is very successful. If ∥ r k ∥ = O ( ∥ ∇ f ( x k ) ∥ 1 + ζ ) \|r_k\| = O(\|\nabla f(x_k)\|^{1+\zeta}) ∥ r k ∥ = O ( ∥∇ f ( x k ) ∥ 1 + ζ ) and σ k = O ( ∥ ∇ f ( x k ) ∥ ζ ) \sigma_k = O(\|\nabla f(x_k)\|^\zeta) σ k = O ( ∥∇ f ( x k ) ∥ ζ ) , ∥ ∇ f ( x k + 1 ) ∥ = O ( ∥ ∇ f ( x k ) ∥ 1 + ζ ) \|\nabla f(x_{k+1})\| = O(\|\nabla f(x_k)\|^{1+\zeta}) ∥∇ f ( x k + 1 ) ∥ = O ( ∥∇ f ( x k ) ∥ 1 + ζ ) and ∥ x k + 1 − x ⋆ ∥ = O ( ∥ x k − x ⋆ ∥ 1 + ζ ) \|x_{k+1}-x_\star\| = O(\|x_k-x_\star\|^{1+\zeta}) ∥ x k + 1 − x ⋆ ∥ = O ( ∥ x k − x ⋆ ∥ 1 + ζ ) . In other words, the sequence { x k } \{x_k\} { x k } generated by Algorithm 10.1 converges locally superlinearly with rate 1 + ζ 1+\zeta 1 + ζ to an isolated minimizer. If B k s k = ∇ 2 f ( x k ) s k B_k s_k = \nabla^2 f(x_k)s_k B k s k = ∇ 2 f ( x k ) s k for all k k k , we may choose ζ = 1 \zeta=1 ζ = 1 , and the rate is quadratic.
Proof. By Corollary 3, ∥ ∇ f ( x k ) ∥ = Θ ( ∥ s k ∥ ) \|\nabla f(x_k)\| = \Theta(\|s_k\|) ∥∇ f ( x k ) ∥ = Θ ( ∥ s k ∥ ) , so that our assumptions on r k r_k r k and σ k \sigma_k σ k imply those of Lemma 9, which yields the first assertion. The second follows from Corollary 2. A Taylor expansion about x ⋆ x_\star x ⋆ yields, for all large enough k k k ,
∥ ∇ f ( x k ) ∥ = ∥ ∇ 2 f ( x ⋆ ) ( x k − x ⋆ ) + o ( ∥ x k − x ⋆ ∥ ) ∥ = Θ ( ∥ x k − x ⋆ ∥ ) . \|\nabla f(x_k)\| = \|\nabla^2 f(x_\star)(x_k-x_\star)+o(\|x_k-x_\star\|)\| = \Theta(\|x_k-x_\star\|). ∥∇ f ( x k ) ∥ = ∥ ∇ 2 f ( x ⋆ ) ( x k − x ⋆ ) + o ( ∥ x k − x ⋆ ∥ ) ∥ = Θ ( ∥ x k − x ⋆ ∥ ) .
Thus, ∥ x k + 1 − x ⋆ ∥ = O ( ∥ x k − x ⋆ ∥ 1 + ζ ) \|x_{k+1}-x_\star\| = O(\|x_k-x_\star\|^{1+\zeta}) ∥ x k + 1 − x ⋆ ∥ = O ( ∥ x k − x ⋆ ∥ 1 + ζ ) . □ \square □
In practice, the value of ζ \zeta ζ is often unknown. However, it should be clear from the analysis above that if one sets ∥ r k ∥ = O ( ∥ ∇ f ( x k ) ∥ 1 + μ ) \|r_k\| = O(\|\nabla f(x_k)\|^{1+\mu}) ∥ r k ∥ = O ( ∥∇ f ( x k ) ∥ 1 + μ ) and σ k = O ( ∥ ∇ f ( x k ) ∥ ω ) \sigma_k = O(\|\nabla f(x_k)\|^\omega) σ k = O ( ∥∇ f ( x k ) ∥ ω ) with 0 < μ , ω ≤ 1 0 < \mu,\omega\le1 0 < μ , ω ≤ 1 , the overall convergence rate will be 1 + min ( μ , ω , ζ ) 1+\min(\mu,\omega,\zeta) 1 + min ( μ , ω , ζ ) . Alternatively, one may simply set ∥ r k ∥ = O ( ∥ ∇ f ( x k ) ∥ 2 ) \|r_k\| = O(\|\nabla f(x_k)\|^2) ∥ r k ∥ = O ( ∥∇ f ( x k ) ∥ 2 ) and σ k = O ( ∥ ∇ f ( x k ) ∥ ) \sigma_k = O(\|\nabla f(x_k)\|) σ k = O ( ∥∇ f ( x k ) ∥ ) , as in Algorithm 10.1, and the overall convergence rate will be 1 + ζ 1+\zeta 1 + ζ . Although the latter choice may require solving (21) to higher accuracy than strictly necessary, it dispenses with trying to estimate ζ \zeta ζ .
A Variant for Nonlinear Least-Squares
Algorithm 4.1 specializes naturally to the smooth nonlinear least-squares problem
minimize x ∈ R n f ( x ) , f ( x ) : = 1 2 ∥ F ( x ) ∥ 2 , (41) \underset{x\in\mathbb{R}^n}{\operatorname{minimize}}\ f(x), \qquad f(x) := \frac{1}{2}\|F(x)\|^2, \tag*{(41)} x ∈ R n minimize f ( x ) , f ( x ) := 2 1 ∥ F ( x ) ∥ 2 , (41)
where F : R n → R m F:\mathbb{R}^n\to\mathbb{R}^m F : R n → R m is continuously differentiable. The gradient is given by ∇ f ( x ) = J ( x ) T F ( x ) \nabla f(x)=J(x)^T F(x) ∇ f ( x ) = J ( x ) T F ( x ) , where J ( x ) J(x) J ( x ) is the Jacobian of F F F . For simplicity, we write F k : = F ( x k ) F_k := F(x_k) F k := F ( x k ) , J k : = J ( x k ) J_k := J(x_k) J k := J ( x k ) , and g k : = ∇ f ( x k ) = J k T F k g_k := \nabla f(x_k)=J_k^T F_k g k := ∇ f ( x k ) = J k T F k .
Following the classic framework of Levenberg [34 ] and Marquardt [40 ] , we use the Gauss-Newton model by selecting B k : = J k T J k B_k := J_k^T J_k B k := J k T J k . Because σ k > 0 \sigma_k>0 σ k > 0 , B k + σ k I ≻ 0 B_k+\sigma_k I\succ0 B k + σ k I ≻ 0 , the subproblem is strongly convex, and hence admits a unique (global) minimizer. In addition, nonpositive-curvature directions never occur, and neither does the Armijo-Goldstein line search. The step s k s_k s k can be viewed as an approximate solution of the linear least-squares model
m ( s ; x k , σ k ) : = 1 2 ∥ J k s + F k ∥ 2 + 1 2 σ k ∥ s ∥ 2 = 1 2 ∥ [ J k σ k I ] s + [ F k 0 ] ∥ 2 . (42) m(s;x_k,\sigma_k) := \frac{1}{2}\|J_k s+F_k\|^2+\frac{1}{2}\sigma_k\|s\|^2 = \frac{1}{2}\left\|\begin{bmatrix}J_k\\ \sqrt{\sigma_k}I\end{bmatrix}s+\begin{bmatrix}F_k\\ 0\end{bmatrix}\right\|^2. \tag*{(42)} m ( s ; x k , σ k ) := 2 1 ∥ J k s + F k ∥ 2 + 2 1 σ k ∥ s ∥ 2 = 2 1 [ J k σ k I ] s + [ F k 0 ] 2 . (42)
In this context, (21) is the system of normal equations associated with (42) . The solvers used to compute a step parallel those used in Algorithm 4.1 , except that there is no quasi-Newton solver, but they exploit the least-squares structure of m ( ⋅ ; x k , σ k ) m(\cdot;x_k,\sigma_k) m ( ⋅ ; x k , σ k ) :
CGLS: a variant of CG described by Hestenes and Stiefel [28 ] in which products with J k J_k J k and J k T J_k^T J k T are decoupled, and that is equivalent to CG applied to (21) in exact arithmetic, but that is typically more robust in practice.
LSQR [50 ] : a Krylov method that is equivalent to CG applied to (21) in exact arithmetic, but that is typically more robust in practice.
LSMR [21 ] : a Krylov method that is equivalent to MINRES applied to (21) in exact arithmetic, but that is typically more robust in practice.
QRMumps [1 ] : a multi-core sparse QR factorization used to factorize the matrix of the linear residual in (42) . Indeed the R R R factor of the latter is the transposed Cholesky factor of B k + σ k I B_k+\sigma_k I B k + σ k I . This approach parallels the sparse factorization of B k + σ k I B_k+\sigma_k I B k + σ k I in (21) .
Our implementation uses the Julia implementation of CGLS, LSQR and LSMR found in [44 ] and the QRMumps interface found in [7 ] . By extension of the subproblem solvers for Algorithm 4.1 , the solvers above guarantee Cauchy decrease under the same assumptions.
The resulting procedure is a globally convergent Levenberg-Marquardt method. In (41) , denote F ( x ) = ( f 1 ( x ) , … , f m ( x ) ) F(x)=(f_1(x),\ldots,f_m(x)) F ( x ) = ( f 1 ( x ) , … , f m ( x )) . If each f i f_i f i is twice differentiable, Model Assumption 4 can be stated as
∥ ( ∑ i = 1 m f i ( x k ) ∇ 2 f i ( x k ) ) s k ∥ ≤ C H ∥ s k ∥ 1 + ζ , \left\Vert\left(\sum_{i=1}^{m}f_i(x_k)\nabla^2 f_i(x_k)\right)s_k\right\Vert\le C_H\left\Vert s_k\right\Vert^{1+\zeta}, ( i = 1 ∑ m f i ( x k ) ∇ 2 f i ( x k ) ) s k ≤ C H ∥ s k ∥ 1 + ζ ,
and holds, among others, when F F F is linear near a solution, and when x k x_k x k approaches a zero-residual solution, but may potentially hold in other situations. All global convergence, worst-case complexity bounds, and local convergence of § 7 , § 8 and § 11 carry over without modification under the assumption above.
Implementation and Numerical Experiments
We describe our implementation of R2N and R2NLS and assess it on problems from the CUTEst collection. In § 13.1 to § 13.3 , we describe the computational environment, test set, algorithmic parameters and performance measures. Our first objective is to identify a best default configuration for R2N by evaluating options for the treatment of nonpositive curvature, the Krylov subproblem solver, the update of the regularization parameter, and direct vs. iterative subproblem solves. We use exact second derivatives in § 13.4 . We end the section with a comparison with a trust-region method, which has natural treatment of nonpositive curvature directions. We repeat similar experiments using limited-memory BFGS Hessian approximations in § 13.7 . Finally, we consider nonlinear least-squares problems in § 13.9 , for which nonpositive curvature cannot arise.
Implementation and Benchmark Setup
All experiments were conducted on a Linux system equipped with two AMD EPYC 7402 24-core processors and 1 TiB of RAM, though only 8 GiB are available to any individual user, running AlmaLinux 9.8 (Olive Jaguar). The solvers are implemented in Julia 1.13, and every run uses a single CPU thread without GPU acceleration. Julia relies on a BLAS library, while MA57 and QRMumps both rely on another, and both are set to use a single thread. Problems are solved sequentially, so the reported times are free of contention between runs. All computations are carried out in Float64.
The R2N and R2NLS solvers are part of the JSOSolvers.jl package [43 ] version 0.14.9, a component of the JuliaSmoothOptimizers (JSO) organization. Their implementation is based on several JSO libraries: NLPModels.jl [47 ] (v0.21.12) defines abstract types to represent problems, NLPModelsModifiers.jl [41 ] (v0.8.0) is used to replace a model’s exact second derivatives with quasi-Newton approximations, LinearOperators.jl [32 ] (v2.14.1) is used to model exact Hessians and limited-memory quasi-Newton approximations as abstract linear operators, Krylov.jl [44 ] (v0.10.6) has implementations of the various Krylov methods used in R2N and R2NLS, HSL.jl [23 ] (v0.5.2, LibHSL 2025.7.21) provides an interface to MA57, QRMumps.jl [7 ] (v0.3.2, QRMumps 3.1.1) interfaces QRMumps, and SolverCore.jl [42 ] (v0.3.10) provides solver building blocks. Finally, CUTEst.jl (v1.3.7, CUTEst 2.6.0, SIFDecode 3.1.0) provides access to problems from the CUTEst collection using the abstractions of NLPModels.jl, and SolverBenchmark.jl [48 ] (v0.6.5) standardizes benchmarking activities. Problems obtained from CUTEst.jl allow access to explicit Hessians as sparse matrices, or as abstract linear operators via operator-vector products.
While evaluating the model curvature along the gradient, γ k \gamma_k γ k , requires only one operator-vector product and a few dot products, computing the exact Cauchy step s k , c p s_{k,\mathrm{cp}} s k , cp (Algorithm 4.2) is not necessarily cheap. When γ k ≤ 0 \gamma_k \le0 γ k ≤ 0 , it requires estimating the spectral norm ∥ B k ∥ \lVert B_k\rVert ∥ B k ∥ at Algorithm 4.2. We use the estimator implemented by default in LinearOperators.jl, which computes the norm via an eigendecomposition for n ≤ 5 n \le5 n ≤ 5 and otherwise calls the implicitly restarted Lanczos iteration of ARPACK [33 ] via the Arpack.jl (v0.5.4) package. Thus, falling back to s k , c p s_{k,\mathrm{cp}} s k , cp is a safe global convergence mechanism, but it is not free. When a direction of nonpositive curvature is detected and a step length α k \alpha_k α k satisfying the Armijo-Goldstein conditions has been found, the resulting step is subjected to the usual ratio test by default. Proposition 10 shows that ρ k ≥ η ~ 1 > 0 \rho_k \ge\tilde{\eta}_1 > 0 ρ k ≥ η ~ 1 > 0 for such steps, so the test may optionally be bypassed; we evaluate that variant in § 13.4 and § 13.7 . Before factorizing, the direct subproblem solvers apply a density test: MA57 is not used if n > 12,000 n > 12{,}000 n > 12 , 000 and nnz ( H ) > n ( n + 1 ) / 4 \operatorname{nnz}(H) > n(n+1)/4 nnz ( H ) > n ( n + 1 ) /4 , i.e., the Hessian is more than half full. Similarly, QRMumps is not used if m n > 12,000 2 mn > 12{,}000^2 mn > 12 , 00 0 2 and nnz ( J ) > 1 2 m n \operatorname{nnz}(J) > \frac{1}{2}mn nnz ( J ) > 2 1 mn . Below the size thresholds, even a fully dense matrix is inexpensive to factorize, and density alone is no reason to avoid a direct solve. When the test fails, the solver declines to factorize and recommends a Krylov subproblem solver instead.
Test problems. Our benchmark uses problems drawn from the CUTEst test set [26 ] . For the general unconstrained experiments of § 13.4 and § 13.7 , we retain the smooth unconstrained problems, excluding those of nonlinear least-squares type, which are treated separately in § 13.9 . No bound is imposed on the number of variables n n n , and the suite spans problems from a few variables to large-scale instances.
Problems FLETCBV2, FLETCBV3, FLETCHBV, LRCOVTYPE, and NONM-SQRT were excluded because they exceed the time limit of 600s in all solver configurations. In addition, PENALTY1 and VAREIGVL were excluded because they fail the density test for MA57. The remaining suite contains 87 problems.
In the nonlinear least-squares experiments of § 13.9 , we use the CUTEst least-squares problems with at most 5,000 variables. The seven problems ARGLCLE, DIAMON3D, DMN15103, DMN37142, DMN37143, KSS, and PATTERNNE fail the density test, and are excluded. The remaining suite contains 177 problems.
Algorithm Parameters and Tolerances
All global tolerances, experimental settings, and algorithmic constants for the step-acceptance logic and regularization multipliers are summarized in Table 1 . Termination is controlled by the wall-clock time limit and by the gradient-norm criterion ∥ ∇ f ( x k ) ∥ ≤ ε a + ε r ∥ ∇ f ( x 0 ) ∥ \lVert\nabla f(x_k)\rVert\le\varepsilon_a+\varepsilon_r\lVert\nabla f(x_0)\rVert ∥ ∇ f ( x k )∥ ≤ ε a + ε r ∥ ∇ f ( x 0 )∥ . For least-squares problems, the solvers also stop when ∥ F ( x k ) ∥ ≤ ε F a + ε F r ∥ F ( x 0 ) ∥ \lVert F(x_k)\rVert\le\varepsilon_{F_a}+\varepsilon_{F_r}\lVert F(x_0)\rVert ∥ F ( x k )∥ ≤ ε F a + ε F r ∥ F ( x 0 )∥ . The same criteria, tolerances and time limit are used for every solver compared in § 13 , including the trust-region solver Trunk of § 13.6 , § 13.8 and § 13.9 . Apart from these settings, Trunk is used as distributed in JSOSolvers.jl with its default parameters; in particular, it backtracks along rejected steps and selects its own initial trust-region radius.
Table 1. Experimental settings and algorithmic constants.
We set the initial regularization parameter to
σ 0 : = max ( σ min , 2 round ( log 2 ( ∥ ∇ f ( x 0 ) ∥ + 1 ) ) ∥ ∇ f ( x 0 ) ∥ ) , (43) \sigma_0 := \max\left(\sigma_{\min}, \frac{2^{\operatorname{round}(\log_2(\lVert\nabla f(x_0)\rVert+1))}}{\lVert\nabla f(x_0)\rVert}\right), \tag*{(43)} σ 0 := max ( σ m i n , ∥ ∇ f ( x 0 )∥ 2 round ( l o g 2 (∥ ∇ f ( x 0 )∥ + 1 )) ) , (43)
and σ 0 : = max ( σ min , 1 ) \sigma_0 := \max(\sigma_{\min},1) σ 0 := max ( σ m i n , 1 ) in the case ∇ f ( x 0 ) = 0 \nabla f(x_0)=0 ∇ f ( x 0 ) = 0 . Rounding to the nearest power of two perturbs the numerator by at most a factor 2 \sqrt{2} 2 , and therefore σ 0 ≥ ( 1 + ∥ ∇ f ( x 0 ) ∥ − 1 ) / 2 > 2 − 1 / 2 \sigma_0 \ge(1+\lVert\nabla f(x_0)\rVert^{-1})/\sqrt{2}>2^{-1/2} σ 0 ≥ ( 1 + ∥ ∇ f ( x 0 ) ∥ − 1 ) / 2 > 2 − 1/2 .
Hence, the lower bound in (43) is typically never active and σ min \sigma_{\min} σ m i n serves only as a floor on subsequent decreases of σ k \sigma_k σ k . This choice requires no per-problem tuning, and it keeps the problem-dependent constants b max b_{\max} b m a x of Proposition 13 and the leading term of Theorem 6, both of which involve σ 0 \sigma_0 σ 0 , of moderate size. We set σ min = ε M ≈ 2.2 × 10 − 16 \sigma_{\min}=\varepsilon_M\approx2.2\times10^{-16} σ m i n = ε M ≈ 2.2 × 1 0 − 16 . A strictly positive σ min \sigma_{\min} σ m i n satisfies assumption (i) of Proposition 3; at this magnitude it does not interfere numerically with the local convergence analysis of § 11 , which requires σ k → 0 \sigma_k\to0 σ k → 0 near an isolated minimizer.
We set θ 2 = ε M − 1 \theta_2=\varepsilon_M^{-1} θ 2 = ε M − 1 , so that the safeguard on Algorithm 4.1 of Algorithm 4.1 is effectively disabled, and the assumption following Theorem 2 holds.
When a nonpositive curvature direction is detected, the default handler is the Armijo-Goldstein line search with the constants ρ L \rho_L ρ L and ρ U \rho_U ρ U of Table 1 . It starts from α = 1 \alpha=1 α = 1 , multiplies the trial step length by 1.5 while the Goldstein condition fails, and halves it while the Armijo condition fails, with at most 10 expansions and 10 reductions. If either budget is exhausted, or if the direction returned by the subproblem solver is not a descent direction, the step is rejected and σ k \sigma_k σ k is increased. A step whose predicted reduction does not exceed ε M max ( 1 , ∣ f ( x k ) ∣ ) \varepsilon_M \max(1, |f(x_k)|) ε M max ( 1 , ∣ f ( x k ) ∣ ) is also rejected, without evaluating f f f . When using the MA57 direct solver, nonpositive curvature is detected as a by-product of the factorization itself, which reports the inertia. If detected, the step is rejected and σ k \sigma_k σ k is increased. Indeed, the Armijo-Goldstein line search is not applicable because an exact solution of (21) that is a nonpositive-curvature direction cannot be a descent direction. For Krylov-based inner solvers, the absolute stopping tolerance matches ε a \varepsilon_a ε a , while the relative tolerance ε r k \varepsilon_{rk} ε r k follows the forcing sequence
ε r k = max ( ε r , min ( 0.1 , ∥ ∇ f ( x k ) ∥ , 0.9 ε r , k − 1 ) ) , (44) \varepsilon_{rk} = \max\left(\varepsilon_r, \min\left(0.1, \sqrt{\lVert\nabla f(x_k)\rVert}, 0.9\varepsilon_{r,k-1}\right)\right), \tag*{(44)} ε r k = max ( ε r , min ( 0.1 , ∥ ∇ f ( x k )∥ , 0.9 ε r , k − 1 ) ) , (44)
updated after each accepted step. The Krylov subproblem solvers of Trunk use the same rule, but update it at every iteration, including after a rejected step, in which case their tolerance decreases by a factor 0.9 while that of R2N is unchanged. In the limited-memory experiments of § 13.7 , B k B_k B k is the L-BFGS approximation implemented in LinearOperators.jl with memory q = 5 q = 5 q = 5 , initialized with B k , 0 = ( y k T y k / s k T y k ) I B_{k,0} = (y_k^T y_k / s_k^T y_k)I B k , 0 = ( y k T y k / s k T y k ) I from the most recent stored pair, and an update is performed whenever s k T y k ≥ ε M s_k^T y_k \ge\varepsilon_M s k T y k ≥ ε M . The same model and memory are used on both sides of the comparison of § 13.8 . R2NLS uses the update of σ k \sigma_k σ k given in Algorithm 4.1 ; the local analysis of § 11 does not apply to least-squares problems in general. An objective is declared unbounded when f ( x k ) < min ( − 1 , f ( x 0 ) ) / ε M f(x_k) < \min(-1, f(x_0))/\varepsilon_M f ( x k ) < min ( − 1 , f ( x 0 )) / ε M .
Performance Metrics
We compare solvers by means of Dolan and Moré [17 ] performance profiles, produced by SolverBenchmark.jl [48 ] . For each problem p p p and solver s s s , let t p , s > 0 t_{p,s} > 0 t p , s > 0 denote the measure of interest, with t p , s = ∞ t_{p,s} = \infty t p , s = ∞ if s s s fails on p p p . The performance ratio is r p , s ≔ t p , s / min s ′ t p , s ′ r_{p,s} \coloneqq t_{p,s}/\min_{s'} t_{p,s'} r p , s : = t p , s / min s ′ t p , s ′ , and the profile of solver s s s gives, as a function of τ ≥ 1 \tau\ge1 τ ≥ 1 , the fraction of problems for which r p , s ≤ τ r_{p,s} \le\tau r p , s ≤ τ . The measures are wall-clock time, objective evaluations, gradient evaluations and equivalent Hessian evaluations n H + n H v / n n_H + n_{Hv}/n n H + n H v / n , which counts n n n Hessian-vector products as one Hessian evaluation. Because the gradient is evaluated once per accepted step, the gradient profile also measures the number of successful iterations. For least-squares problems, we report residual evaluations, iterations and equivalent Jacobian evaluations n J + n J v / n + n J T v / m n_J + n_{Jv}/n + n_{J_Tv}/m n J + n J v / n + n J T v / m . Table 2 reports the number of problems solved by each configuration and how the failed runs terminated. A run is counted under Exception when the solver stops on an error before meeting a stopping criterion. For instance, on INDEFF, whose objective is unbounded below, such a termination is expected. With more than two solvers, a profile identifies the solver most likely to be within a factor τ \tau τ of the best, but does not compare them two-by-two [25 ] . Below, we do not report results with R2NLS in full detail because it is an implementation of the well-known Levenberg [34 ] and Marquardt [40 ] method, as is its trust-region variant, first described by Moré [46 ] . We use our own implementation of the latter, named TrunkNLS, with LSMR as subproblem solver.
Table 2. Problems solved, and reason for termination otherwise, for each configuration appearing in Sections 12.4 to 12.6. The unconstrained suite contains 87 problems and the least-squares suite 177. Exception (non-descent): termination on a search direction that is not a descent direction.
R2N with Exact Second Derivatives
We first evaluate R2N when exact second derivatives are available, either through Hessian-vector products or as an assembled sparse Hessian. We progressively compare options to build an efficient and robust default configuration. We examine in turn the treatment of nonpositive-curvature directions (§ 13.4.1 ), the Krylov subproblem solver (§ 13.5 ), the regularization parameter update, and compare options combined with an iterative, and with a direct subproblem solver (§ 13.5.1 and § 13.5.2 ). We then compare direct vs. iterative solves (§ 13.5.3 ), and finally compare our best configuration of R2N with a trust-region solver (§ 13.6 ).
Nonpositive-Curvature Handlers
Our first experiment concerns the treatment of nonpositive-curvature (NPC) directions. We fix MINRES-QLP as subproblem solver and vary only the handler; the model, the regularization update and the stopping tolerances are identical across the four runs. The four handlers are those discussed in § 6.6 :
AG: an Armijo-Goldstein line search along the NPC direction, i.e., (14) ;
Prev: the most recent Krylov iterate preceding the detection of the NPC direction, which continues to satisfy sufficient decrease; when NPC appears at the first inner iteration, no previous iterate exists, and the subproblem solver returns the right-hand side − ∇ f ( x k ) -\nabla f(x_k) − ∇ f ( x k ) , which Prev uses as the step;
Sigma: an increase of σ k \sigma_k σ k followed by a restart of the subproblem solver, which promotes convexity of the model at the price of the work already performed;
CP: a fallback on the Cauchy step, which ignores curvature information and requires an estimate of ∥ B k ∥ \lVert B_k\rVert ∥ B k ∥ whenever γ k ≤ 0 \gamma_k \le0 γ k ≤ 0 (Algorithm 4.2 of Algorithm 4.2).
Figure 3 shows that CP is dominated by the three other handlers on elapsed time and on equivalent Hessian evaluations. It is also the least robust: it solves five fewer problems than AG, Prev and Sigma, which solve the same 85 problems (Table 2 ). The first-order Cauchy step increases the number of outer iterations, and on those iterations where γ k ≤ 0 \gamma_k \le0 γ k ≤ 0 it also requires an estimate of ∥ B k ∥ \lVert B_k\rVert ∥ B k ∥ , obtained as described in § 13.1 ; both effects are likely to contribute to its cost. Falling back on the Cauchy step is a sound global convergence mechanism, but an expensive default.
Figure 3. Performance profiles of R2N with exact second derivatives, the MINRES-QLP subproblem solver and the σ k \sigma_k σ k update of Algorithm 4.1 . Comparison between nonpositive-curvature (NPC) handlers: Armijo-Goldstein line search (AG), previous MINRES-QLP iterate (Prev), increase of σ k \sigma_k σ k (Sigma), and fallback on the Cauchy step (CP).
The three remaining handlers are close, and their profiles largely overlap. AG has the highest profiles for gradient evaluations and equivalent Hessian evaluations, but the lowest for objective evaluations at small τ \tau τ , because each Armijo-Goldstein line search evaluates f f f several times; the elapsed-time profiles overlap. AG thus trades objective evaluations for gradient evaluations and Hessian-vector products, and is preferable when the latter dominate the cost of an iteration, whereas Prev or Sigma may be preferable when objective evaluations are the more expensive. We also ran AG with other values of ρ L \rho_L ρ L and ρ U \rho_U ρ U and of the expansion and reduction factors of the line search, and observed no noticeable change in the results, which we do not report. We adopt AG as the default for the remainder of our experiments.
Truncated CG versus MINRES-QLP
With the handler fixed to AG, we compare the two Krylov methods available for the subproblem. Truncated CG [52 ] detects nonpositive curvature based on its search directions. MINRES-QLP [9 ] coincides with MINRES in exact arithmetic on nonsingular systems, so that the guarantees of § 6.4 apply to it, and remains well defined on singular systems. Equipped with the mechanism of Liu and Roosta [38 ] , MINRES-QLP detects nonpositive curvature directly from quantities generated by the Lanczos process. The outer loop, the handler and the stopping tolerances are identical.
The profiles of MINRES-QLP lie above those of truncated CG for all four measures of Figure 4 . MINRES-QLP solves one more problem, DJTL, on which truncated CG makes little progress until the time limit (Table 2 ).
Figure 4. Performance profiles of R2N with exact second derivatives, the AG handler and the base update of σ k \sigma_k σ k . Comparison between subproblem solvers: truncated CG (CG) and MINRES-QLP (MINRES-QLP).
We use MINRES-QLP as the default subproblem solver in the sequel. Truncated CG remains a reasonable widely-available alternative.
Outer-Loop Variants with MINRES-QLP
We now study the two outer-loop switches of R2N, holding MINRES-QLP and the AG handler fixed. The Base configuration is that of Algorithm 4.1 with its update of σ k \sigma_k σ k and the parameters of Table 1 . The Fast variant replaces the σ k \sigma_k σ k update on very successful iterations by that of Algorithm 10.1, which drives σ k \sigma_k σ k to zero. The Skip ρ \rho ρ variant accepts a step obtained from an Armijo-Goldstein line search without evaluating ρ k \rho_k ρ k , as motivated by Proposition 10 . The fourth configuration enables both.
The Fast update produces the visible difference in Figure 5 . Its profiles lie above those of the base update at small τ \tau τ for gradient evaluations, i.e., successful iterations, and for equivalent Hessian evaluations, while the elapsed-time and objective evaluations profiles largely overlap and robustness is unchanged (Table 2 ). This suggests that the base update of Algorithm 4.1 , which decreases σ k \sigma_k σ k by γ 3 \gamma_3 γ 3 per very successful iteration, keeps σ k \sigma_k σ k larger than necessary as the iterates approach a minimizer. In § 13.5.2 , exact subproblem solves illustrate the same effect.
Figure 5. Performance profiles of R2N with exact second derivatives, the MINRES-QLP subproblem solver and the AG handler. Comparison between variants: update of σ k \sigma_k σ k of Algorithm 4.1 (Base), update of Algorithm 10.1 (Fast), acceptance of AG steps without the ratio test (Skip ρ \rho ρ ), and both changes (Fast, Skip ρ \rho ρ ).
The profiles with and without the Skip ρ \rho ρ switch are superimposed, as Proposition 10 leads us to expect: an Armijo-Goldstein step satisfies ρ k ≥ η ~ 1 > 0 \rho_k \ge\widetilde{\eta}_1 > 0 ρ k ≥ η 1 > 0 , so that, with η 1 = ε M 1 / 4 \eta_1 = \varepsilon_M^{1/4} η 1 = ε M 1/4 , the ratio test can reject such a step only if η ~ 1 < η 1 \widetilde{\eta}_1 < \eta_1 η 1 < η 1 . Because f ( x k + s k ) f(x_k+s_k) f ( x k + s k ) has already been computed by the line search, skipping the test saves no evaluation; its only effect is on the regularization parameter, which is left unchanged after every accepted Armijo-Goldstein step, whereas with the test in place a step with ρ k ≥ η 2 \rho_k \ge\eta_2 ρ k ≥ η 2 decreases it. The switch costs one problem, SCOSINE. When nonpositive curvature is detected on many consecutive iterations, freezing σ k \sigma_k σ k may leave it at a value fixed early in the run and over-regularize the steps that follow, which is a plausible explanation of that loss. Because skipping the test saves no evaluation and costs one problem, we keep the ratio test.
The AG handler combined with the Fast update is the configuration we carry into the comparisons that follow.
Outer-Loop Variants with MA57
We repeat the comparison of § 13.5.1 with the direct solver MA57 [18 ] in place of MINRES-QLP, retaining only the Fast switch. The subproblem is then solved exactly. Figure 6 shows that the Fast update is above the base update on all four measures, including elapsed time.
Figure 6. Performance profiles of R2N with exact second derivatives and the MA57 subproblem solver. Comparison between the update of σ k \sigma_k σ k of Algorithm 4.1 (Base) and that of Algorithm 10.1 (Fast). Nonpositive curvature is handled by rejecting the step and increasing σ k \sigma_k σ k .
The update rule does not affect robustness. Both configurations solve the same 85 problems (Table 2 ), and both declare INDEF and HIELOW unbounded below. Neither reaches the time limit. With exact subproblem solves, the Fast update should therefore be preferred; the price of such a solve, which is to assemble and factorize the Hessian at every iteration, is the subject of § 13.5.3 .
MA57 versus MINRES-QLP
We compare the two ways of solving the subproblem with exact second derivatives, both under the Fast update of Algorithm 10.1: MINRES-QLP with the AG handler, and MA57 [18 ] , which increases σ k \sigma_k σ k on NPC directions, and hence, requires a fresh factorization. The equivalent Hessian panel of Figure 7 counts one assembled Hessian as n n n products, and therefore does not measure the relative cost of the two solvers.
Figure 7. Performance profiles of R2N with exact second derivatives and the Fast update of σ k \sigma_k σ k . Comparison between subproblem solvers: MINRES-QLP with the AG handler and MA57. Equivalent Hessian evaluations count one assembled Hessian as n n n Hessian-vector products and do not reflect the cost of factorization.
The two configurations are closely matched on this test set, and their elapsed-time profiles nearly coincide. MA57 requires fewer objective evaluations on more problems, which is consistent with an exact step being accepted more often and with the absence of a line search in the Sigma strategy, while the gradient-evaluation profiles are close. Both solve 85 problems (Table 2 ). Besides INDEF, MINRES-QLP reaches the time limit on SCOSINE, and MA57 declares HIELOW unbounded.
We retain MINRES-QLP as the default subproblem solver, since it needs only operator-vector products and its memory requirements do not depend on fill-in. MA57 is the better choice for small to moderate sizes when the Hessian is sparse, inexpensive to assemble and has sparse factors.
R2N versus Trunk
We now compare R2N, with truncated CG, the AG handler and the Fast update, with Trunk, the Steihaug-Toint trust-region method [52 ] . The two solvers share the model, the Krylov method, the forcing formula (44) and the stopping test, but they are complete solvers that differ in more than the step control. Trunk applies a backtracking line search along rejected steps, uses its own initial radius and update constants, tightens the inner tolerance after a rejected step, and steps to the trust-region boundary along a nonpositive-curvature direction. The comparison therefore assesses R2N against an established solver, not one ingredient in isolation.
Neither solver dominates in Figure 8 . Trunk is the fastest on more problems, but the elapsed-time profiles cross at small τ \tau τ , and R2N is slightly more robust. R2N requires fewer objective and gradient evaluations, hence fewer iterations. Trunk requires fewer Hessian-vector products on more problems, but again, the profiles cross for small τ \tau τ .
Figure 8. Performance profiles with exact second derivatives and truncated CG as subproblem solver on both sides. Comparison between R2N with the AG handler and the Fast update of σ k \sigma_k σ k (R2N) and the trust-region method Trunk (Trunk).
R2N solves three more problems than Trunk, and every problem solved by Trunk is also solved by R2N (Table 2 ). Of the three, Trunk reaches the time limit on SCOSINE and STRATEC, and declares HIELOW unbounded. On INDEF, whose objective is unbounded below, R2N detects unboundedness, whereas Trunk reaches the time limit.
R2N is thus competitive with an established trust-region solver. With exact second derivatives, R2N is preferable when gradient evaluations dominate the cost of an iteration, and Trunk when Hessian-vector products do. § 13.8 and § 13.9 repeat the comparison with models for which nonpositive curvature cannot arise.
R2N with a Limited-Memory Model
We now replace the exact Hessian with an L-BFGS approximation with memory q = 5 q = 5 q = 5 described in § 13.2 , which satisfies B k ≻ 0 B_k \succ0 B k ≻ 0 at every iteration. The shifted operator B k + σ k I B_k + \sigma_k I B k + σ k I is then positive definite; no direction of nonpositive curvature arises, and the NPC handler is inactive. We compare two subproblem solvers in § 13.7.1 , and repeat the comparison with Trunk in § 13.8 . We report elapsed time, objective evaluations and gradient evaluations.
Shifted L-BFGS Solver versus MINRES-QLP
We compare the shifted solver of Erway et al. [20 ] , which exploits the representation of the L-BFGS approximation to compute the exact minimizer of (21) at a cost of O ( q 2 n ) O(q^2 n) O ( q 2 n ) per solve, with a matrix-free MINRES-QLP solve of the same model, whose cost grows with the number of inner iterations. Both configurations use the Fast update of Algorithm 10.1, and the subproblem solver is the only difference.
The two are practically equivalent on this test set, and their profiles in the left column of Figure 9 are close on all three measures, with MINRES-QLP slightly above. On this test set, solving the subproblem exactly did not reduce the number of iterations. MINRES-QLP solves two more problems (Table 2 ): the shifted solver additionally reaches the time limit on JIMACK and on DJTL, where it makes slow progress.
Figure 9. Performance profiles with the L-BFGS model (q = 5 q = 5 q = 5 ) and the Fast update of σ k \sigma_k σ k in R2N; rows show elapsed time, objective evaluations and gradient evaluations. Left column: R2N with MINRES-QLP (MINRES-QLP) and with the shifted solve of Erway et al. [20 ] (Shifted). Right column: R2N and Trunk, both with truncated CG as subproblem solver.
The solver of Erway et al. [20 ] remains the natural choice when an exact solve of the subproblem is wanted, for instance to separate the effect of the model from that of the subproblem accuracy.
R2N versus Trunk with L-BFGS
We repeat the comparison of § 13.6 with the L-BFGS model, using CG as subproblem solver on both sides.
The two solvers are closely matched. Trunk is slightly faster and requires slightly fewer objective evaluations on more problems in the right column of Figure 9 , and the advantage in gradient evaluations that R2N showed with exact second derivatives is now absent. Both solve 78 problems (Table 2 ). R2N additionally declares PARKCH unbounded, and Trunk fails with an exception on DJTL. Compared to the results of § 13.6 , R2N loses seven problems and Trunk four, and the difference in robustness between the two disappears.
R2NLS on Nonlinear Least-Squares Problems
We evaluate the nonlinear least-squares specialization of Algorithm 4.1 on the 177 least-squares problems described in § 13.1 .
We first compare R2NLS with the subproblem solvers LSMR [21 ] , which requires only products with J k J_k J k and J k T J_k^T J k T , and a sparse QR factorization of the matrix in (42) , computed with QRMumps [1 ] , which requires J k J_k J k explicitly. The rest of the algorithm is identical on both sides.
In terms of iterations and residual evaluations, QRMumps is the most efficient on more problems, yet LSMR is the fastest on more problems, and the time profile of QRMumps catches up with that of LSMR only for larger τ \tau τ . The two are equally robust, with 169 and 170 problems solved, and all failures are exhaustions of the time limit (Table 2 ). The solved sets differ by a few problems in each direction. As in § 13.5.3 , the test set favors the direct solver. Of course, R2NLS with LSMR requires neither the assembled Jacobian nor storage for its factors, and it remains the configuration we recommend for large problems. For small to moderate problems, QRMumps is a highly competitive alternative.
We repeat the comparison of § 13.6 on least-squares problems with TrunkNLS, the least-squares variant of Trunk in JSOSolvers.jl. Both share the Gauss-Newton model, LSMR as subproblem solver and the stopping tests. TrunkNLS is ahead on every measure. In elapsed time and in iterations, it is the most efficient solver on more than twice as many problems as R2NLS, and the gap is smaller in residual evaluations. The gap narrows as τ \tau τ grows, but TrunkNLS solves five more problems, and every problem solved by R2NLS is also solved by TrunkNLS (Table 2 ). The five are exhaustions of the time limit, and the difference in robustness is small. These results are consistent with the authors’ experience with the two implementations of the Levenberg-Marquardt method.
Discussion
As Proposition 13 and Theorem 3 show, in a regularized Newton method, the worst-case complexity is dictated by positive-curvature steps, not by the subproblem solver. Detecting nonpositive curvature, with MINRES or otherwise, does not improve the worst-case complexity of Algorithm 4.1 —see Theorem 4.
In practice, however, exploiting nonpositive curvature matters for performance. R2N only has an edge over a standard trust-region method when nonpositive curvature can arise—see Figure 8 and Figure 9 —, which suggests that its treatment deserves as much care in regularization methods as it traditionally receives in trust-region methods.
When subproblems are convex, we observe no advantage of regularization over a trust region. The main argument in favor of regularization is then that subproblems are unconstrained, so that direct solvers and specialized solvers such as that of Erway et al. [20 ] apply without modification.
Kanzow and Steck [30 ] use limited-memory quasi-Newton models and solve the subproblem exactly with variants of the direct method of Erway et al. [20 ] . They assume that { B k } \{B_k\} { B k } is bounded, and increase the regularization parameter when nonpositive curvature occurs. While it is known that several limited-memory quasi-Newton approximations remain bounded under standard assumptions [2 , 6 , 14 ] , boundedness remains an open question for full quasi-Newton approximations. Our analysis covers inexact solves and potentially unbounded { B k } \{B_k\} { B k } . In addition, our results suggest that exact solves with limited-memory quasi-Newton models yield no discernible advantage. In § 13.7.1 , the direct solver did not reduce the number of iterations compared to MINRES-QLP, and solved two fewer problems. Our approach and that of Kanzow and Steck [30 ] differ most with indefinite models such as L-SR1, where R2N exploits nonpositive curvature instead of increasing σ k \sigma_k σ k . Experiments with L-SR1 models, for R2N and Trunk alike, are the natural next step.
Several improvements to the solver are possible. Our density test is a proxy for the cost of a factorization. The symbolic analysis phase of a sparse factorization predicts the size of the factors, and could be used to choose between a direct and an iterative solver automatically. Shift invariance of the Krylov subspace could be exploited after a rejected step, either by reusing the Krylov subspace generated for the previous value of σ k \sigma_k σ k , or by solving for several values of σ k \sigma_k σ k at once with a shifted Krylov method such as the shifted variant of CG-Lanczos [24 ] . A similar idea is exploited in [19 ] in the context of a cubic regularization method. Preconditioning the Krylov solvers, e.g., with an incomplete factorization, is a natural way to combine both approaches, provided the preconditioner is positive definite so that nonpositive-curvature detection remains meaningful. Other Krylov solvers are potential candidates to solve the subproblem. A recent example is MinAres [45 ] , which minimizes ∥ A r k ∥ \lVert A r_k \rVert ∥ A r k ∥ and is well suited to inconsistent systems, which could occur when B k + σ k I B_k+\sigma_k I B k + σ k I is singular. Using it in R2N requires nonpositive-curvature detection and a Cauchy decrease guarantee similar to those of § 6.3 and § 6.4 .
Several questions remain open. Gratton et al. [27 ] regularize the Hessian with a multiple of ∥ ∇ f ( x k ) ∥ 1 / 2 \lVert\nabla f(x_k) \rVert^{1/2} ∥ ∇ f ( x k ) ∥ 1/2 and obtain a bound in O ( ∣ log ε ∣ ε − 3 / 2 ) O(|\log\varepsilon| \varepsilon^{-3/2}) O ( ∣ log ε ∣ ε − 3/2 ) . Whether such a rule can be combined with the update of Algorithm 4.1 , and how it affects the local rate, remains to be investigated. Equipping Trunk with MINRES-QLP would tell whether the advantage of MINRES-QLP over truncated CG carries over to trust-region methods. Finally, we do not know of an example that attains the bound of Theorem 3 when 0 < ζ < 1 0 < \zeta< 1 0 < ζ < 1 , or whether the bound of Theorem 6 is tight.
We used the large language model Claude Opus 5.5 (Anthropic) during the preparation of this paper. Below, we list each section of the paper and state whether it was written entirely by the human authors or whether AI contributed, and how. In every section, AI was used to edit the English and make the text more readable. All AI contributions were checked by the human authors, who also cross-checked each other’s work, and the human authors take full responsibility for the content of this paper.
Abstract, Introduction, Background, Models and Cauchy Decrease. Written by the human authors.
Algorithm Statement, Step Computation. The statement and proof of all results were developed and verified by the human authors, and AI was used to re-verify the proofs.
Convergence Analysis. Written by the human authors.
Structured Worst-Case Complexity. The statements and proofs of all results were developed and verified by the human authors, and AI was used to re-verify the proofs.
Slow Convergence of Algorithm 4.1 in the Absence of Nonpositive Curvature. The example, together with its lemma and proof, was constructed and verified by the human authors, re-verified with AI, and finally checked numerically to confirm that it satisfies the assumptions of the corresponding results.
Slow Convergence of Algorithm 4.1 in the Presence of Nonpositive Curvature. The design of the sequences { f k } \{f_k\} { f k } , { g k } \{g_k\} { g k } , { H k } \{H_k\} { H k } and { s k } \{s_k\} { s k } was done jointly with AI. The assumptions of Theorem 5 were formulated by the human authors with the help of AI. Lemmas 2 and 3 and Theorem 5 and their proofs were developed by both the human authors and AI: AI was used to re-evaluate them and to check that the assumptions hold, and the human authors extended the lemmas and their proofs. The final construction was re-evaluated by the human authors and checked numerically to confirm that it satisfies the assumptions of the corresponding results.
A Variant with Fast Local Convergence. The statements and proofs of all results were developed and verified by the human authors, and AI was used to re-verify the proofs.
A Variant for Nonlinear Least-Squares. Written by the human authors.
Implementation and Numerical Experiments. The text was written by the human authors. Most of the code was written by F. Rahbarnia, and an AI coding agent was used to clean and review the code as needed. The implementation and the numerical results were validated by the human authors.
Discussion. The human authors outlined the content of this section. AI was used to turn the outline into sentences, which the human authors edited for readability.
References
References. AI was used to check bibliographic data and to format entries, all of which were checked by the human authors.
Declarations
Availability of data and materials All test problems are from the CUTEst collection, which is publicly available. The results of all experiments are available at [https://github.com/farhadrc lass/r2n-smooth-benchmarks](https://github.com/farhad rclass/r2n-smooth-benchmarks).
Code availability R2N and R2NLS are part of JSOSolvers.jl v0.14.9, available at https://github.com/JuliaSmoothOptimizers/JSOSolvers.jl . The scripts that reproduce all numerical results are available at [https://github.com/farhad rclass/r2n-smooth-benchmarks](https://github.com/farhad rclass/r2n-smooth-benchmarks).