Optimization Online


Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization

Coralia Cartis(coralia.cartis***at***maths.ox.ac.uk)
Nicholas I. M. Gould(nick.gould***at***stfc.ac.uk)
P Toint(philippe.toint***at***unamur.be)

Abstract: High-order optimality conditions for convexly-constrained nonlinear optimization problems are analyzed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order $\epsilon$-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that, if derivatives of the objective function up to order $q \geq 1$ can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most $O(\epsilon^{-(q+1)})$ evaluations of $f$ and its derivatives to compute an $\epsilon$-approximate $q$-th order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed showing that the obtained evaluation complexity bounds are essentially sharp.

Keywords: nonlinear optimization, high-order optimality conditions, complexity theory, machine learning

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Nonlinear Optimization (Bound-constrained Optimization )

Category 3: Nonlinear Optimization (Unconstrained Optimization )

Citation: Report naXys-06-2016, Namur Centre for Complex Systems, University of Namur, Namur, Belgium

Download: [PDF]

Entry Submitted: 08/16/2016
Entry Accepted: 08/16/2016
Entry Last Modified: 08/16/2016

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