Optimization Online


Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization

Clément W. Royer (croyer2***at***wisc.edu)
Stephen J. Wright (swright***at***cs.wisc.edu)

Abstract: There has been much recent interest in finding unconstrained local minima of smooth functions, due in part of the prevalence of such problems in machine learning and robust statistics. A particular focus is algorithms with good complexity guarantees. Second-order Newton-type methods that make use of regularization and trust regions have been analyzed from such a perspective. More recent proposals, based chiefly on first-order methodology, have also been shown to enjoy optimal iteration complexity rates, while providing additional guarantees on computational cost. In this paper, we present an algorithm with favorable complexity properties that differs in two significant ways from other recently proposed methods. First, it is based on line searches only: Each step involves computation of a search direction, followed by a backtracking line search along that direction. Second, its analysis is rather straightforward, relying for the most part on the standard technique for demonstrating sufficient decrease in the objective from backtracking. In the latter part of the paper, we consider inexact computation of the search directions, using iterative methods in linear algebra: the conjugate gradient and Lanczos methods. We derive modified convergence and complexity results for these more practical methods.

Keywords: smooth nonconvex unconstrained optimization, line search, second-order necessary conditions, iteration complexity.

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Citation: Technical Report, June 2017.

Download: [PDF]

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