Optimization Online


How to Characterize the Worst-Case Performance of Algorithms for Nonconvex Optimization

Frank E. Curtis(frank.e.curtis***at***gmail.com)
Daniel P. Robinson(daniel.p.robinson***at***gmail.com)

Abstract: A proposal is presented for how to characterize the worst-case performance of algorithms for solving smooth nonconvex optimization problems. Contemporary analyses characterize worst-case performance by providing, under certain broad assumptions on the objective function, an upper bound on the number of iterations (or function or derivative evaluations) required until a pth-order stationarity condition is approximately satisfied. However, this arguably leads to characterizations based on anomalous objective functions rather than on ones that are typically encountered in practice. By contrast, the proposal in this paper recommends to characterize worst-case performance over distinct regions of the search space. These regions are defined according to a partitioning of the search space based on whether or not regularized pth-order derivative models of the objective function predict a decrease proportional to an objective value error. This strategy can be adopted to characterize the behavior of algorithms when minimizing different classes of objective functions.

Keywords: nonlinear optimization, nonconvex optimization, worst-case iteration complexity, worst-case evaluation complexity, regularization methods, trust region methods

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: Lehigh ISE/COR@L Technical Report 18T-003

Download: [PDF]

Entry Submitted: 02/03/2018
Entry Accepted: 02/03/2018
Entry Last Modified: 02/03/2018

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