A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis
Preprint
Abstract
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 amongst 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 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.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- On the use of the energy norm in trust-region and adaptive cubic regularization subproblemsComputational Optimization and Applications, 2017
- Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimizationJournal of Global Optimization, 2016
- Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized modelsMathematical Programming, 2016
- Recent advances in trust region algorithmsMathematical Programming, 2015
- CUTEst: a Constrained and Unconstrained Testing Environment with safe threads for mathematical optimizationComputational Optimization and Applications, 2014
- Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexityMathematical Programming, 2010
- Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical resultsMathematical Programming, 2009
- Cubic regularization of Newton method and its global performanceMathematical Programming, 2006
- Introductory Lectures on Convex Optimization2004
- Benchmarking optimization software with performance profilesMathematical Programming, 2002