×

zbMATH — the first resource for mathematics

Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization. (English) Zbl 07319273
MSC:
90C26 Nonconvex programming, global optimization
49M05 Numerical methods based on necessary conditions
49M15 Newton-type methods
65K05 Numerical mathematical programming methods
90C60 Abstract computational complexity for mathematical programming problems
Software:
CUTEst; GQTPAR; HSL-VF05; tn
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan, and T. Ma, Finding approximate local minima faster than gradient descent, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), 2017. · Zbl 1369.68290
[2] E. Bergou, Y. Diouane, and S. Gratton, On the use of the energy norm in trust-region and adaptive cubic regularization subproblems, Comput. Optim. Appl., 68 (2017), pp. 533-554. · Zbl 1390.90511
[3] E. Bergou, Y. Diouane, and S. Gratton, A line-search algorithm inspired by the adaptive cubic regularization framework and complexity analysis, J. Optim. Theory Appl., 178 (2018), pp. 885-913. · Zbl 1417.90097
[4] Y. Carmon and J. C. Duchi, Analysis of Krylov subspace solutions of regularized nonconvex quadratic problems, in Advances in Neural Information Processing Systems 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, eds., 2018, pp. 10726-10736.
[5] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford, “Convex until proven guilty”: Dimension-free acceleration of gradient descent on non-convex functions, in Proceedings of the International Conference on Machine Learning, August 2017, Sydney, Australia, 2017, pp. 654-663.
[6] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford, Accelerated methods for non-convex optimization, SIAM J. Optim., 28 (2018), pp. 1751-1772. · Zbl 1400.90250
[7] C. Cartis, N. I. M. Gould, and P. L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity, Math. Program., 130 (2011), pp. 295-319. · Zbl 1229.90193
[8] C. Cartis, N. I. M. Gould, and P. L. Toint, Optimal Newton-Type Methods for Nonconvex Optimization, Tech. Report naXys-17-2011, Department of Mathematics, University of Namur, Namur, Belgium, 2011. · Zbl 1229.90193
[9] C. Cartis, N. I. M. Gould, and P. L. Toint, Complexity bounds for second-order optimality in unconstrained optimization, J. Complexity, 28 (2012), pp. 93-108. · Zbl 1245.65063
[10] C. Cartis, N. I. M. Gould, and P. L. Toint, Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization, in Proceedings of the International Congress of Mathematicians (ICM 2018), vol. 3, 2019, pp. 3697-3738.
[11] F. E. Curtis, D. P. Robinson, and M. Samadi, A trust region algorithm with a worst-case iteration complexity of \({O}\left(\epsilon^{-3/2}\right)\) for nonconvex optimization, Math. Program., 162 (2017), pp. 1-32. · Zbl 1360.49020
[12] F. E. Curtis, D. P. Robinson, and M. Samadi, An inexact regularized Newton framework with a worst-case iteration complexity of \(\mathcal{O}(\epsilon^{-3/2})\) for nonconvex optimization, IMA J. Numer. Anal., 39 (2019), pp. 1296-1327.
[13] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), pp. 201-213. · Zbl 1049.90004
[14] J.-P. Dussault, \(Arc_q\): A new adaptive regularization by cubics, Optim. Methods Softw., 33 (2018), pp. 322-335. · Zbl 1397.90356
[15] J.-P. Dussault and D. Orban, Scalable Adaptive Cubic Regularization Methods, Tech. Report G-2015-109, GERAD, 2015.
[16] N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9 (1999), pp. 504-525. · Zbl 1047.90510
[17] N. I. M. Gould, D. Orban, and P. L. Toint, CUTEst: A constrained and unconstrained testing environment with safe threads, Comput. Optim. Appl., 60 (2015), pp. 545-557. · Zbl 1325.90004
[18] N. I. M. Gould and V. Simoncini, Error Estimates for Iterative Algorithms for Minimizing Regularized Quadratic Subproblems, Tech. Report RAL-TR-2019-004, Rutherford Appleton Laboratory, 2019. · Zbl 1428.90160
[19] S. Gratton, A. Sartenaer, and P. L. Toint, Recursive trust-region methods for multiscale nonlinear optimization, SIAM J. Optim., 19 (2008), pp. 414-444. · Zbl 1163.90024
[20] E. Hazan and T. Koren, A linear-time algorithm for trust region problems, Math. Program., 158 (2016), pp. 363-381. · Zbl 1346.90654
[21] J. Kuczyński and H. Woźniakowski, Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1094-1122. · Zbl 0759.65016
[22] J. Kuczyński and H. Woźniakowski, Probabilistic bounds on the extremal eigenvalues and condition number by the Lanczos algorithm, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 672-691. · Zbl 0801.65034
[23] J. M. Martínez and M. Raydan, Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization, J. Global Optim., 68 (2017), pp. 367-385. · Zbl 1379.90029
[24] J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM J. Sci. Comput., 4 (1983), pp. 553-572. · Zbl 0551.65042
[25] S. G. Nash, Newton-type minimization via the Lanczos method, SIAM J. Numer. Anal., 21 (1984), pp. 770-788. · Zbl 0558.65041
[26] Y. Nesterov, Introductory Lectures on Convex Programming. Volume I: Basic Course, manuscript, 1998, p. 5.
[27] Y. Nesterov and B. T. Polyak, Cubic regularization of Newton method and its global performance, Math. Program., 108 (2006), pp. 177-205. · Zbl 1142.90500
[28] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer Ser. Oper. Res. Financ. Eng., Springer-Verlag, New York, 2006. · Zbl 1104.65059
[29] C. W. Royer, M. O’Neill, and S. J. Wright, A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization, Math. Program., 180 (2020), pp. 451-488. https://doi.org/10.1007/s10107-019-01362-7. · Zbl 1448.90081
[30] C. W. Royer and S. J. Wright, Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization, SIAM J. Optim., 28 (2018), pp. 1448-1477. · Zbl 1391.49055
[31] T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20 (1983), pp. 626-637. · Zbl 0518.65042
[32] P. L. Toint, Towards an efficient sparsity exploiting Newton method for minimization, in Sparse Matrices and Their Uses, I. S. Duff, ed., Academic Press, London, 1981, pp. 57-88. · Zbl 0463.65045
[33] J. Wang and Y. Xia, A linear-time algorithm for the trust region subproblem based on hidden convexity, Optim. Lett., 11 (2017), pp. 1639-1646. · Zbl 1410.90145
[34] L.-H. Zhang, C. Shen, and R.-C. Li, On the generalized Lanczos trust-region method, SIAM J. Optim., 27 (2017), pp. 2110-2142. · 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.