-

 

 

 




Optimization Online





 

A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds

S. Gratton(serge.gratton***at***enseeiht.fr)
C. W. Royer(croyer2***at***wisc.edu)
L. N. Vicente(lnv***at***mat.uc.pt)

Abstract: In order to be provably convergent towards a second-order stationary point, optimization methods applied to nonconvex problems must necessarily exploit both first and second-order information. However, as revealed by recent complexity analyzes of some of these methods, the overall effort to reach second-order points is significantly larger when compared to the one of approaching first-order ones. In addition, there are other algorithmic schemes, initially designed with first-order convergence in mind, that do not appear to maintain the same first-order performance when modified to take second-order information into account. In this paper, we propose a technique that separately computes first and second-order steps, and that globally converges to second-order stationary points. Our approach is shown to lead to an improvement of the corresponding complexity bound with respect to the first-order optimality tolerance. Although the applicability of our ideas is wider, we focus the presentation on trust-region methods with and without derivatives.

Keywords: Worst-case complexity, global rates, first-order stationarity, second-order stationarity, decoupling, trust-region methods

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: S. Gratton, C. W. Royer, and L. N. Vicente, A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds, preprint 17-21, Dept. Mathematics, Univ. Coimbra.

Download: [PDF]

Entry Submitted: 04/21/2017
Entry Accepted: 04/21/2017
Entry Last Modified: 04/21/2017

Modify/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
Mathematical Optimization Society