×

zbMATH — the first resource for mathematics

Error estimates for iterative algorithms for minimizing regularized quadratic subproblems. (English) Zbl 1428.90160
Summary: 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.

MSC:
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adachi, S.; Iwata, S.; Nakatsukasa, Y.; Takeda, A., Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM J. Optim., 27, 1, 269-291 (2017) · Zbl 1359.49009
[2] Axelsson, O., Iterative Solution Methods (1996), Cambridge University Press: Cambridge University Press, Cambridge
[3] Axelsson, O.; Kaporin, I., On the sublinear and superlinear rate of convergence of conjugate gradient methods, Numer. Algorithms, 25, 1, 1-22 (2000) · Zbl 0972.65024
[4] Axelsson, O.; Karátson, J., Reaching the superlinear convergence phase of the CG method, J. Comput. Appl. Math., 260, 244-257 (2014) · Zbl 1293.65045
[5] Beck, A.; Vaisbourd, Y., Globally solving the trust region subproblem using simple first-order methods, SIAM J. Optim., 28, 3, 1951-1967 (2018) · Zbl 1455.90104
[6] Bianconcini, T.; Liuzzi, G.; Morini, B.; Sciandrone, M., On the use of iterative methods in cubic regularization for unconstrained optimization, Comput. Optim. Appl., 60, 1, 35-57 (2015) · Zbl 1308.90166
[7] Carmon, Y. and Duchi, J.C., Gradient descent efficiently finds the cubic-regularized non-convex Newton step, (2016). Available at arXiv:1612.00547. · Zbl 07105232
[8] Carmon, Y. and Duchi, J.C., Analysis of Krylov subspace solutions of regularized nonconvex quadratic problems, (2018). Available at arXiv:1806.09222v1.
[9] Cartis, C.; Gould, N. I.M.; Toint, Ph. L., Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results, Math. Program. Ser. A, 127, 2, 245-295 (2011) · Zbl 1229.90192
[10] Cartis, C., Gould, N.I.M., and Lange, M., 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.
[11] Conn, A. R.; Gould, N. I.M.; Toint, Ph. L., Trust-Region Methods (2000), SIAM: SIAM, Philadelphia
[12] Demko, S.; Moss, W. F.; Smith, P. W., Decay rates for inverses of band matrices, Math. Comput., 43, 168, 491-499 (1984) · Zbl 0568.15003
[13] Erway, J. B.; Gill, P. E., A subspace minimization method for the trust-region step, SIAM J. Optim., 20, 3, 1439-1461 (2009) · Zbl 1195.49042
[14] Erway, J. B.; Gill, P. E.; Griffin, J. D., Iterative methods for finding a trust-region step, SIAM J. Optim., 20, 2, 1110-1131 (2009) · Zbl 1189.49049
[15] Fortin, C.; Wolkowicz, H., The trust region subproblem and semidefinite programming, Optim. Methods Softw., 19, 1, 41-67 (2004) · Zbl 1070.65041
[16] Gay, D. M., Computing optimal locally constrained steps, SIAM J. Sci. Statist. Comput., 2, 2, 186-197 (1981) · Zbl 0467.65027
[17] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press, Baltimore · Zbl 0865.65009
[18] Gould, N. I.M.; Lucidi, S.; Roma, M.; Toint, Ph. L., Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9, 2, 504-525 (1999) · Zbl 1047.90510
[19] Gould, N. I.M.; Orban, D.; Toint, Ph. L., GALAHAD—a library of thread-safe fortran 90 packages for large-scale nonlinear optimization, ACM Trans. Math. Soft., 29, 4, 353-372 (2003) · Zbl 1068.90525
[20] Gould, N. I.M.; Robinson, D. P.; Thorne, H. S., On solving trust-region and other regularised subproblems in optimization, Math. Program. Comput., 2, 1, 21-57 (2010) · Zbl 1193.65098
[21] Gould, N. I.M.; Orban, D.; Toint, Ph. L., CUTEst: A constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl., 60, 3, 545-557 (2015) · Zbl 1325.90004
[22] Greenbaum, A., Iterative Methods for Solving Linear Systems (1997), SIAM: SIAM, Philadelphia · Zbl 0883.65022
[23] Hager, W. W., Minimizing a quadratic over a sphere, SIAM J. Optim., 12, 1, 188-208 (2001) · Zbl 1058.90045
[24] Hazan, E.; Koren, T., A linear-time algorithm for trust region problems, Math. Program., 158, 1-2, 363-381 (2016) · Zbl 1346.90654
[25] Ho-Nguyen, N. and Kilinç-Karzan, F., A second-order cone based approach for solving the trust-region subproblem and its variants, (2016). Available at arXiv:1603.03366.
[26] Lampe, J.; Rojas, M.; Sorensen, D. C.; Voss, H., Accelerating the LSTRS algorithm, SIAM J. Sci. Comput., 33, 1, 175-194 (2011) · Zbl 1368.65096
[27] Liesen, J.; Strakoš, Z., Krylov Subspace Methods (2013), Oxford University Press: Oxford University Press, Oxford · Zbl 1263.65034
[28] Lukšan, L.; Matonoha, C.; Vlček, J., On Lagrange multipliers of trust-region subproblems, BIT Numer. Math., 48, 4, 763-768 (2008) · Zbl 1163.90027
[29] Martínez, J. M., Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4, 1, 159-176 (1994) · Zbl 0801.65057
[30] Moré, J. J.; Sorensen, D. C., Computing a trust region step, SIAM J. Sci. Statist. Comput., 4, 3, 553-572 (1983) · Zbl 0551.65042
[31] Nesterov, Yu.; Polyak, B. T., Cubic regularization of Newton method and its global performance, Math. Program., 108, 1, 177-205 (2006) · Zbl 1142.90500
[32] Nocedal, J. and Wright, S.J., Numerical Optimization, 2nd ed., Series in Operations Research. Springer Verlag, Heidelberg, Berlin, New York, 2006. · Zbl 1104.65059
[33] Rendl, F.; Wolkowicz, H., A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program. Ser. B, 77, 2, 273-299 (1997) · Zbl 0888.90137
[34] Rojas, M.; Santos, S. A.; Sorensen, D. C., A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11, 3, 611-646 (2001) · Zbl 0994.65067
[35] Rojas, M.; Santos, S. A.; Sorensen, D. C., Algorithm 873: LSTRS: MATLAB software for large-scale trust-region subproblems and regularization, ACM Trans. Math. Softw., 34, 2 (2008) · Zbl 1291.65177
[36] Royer, C.W. and Wright, S.J., Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization, (2017). Available at arXiv:1706.03131v2.
[37] Steihaug, T., The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20, 3, 626-637 (1983) · Zbl 0518.65042
[38] Toint, Ph. L., 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. · Zbl 0463.65045
[39] van der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems (2003), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 1023.65027
[40] Wong, J.; Xia, Y., A linear-time algorithm for the trust region subproblem based on hidden convexity, Optim. Lett., 11, 8, 1639-1646 (2017) · Zbl 1410.90145
[41] Zhang, L.-H.; Shen, C., A nested Lanczos method for the trust-region subproblem, SIAM J. Sci. Comput., 40, 4, A2005-A2032 (2018) · Zbl 1402.90113
[42] Zhang, L.-H.; Shen, C.; Li, R.-C., On the generalized Lanczos trust-region method, SIAM J. Optim., 27, 3, 2110-2142 (2017) · Zbl 1380.90210
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.