- A line-search algorithm inspired by the adaptive cubic regularization framework with a worst-case complexity $\mathcal{O}(\epsilon^{-3/2})$ E. Bergou (el-houcine.bergoujouy.inra.fr) Y. Diouane (youssef.diouaneisae.fr) S. Gratton (serge.grattonenseeiht.fr) Abstract: Adaptive regularized framework using cubics (ARC) has emerged as an alternative to line-search and trust-region for smooth nonconvex optimization, with an optimal complexity amongst second-order methods. In this paper, we propose and analyze the use of a special (iteration dependent) scaled norm in ARC of the form $\|x\|_M= \sqrt{x^{\top}Mx}$ for $x \in \real^n$, where $M$ is a symmetric positive definite matrix satisfying specific secant equation. Within the proposed norm, ARC behaves as a line-search algorithm along the Newton direction, with a special backtracking strategy and acceptability condition. Under appropriate assumptions, the obtained algorithm enjoys the same convergence and complexity properties as ARC, in particular the complexity for finding an approximate first-order stationary point is $\mathcal{O}(\epsilon^{-3/2})$. Furthermore, using the same scaled norm in the trust-region framework, we have derived a second line-search algorithm. The good potential of the obtained algorithms is showed on a set of large scale optimization problems. Keywords: Nonlinear optimization, unconstrained optimization, line-search methods, adaptive regularized framework using cubics, trust-region methods, worst-case complexity. Category 1: Nonlinear Optimization (Unconstrained Optimization ) Citation: Download: [PDF]Entry Submitted: 06/16/2017Entry Accepted: 06/16/2017Entry Last Modified: 12/04/2017Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.