Error estimates for iterative algorithms for minimizing regularized quadratic subproblems

References

• S. Adachi, S. Iwata, Y. Nakatsukasa, and A. Takeda, Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM J. Optim. 27(1) (2017), pp. 269–291. doi: 10.1137/16M1058200
   Web of Science ®Google Scholar
• O. Axelsson, Iterative Solution Methods, Cambridge University Press, Cambridge, 1996.
   Google Scholar
• O. Axelsson and I. Kaporin, On the sublinear and superlinear rate of convergence of conjugate gradient methods, Numer. Algorithms 25(1) (2000), pp. 1–22. doi: 10.1023/A:1016694031362
   Web of Science ®Google Scholar
• O. Axelsson and J. Karátson, Reaching the superlinear convergence phase of the CG method, J. Comput. Appl. Math. 260 (2014), pp. 244–257. doi: 10.1016/j.cam.2013.10.001
   Web of Science ®Google Scholar
• A. Beck and Y. Vaisbourd, Globally solving the trust region subproblem using simple first-order methods, SIAM J. Optim. 28(3) (2018), pp. 1951–1967. doi: 10.1137/16M1150281
   Web of Science ®Google Scholar
• T. Bianconcini, G. Liuzzi, B. Morini, and M. Sciandrone, On the use of iterative methods in cubic regularization for unconstrained optimization, Comput. Optim. Appl. 60(1) (2015), pp. 35–57. doi: 10.1007/s10589-014-9672-x
   Web of Science ®Google Scholar
• Y. Carmon and J.C. Duchi, Gradient descent efficiently finds the cubic-regularized non-convex Newton step, (2016). Available at arXiv:1612.00547.
   Google Scholar
• Y. Carmon and J.C. Duchi, Analysis of Krylov subspace solutions of regularized nonconvex quadratic problems, (2018). Available at arXiv:1806.09222v1.
   Google Scholar
• C. Cartis, N.I.M. Gould, and Ph. L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results, Math. Program. Ser. A 127(2) (2011), pp. 245–295. doi: 10.1007/s10107-009-0286-5
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and M. Lange, On monotonic estimates of the norm of the minimizers of regularized quadratic functions in Krylov spaces. Tech. Rep. RAL-TR-2019, Rutherford Appleton Laboratory, Chilton, Oxfordshire, England, 2019.
   Google Scholar
• A.R. Conn, N.I.M. Gould, and Ph. L. Toint, Trust-Region Methods, SIAM, Philadelphia, 2000.
   Google Scholar
• S. Demko, W.F. Moss, and P.W. Smith, Decay rates for inverses of band matrices, Math. Comput. 43(168) (1984), pp. 491–499. doi: 10.1090/S0025-5718-1984-0758197-9
   Web of Science ®Google Scholar
• J.B. Erway and P.E. Gill, A subspace minimization method for the trust-region step, SIAM J. Optim. 20(3) (2009), pp. 1439–1461. doi: 10.1137/08072440X
   Web of Science ®Google Scholar
• J.B. Erway, P.E. Gill, and J.D. Griffin, Iterative methods for finding a trust-region step, SIAM J. Optim. 20(2) (2009), pp. 1110–1131. doi: 10.1137/070708494
   Web of Science ®Google Scholar
• C. Fortin and H. Wolkowicz, The trust region subproblem and semidefinite programming, Optim. Methods Softw. 19(1) (2004), pp. 41–67. doi: 10.1080/10556780410001647186
   Web of Science ®Google Scholar
• D.M. Gay, Computing optimal locally constrained steps, SIAM J. Sci. Statist. Comput. 2(2) (1981), pp. 186–197. doi: 10.1137/0902016
   Web of Science ®Google Scholar
• G.H. Golub and C.F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, 1996.
   Google Scholar
• N.I.M. Gould, S. Lucidi, M. Roma, and Ph. L. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim. 9(2) (1999), pp. 504–525. doi: 10.1137/S1052623497322735
   Web of Science ®Google Scholar
• N.I.M. Gould, D. Orban, and Ph. L. Toint, GALAHAD—a library of thread-safe fortran 90 packages for large-scale nonlinear optimization, ACM Trans. Math. Soft. 29(4) (2003), pp. 353–372. doi: 10.1145/962437.962438
   Web of Science ®Google Scholar
• N.I.M. Gould, D.P. Robinson, and H.S. Thorne, On solving trust-region and other regularised subproblems in optimization, Math. Program. Comput. 2(1) (2010), pp. 21–57. doi: 10.1007/s12532-010-0011-7
   Google Scholar
