×

zbMATH — the first resource for mathematics

A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization. (English) Zbl 1360.49020
Summary: We propose a trust region algorithm for solving nonconvex smooth optimization problems. For any \(\overline{\epsilon}\in (0,\infty )\), the algorithm requires at most \(\mathcal{O}(\epsilon ^{-3/2})\) iterations, function evaluations, and derivative evaluations to drive the norm of the gradient of the objective function below any \(\epsilon \in (0,\overline{\epsilon}]\). This improves upon the \(\mathcal{O}(\epsilon ^{-2})\) bound known to hold for some other trust region algorithms and matches the \(\mathcal{O}(\epsilon^{-3/2})\) bound for the recently proposed Adaptive Regularisation framework using Cubics, also known as the arc algorithm. Our algorithm, entitled trace, follows a trust region framework, but employs modified step acceptance criteria and a novel trust region update mechanism that allow the algorithm to achieve such a worst-case global complexity bound. Importantly, we prove that our algorithm also attains global and fast local convergence guarantees under similar assumptions as for other trust region algorithms. We also prove a worst-case upper bound on the number of iterations, function evaluations, and derivative evaluations that the algorithm requires to obtain an approximate second-order stationary point.

MSC:
49M15 Newton-type methods
49M37 Numerical methods based on nonlinear programming
58C15 Implicit function theorems; global Newton methods on manifolds
65K05 Numerical mathematical programming methods
65K10 Numerical optimization and variational techniques
65Y20 Complexity and performance of numerical algorithms
68Q25 Analysis of algorithms and problem complexity
90C30 Nonlinear programming
90C60 Abstract computational complexity for mathematical programming problems
Software:
GQTPAR
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms, 3rd edn. Wiley, London (2006) · Zbl 1140.90040
[2] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[3] Cartis, C., Gould, N.I.M., Toint, Ph.L.: On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization problems. SIAM J. Optim. 20(6), 2833-2852 (2010) · Zbl 1211.90225
[4] 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. 127, 245-295 (2011) · Zbl 1229.90192
[5] Cartis, C., Gould, N.I.M., Toint, Ph.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part II: Worst-case function- and derivative-evaluation complexity. Math. Program. 130, 295-319 (2011) · Zbl 1229.90193
[6] Cartis, C., Gould, N.I.M., Toint. Ph.L.: Optimal Newton-type methods for nonconvex smooth optimization problems. Technical report ERGO 11-009, School of Mathematics, University of Edinburgh (2011)
[7] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2000) · Zbl 0958.65071
[8] Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1996) · Zbl 0847.65038
[9] 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 (1981)
[10] Griva, I., Nash, S.G., Sofer, A.: Linear and Nonlinear Optimization, 2nd edn. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2008) · Zbl 1159.90002
[11] Moré, JJ; Sorensen, DC, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572, (1983) · Zbl 0551.65042
[12] Nesterov, Yu; Polyak, BT, Cubic regularization of newton’s method and its global performance, Math. Program., 108, 117-205, (2006) · Zbl 1142.90500
[13] Nesterov, Y.: Introductory Lectures on Convex Optimization, vol. 87. Springer, Berlin (2004) · Zbl 1086.90045
[14] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, Berlin (2006)
[15] Ruszczynski, A.: Nonlinear Optimization. Princeton University Press, Princeton (2006) · Zbl 1108.90001
[16] 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.