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

Ernesto Birgin, John Gardenghi, José-Mario Martinez, Sandra Santos, Philippe Toint

Research output: Contribution to journalArticle

4 Downloads (Pure)

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 that strong guarantees (in terms of handling degeneracies) on the possible limit 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.
Original languageEnglish
Number of pages20
JournalSIAM Journal on Optimization
Volume26
Issue number2
Publication statusPublished - 2016

Fingerprint

KKT Conditions
Constrained optimization
Constrained Optimization
Nonlinear Optimization
Higher Order
First-order
Lagrange multipliers
Limit Point
Evaluation
Criticality
Iterate
Derivatives
Derivative
Model

Keywords

  • Nonlinear optimization
  • Complexity theory
  • Constrained problems

Cite this

Birgin, Ernesto ; Gardenghi, John ; Martinez, José-Mario ; Santos, Sandra ; Toint, Philippe. / Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models. In: SIAM Journal on Optimization. 2016 ; Vol. 26, No. 2.
@article{59d54b55ef8d4f3ab55e490430b07f50,
title = "Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models",
abstract = "The evaluation complexity of general nonlinear, possibly nonconvex,constrained optimization is analyzed. It is shown that, under suitablesmoothness conditions, an $\epsilon$-approximate first-order criticalpoint 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, andToint (2011, 2013). It is also shown that strong guarantees (in terms of handling degeneracies) on the possible limit 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, Constrained problems",
author = "Ernesto Birgin and John Gardenghi and Jos{\'e}-Mario Martinez and Sandra Santos and Philippe Toint",
year = "2016",
language = "English",
volume = "26",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics",
number = "2",

}

Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models. / Birgin, Ernesto; Gardenghi, John; Martinez, José-Mario; Santos, Sandra; Toint, Philippe.

In: SIAM Journal on Optimization, Vol. 26, No. 2, 2016.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Birgin, Ernesto

AU - Gardenghi, John

AU - Martinez, José-Mario

AU - Santos, Sandra

AU - Toint, Philippe

PY - 2016

Y1 - 2016

N2 - The evaluation complexity of general nonlinear, possibly nonconvex,constrained optimization is analyzed. It is shown that, under suitablesmoothness conditions, an $\epsilon$-approximate first-order criticalpoint 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, andToint (2011, 2013). It is also shown that strong guarantees (in terms of handling degeneracies) on the possible limit 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.

AB - The evaluation complexity of general nonlinear, possibly nonconvex,constrained optimization is analyzed. It is shown that, under suitablesmoothness conditions, an $\epsilon$-approximate first-order criticalpoint 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, andToint (2011, 2013). It is also shown that strong guarantees (in terms of handling degeneracies) on the possible limit 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.

KW - Nonlinear optimization

KW - Complexity theory

KW - Constrained problems

M3 - Article

VL - 26

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 2

ER -