Optimization Online


Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Coralia Cartis (coralia.cartis***at***maths.ox.ac.uk)
Nick Gould (nick.gould***at***stfc.ac.uk)
Philippe L. Toint (philippe.toint***at***unamur.be)

Abstract: Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of $O(\epsilon^{-3/2})$ proved by Cartis, Gould and Toint (IMAJNA 32(4) 2012, pp.1662-1695) for computing an $\epsilon$-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are used, resulting in a bound of $O(\epsilon^{-(p+1)/p})$ evaluations whenever derivatives of order $p$ are available. It is also shown that the bound of $O(\ep^{-1/2}\ed^{-3/2})$ evaluations ($\ep$ and $\ed$ being primal and dual accuracy thresholds) suggested by Cartis, Gould and Toint (SINUM, 53(2), 2015, pp.836-851) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of $O(\ep^{-1/p}\ed^{-(p+1)/p})$ evaluations under similarly weakened assumptions.

Keywords: nonlinear optimization, complexity theory, high-order models, worst-case analysis

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Nonlinear Optimization (Bound-constrained Optimization )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Techreport naXys-11-2015, Namur Center for Complex Systems, University of Namur (Belgium), 2015

Download: [PDF]

Entry Submitted: 10/19/2015
Entry Accepted: 10/19/2015
Entry Last Modified: 11/19/2015

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