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^{\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 )


Download: [PDF]

Entry Submitted: 06/16/2017
Entry Accepted: 06/16/2017
Entry Last Modified: 12/04/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