×

zbMATH — the first resource for mathematics

On the use of iterative methods in cubic regularization for unconstrained optimization. (English) Zbl 1308.90166
Summary: In this paper we consider the problem of minimizing a smooth function by using the adaptive cubic regularized (ARC) framework. We focus on the computation of the trial step as a suitable approximate minimizer of the cubic model and discuss the use of matrix-free iterative methods. Our approach is alternative to the implementation proposed in the original version of ARC, involving a linear algebra phase, but preserves the same worst-case complexity count. Further we introduce a new stopping criterion in order to properly manage the “over-solving” issue arising whenever the cubic model is not an adequate model of the true objective function. Numerical experiments conducted by using a nonmonotone gradient method as inexact solver are presented. The obtained results clearly show the effectiveness of the new variant of ARC algorithm.

MSC:
90C30 Nonlinear programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bellavia, S., Morini, B.: Strong local convergence properties of adaptive regularized methods for nonlinear least-squares. IMA J. Numer. Anal. doi:10.1093/imanum/dru021 · Zbl 1316.65061
[2] Bellavia, S; Cartis, C; Gould, NIM; Morini, B; Toint, PhL, Convergence of a regularized Euclidean residual algorithm for nonlinear least-squares, SIAM J. Numer. Anal., 48, 1-29, (2010) · Zbl 1218.90182
[3] Benson, HY; Shanno, DF, Interior-point methods for nonconvex nonlinear programming: cubic regularization, Comput. Optim. Appl., 58, 323-346, (2014) · Zbl 1305.90333
[4] Bishop, C.M.: Pattern Recognition and Machine Learning. Springer, Berlin (2006) · Zbl 1107.68072
[5] Cartis, C; Gould, NIM; Toint, PhL, On the complexity of steepest descent, newton’s and regularized newton’s methods for nonconvex unconstrained optimization, SIAM J. Optim., 20, 2833-2852, (2010) · Zbl 1211.90225
[6] Cartis, C; Gould, NIM; Toint, PhL, Adaptive cubic overestimation methods for unconstrained optimization. part I: motivation, convergence and numerical results, Math. Program. A, 127, 245-295, (2011) · Zbl 1229.90192
[7] Cartis, C; Gould, NIM; Toint, PhL, Adaptive cubic overestimation methods for unconstrained optimization. part II: worst-case function-evaluation complexity, Math. Program. A, 130, 295-319, (2011) · Zbl 1229.90193
[8] Cartis, C; Gould, NIM; Toint, PhL, An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity, IMA J. Numer. Anal., 32, 1662-1695, (2012) · Zbl 1267.65061
[9] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program. Ser. A, 91, 201-213, (2002) · Zbl 1049.90004
[10] Gould, NIM; Orban, D; Toint, PhL, 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
[11] Gould, NIM; Orban, D; Toint, PhL, Cuter (and sifdec), a constrained and unconstrained testing environment, revisited, ACM Trans. Math. Softw., 29, 373-394, (2003) · Zbl 1068.90526
[12] Gould, NIM; Porcelli, M; Toint, PhL, Updating the regularization parameter in the adaptive cubic regularization algorithm, Comput. Optim. Appl., 53, 1-22, (2012) · Zbl 1259.90134
[13] Gould, NIM; Lucidi, S; Roma, M; Toint, PhL, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9, 504-525, (1999) · Zbl 1047.90510
[14] Griewank, A.: The Modification of Newton’s Method for Unconstrained Optimization by Bounding Cubic Terms. Technical Report NA, 12 (1981). Department of Applied Mathematics and Theoretical Physics, University of Cambridge, UK (1981)
[15] Grippo, L; Sciandrone, M, Nonmonotone globalization techniques for the Barzilai-Borwein gradient method, Comput. Optim. Appl., 23, 143-169, (2002) · Zbl 1028.90061
[16] Nesterov, Yu, Modified Gauss-Newton scheme with worst-case guarantees for global performance, Optim. Methods Softw., 22, 469-483, (2007) · Zbl 1136.65051
[17] Nesterov, Yu; Polyak, BT, Cubic regularization of newton’s method and its global performance, Math. Program., 108, 177-205, (2006) · Zbl 1142.90500
[18] Toint, L, Nonlinear stepsize control, trust regions and regularizations for unconstrained optimization, Optim. Methods Softw., 28, 82-95, (2013) · Zbl 1270.90078
[19] Weiser, M; Deuflhard, P; Erdmann, B, Affine conjugate adaptive Newton methods for nonlinear elastomechanics, Optim. Methods Softw., 22, 413-431, (2007) · Zbl 1128.74007
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.