Optimization Online


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.bergou***at***jouy.inra.fr)
Y. Diouane(youssef.diouane***at***isae.fr)
S. Gratton(serge.gratton***at***enseeiht.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^TMx}$ for $x \in \mathbb{R}^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. The obtained line-search algorithm enjoys the same convergence and complexity properties as ARC, in particular the complexity for finding approximate first-order stationary points is $\mathcal{O}(\epsilon^{-3/2})$. Furthermore, we have proposed similar analysis when considering the trust-region framework. The good potential of the new line-search 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 )


Download: [PDF]

Entry Submitted: 06/16/2017
Entry Accepted: 06/16/2017
Entry Last Modified: 06/16/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society