• N.I.M. Gould, D. Orban, and Ph. L. Toint, CUTEst: A constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl. 60(3) (2015), pp. 545–557. doi: 10.1007/s10589-014-9687-3
   Web of Science ®Google Scholar
• A. Greenbaum, Iterative Methods for Solving Linear Systems, SIAM, Philadelphia, 1997.
   Google Scholar
• W.W. Hager, Minimizing a quadratic over a sphere, SIAM J. Optim. 12(1) (2001), pp. 188–208. doi: 10.1137/S1052623499356071
   Web of Science ®Google Scholar
• E. Hazan and T. Koren, A linear-time algorithm for trust region problems, Math. Program. 158(1–2) (2016), pp. 363–381. doi: 10.1007/s10107-015-0933-y
   Web of Science ®Google Scholar
• N. Ho-Nguyen and F. Kilinç-Karzan, A second-order cone based approach for solving the trust-region subproblem and its variants, (2016). Available at arXiv:1603.03366.
   Google Scholar
• J. Lampe, M. Rojas, D.C. Sorensen, and H. Voss, Accelerating the LSTRS algorithm, SIAM J. Sci. Comput. 33(1) (2011), pp. 175–194. doi: 10.1137/090764426
   Web of Science ®Google Scholar
• J. Liesen and Z. Strakoš, Krylov Subspace Methods, Oxford University Press, Oxford, 2013.
   Google Scholar
• L. Lukšan, C. Matonoha, and J. Vlček, On Lagrange multipliers of trust-region subproblems, BIT Numer. Math. 48(4) (2008), pp. 763–768. doi: 10.1007/s10543-008-0197-5
   Web of Science ®Google Scholar
• J.M. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim. 4(1) (1994), pp. 159–176. doi: 10.1137/0804009
   Web of Science ®Google Scholar
• J.J. Moré and D.C. Sorensen, Computing a trust region step, SIAM J. Sci. Statist. Comput. 4(3) (1983), pp. 553–572. doi: 10.1137/0904038
   Web of Science ®Google Scholar
• Yu. Nesterov and B.T. Polyak, Cubic regularization of Newton method and its global performance, Math. Program. 108(1) (2006), pp. 177–205. doi: 10.1007/s10107-006-0706-8
   Web of Science ®Google Scholar
• J. Nocedal and S.J. Wright, Numerical Optimization, 2nd ed., Series in Operations Research. Springer Verlag, Heidelberg, Berlin, New York, 2006.
   Google Scholar
• F. Rendl and H. Wolkowicz, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program. Ser. B 77(2) (1997), pp. 273–299.
   Web of Science ®Google Scholar
• M. Rojas, S.A. Santos, and D.C. Sorensen, A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim. 11(3) (2001), pp. 611–646. doi: 10.1137/S105262349928887X
   Web of Science ®Google Scholar
• M. Rojas, S.A. Santos, and D.C. Sorensen, Algorithm 873: LSTRS: MATLAB software for large-scale trust-region subproblems and regularization, ACM Trans. Math. Softw. 34(2) (2008), Article 11. doi: 10.1145/1326548.1326553
   Web of Science ®Google Scholar
• C.W. Royer and S.J. Wright, Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization, (2017). Available at arXiv:1706.03131v2.
   Google Scholar
• T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal. 20(3) (1983), pp. 626–637. doi: 10.1137/0720042
   Web of Science ®Google Scholar
• Ph. L. Toint, Towards an efficient sparsity exploiting Newton method for minimization, in Sparse Matrices and Their Uses, I.S. Duff, eds., Academic Press, London, 1981, pp. 57–88.
   Google Scholar
• H.A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, Cambridge, 2003.
   Google Scholar
• J. Wong and Y. Xia, A linear-time algorithm for the trust region subproblem based on hidden convexity, Optim. Lett. 11(8) (2017), pp. 1639–1646. doi: 10.1007/s11590-016-1070-0
   Web of Science ®Google Scholar
• L.-H. Zhang and C. Shen, A nested Lanczos method for the trust-region subproblem, SIAM J. Sci. Comput. 40(4) (2018), pp. A2005–A2032. doi: 10.1137/17M1145914
   Web of Science ®Google Scholar
• L.-H. Zhang, C. Shen, and R.-C. Li, On the generalized Lanczos trust-region method, SIAM J. Optim. 27(3) (2017), pp. 2110–2142. doi: 10.1137/16M1095056
   Web of Science ®Google Scholar