Optimization Online


Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models

E. G. Birgin(ebirgin***at***ime.usp.br)
J. L. Gardenghi(john***at***ime.usp.br)
J. M. Martinez(matinez***at***ime.unicamp.br)
S. A. Santos(snadra***at***ime.unicamp.br)
Ph. L. Toint(philippe.toint***at***unamur.be)

Abstract: The evaluation complexity of general nonlinear, possibly nonconvex,constrained optimization is analyzed. It is shown that, under suitable smoothness conditions, an $\epsilon$-approximate first-order critical point of the problem can be computed in order $O(\epsilon^{1-2(p+1)/p})$ evaluations of the problem's function and their first $p$ derivatives. This is achieved by using a two-phases algorithm inspired by Cartis, Gould, and Toint (2011, 2013). It is also shown thatstrong guarantees (in terms of handling degeneracies) on the possiblelimit points of the sequence of iterates generated by this algorithm can be obtained at the cost of increased complexity. At variance with previous results, the $\epsilon$-approximate first-order criticality is defined by satisfying a version of the KKT conditions with an accuracy that does not depend on the size of the Lagrange multipliers.

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

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Nonlinear Optimization (Bound-constrained Optimization )

Citation: naXys Technical Report 08-2015, UNamur, Belgium

Download: [PDF]

Entry Submitted: 07/22/2015
Entry Accepted: 07/22/2015
Entry Last Modified: 07/22/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