Error estimates for iterative algorithms for minimizing regularized quadratic subproblems

ABSTRACT

We derive bounds for the objective errors and gradient residuals when finding approximations to the solution of common regularized quadratic optimization problems within evolving Krylov spaces. These provide upper bounds on the number of iterations required to achieve a given stated accuracy. We illustrate the quality of our bounds on given test examples.

KEYWORDS:

• Trust-region subproblem
• regularized quadratic suubproblem
• error estimates
• Krylov subspace

2010 MATHEMATICS SUBJECT CLASSIFICATION:

• 90C30

Acknowledgments

The authors are very grateful for fruitful discussions on aspects of this work with Coralia Cartis, Tyrone Rees and Philippe Toint. We also appreciate very helpful comments from two referees and an associate editor.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Nicholas I. M. Gould http://orcid.org/0000-0002-1031-1588

Valeria Simoncini http://orcid.org/0000-0003-0795-5865

Notes

1 That the ‘arg min's in (4(4) $x_k=\underset{x\in {\mathcal{K}}_k}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}q\left(x\right)\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}\parallel x\parallel \le \delta$(4) ) and (5(5) $x_k=\underset{x\in {\mathcal{K}}_k}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}{q}^{\mathrm{R}}(x,\sigma ,p)$(5) ) are unique follows from Theorems 2.1 and 2.2, since g lies in ${\mathcal{K}}_k$ by construction.

2 The precise details of the implementations of GLTR and GLRT are, of course, important, but of no consequence in the bounds that we derive. Such bounds apply equally for any method that use the iterates (4(4) $x_k=\underset{x\in {\mathcal{K}}_k}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}q\left(x\right)\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}\parallel x\parallel \le \delta$(4) ) or (5(5) $x_k=\underset{x\in {\mathcal{K}}_k}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}{q}^{\mathrm{R}}(x,\sigma ,p)$(5) ).

3 This is equivalently the grade of H with respect to g

4 It will only be a local minimizer of ${\mu }_{\ast }^{+}>-{\lambda }_2$ [29].

5 Strictly [8, Corollary 3] only considers the case p = 3, but their method of proof holds in general.

6 Another thing we know but we have not used.: $0\le {\mu }_1\le {\mu }_k\le {\mu }_m$ for $k=1,\dots ,m$ [28].

7 The result would follow if we could show that ${\theta }_{1,k}+{\mu }_k$ decreases monotonically with growing k.

Additional information

Funding

This work was supported by the Engineering and Physical Sciences Research Council (EPSRC) grant EP/M025179/1.

Notes on contributors

Nicholas I. M. Gould

Nicholas I. M. Gould, an STFC Senior Fellow and Professor of Numerical Optimization, has interests in theoretical and practical optimization, and links to linear algebra. He is a SIAM Fellow, a winner of the Leslie Fox and Beale-Orchard Hays prizes, and his most recent book is /Trust-region Methods/(SIAM, 2000), written jointly with Andy Conn and Philippe Toint.

Valeria Simoncini

Valeria Simoncini, a Professor of Numerical Analysis, has interests in matrix analysis and computations with applications to scientific computing and engineering. She is a SIAM Fellow, and member of several editorial board, including SIAM J. Matrix Analysis and Applications, and SIAM J. Numerical Analysis.