×

zbMATH — the first resource for mathematics

A line-search algorithm inspired by the adaptive cubic regularization framework and complexity analysis. (English) Zbl 1417.90097
Summary: Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity among second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such a scaled norm, the obtained method behaves as a line search algorithm along the quasi-Newton direction with a special backtracking strategy. Under appropriate assumptions, the new algorithm enjoys the same convergence and complexity properties as adaptive regularized algorithm using cubics. The complexity for finding an approximate first-order stationary point can be improved to be optimal whenever a second-order version of the proposed algorithm is regarded. In a similar way, using the same scaled norm to define the trust-region neighborhood, we show that the trust-region algorithm behaves as a line search algorithm. The good potential of the obtained algorithms is shown on a set of large-scale optimization problems.

MSC:
90C06 Large-scale problems in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
Software:
CUTEst; GALAHAD
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071
[2] Yuan, Y., Recent advances in trust region algorithms, Math. Program., 151, 249-281, (2015) · Zbl 1317.65141
[3] Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs (1983) · Zbl 0579.65058
[4] Griewank, A.: The modification of Newton’s method for unconstrained optimization by bounding cubic terms. Technical report, NA/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, United Kingdom (1981)
[5] Nesterov, Y.; Polyak, BT, Cubic regularization of Newton’s method and its global performance, Math. Program., 108, 177-205, (2006) · Zbl 1142.90500
[6] Cartis, C.; Gould, NIM; Toint, PL, Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results, Math. Program., 127, 245-295, (2011) · Zbl 1229.90192
[7] Nesterov, Y.: Introductory Lectures on Convex Optimization. Kluwer Academic Publishers, Dordrecht (2004) · Zbl 1086.90045
[8] Gratton, S.; Sartenaer, A.; Toint, PL, Recursive trust-region methods for multiscale nonlinear optimization, SIAM J. Optim., 19, 414-444, (2008) · Zbl 1163.90024
[9] Cartis, C.; Sampaio, PR; Toint, PL, Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization, Optimization, 64, 1349-1361, (2015) · Zbl 1342.90180
[10] Cartis, C.; Gould, NIM; Toint, PL, Adaptive cubic overestimation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity, Math. Program., 130, 295-319, (2011) · Zbl 1229.90193
[11] Birgin, EG; Gardenghi, JL; Martínez, JM; Santos, SA; Toint, PL, Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Math. Program., 163, 359-368, (2017) · Zbl 1365.90236
[12] Cartis, C., Gould, N.I.M., Toint, P.L.: Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization. Technical report (2017)
[13] Curtis, FE; Robinson, DP; Samadi, M., A trust region algorithm with a worst-case iteration complexity of \(O(\epsilon ^{-3/2})\) for nonconvex optimization, Math. Program., 162, 1-32, (2017) · Zbl 1360.49020
[14] Martínez, JM; Raydan, M., Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization, J. Glob. Optim., 68, 367-385, (2017) · Zbl 1379.90029
[15] Birgin, EG; Martínez, JM, The use of quadratic regularization with a cubic descent condition for unconstrained optimization, SIAM J. Optim., 27, 1049-1074, (2017) · Zbl 1370.90260
[16] Bergou, E.; Diouane, Y.; Gratton, S., On the use of the energy norm in trust-region and adaptive cubic regularization subproblems, Comput. Optim. Appl., 68, 533-554, (2017) · Zbl 1390.90511
[17] Gould, NIM; Orban, D.; Toint, PL, GALAHAD, a library of thread-safe fortran 90 packages for large-scale nonlinear optimization, ACM Trans. Math. Softw., 29, 353-372, (2003) · Zbl 1068.90525
[18] Gould, NIM; Orban, D.; Toint, PL, CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl., 60, 545-557, (2015) · Zbl 1325.90004
[19] Paige, CC; Saunders, MA, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629, (1975) · Zbl 0319.65025
[20] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
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.