# 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 journalArticlepeer-review

## 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 language English 20 SIAM Journal on Optimization 26 2 Published - 2016

## Keywords

• Nonlinear optimization
• Complexity theory
• Constrained problems

## Fingerprint

Dive into the research topics of 'Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models'. Together they form a unique fingerprint.
• ### Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Bellavia, S., Gurioli, G., Morini, B. & Toint, P., 2 Jan 2020, 29, 4, p. 2881-2915 35 p.

Research output: Contribution to journalArticlepeer-review

Open Access
File
• ### Complexity of partially separable convexly constrained optimization with non-Lipschitzian singularities

Chen, X., Toint, P. & Wang, H., 15 Apr 2019, 29, 1, p. 874-903 30 p.

Research output: Contribution to journalArticlepeer-review

Open Access
File
• ### Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Cartis, C., Gould, N. I. M. & Toint, P., Jun 2019, Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Demetriou, I. & Pardalos, P. (eds.). Springer Heidelberg, p. 5-26 22 p. (Springer Optimization and Its Applications; vol. 145).

Research output: Contribution in Book/Catalog/Report/Conference proceedingChapter

• ### Complexity in nonlinear optimization

TOINT, P., Gould, N. I. M. & Cartis, C.

1/11/08 → …

Project: Research

1/01/87 → …

Project: Research Axis

• ### A path and some adventures in the jungle of high-order nonlinear optimization

Philippe Toint (Speaker)

24 Oct 2017

Activity: Talk or presentation typesInvited talk

• ### A path and some adventures in the jungle of high-order nonlinear optimization

Philippe Toint (Speaker)

23 Oct 2017

Activity: Talk or presentation typesInvited talk

• ### High-order optimality conditions in nonlinear optimization: necessary conditions and a conceptual approach of evaluation complexity

Philippe Toint (Speaker)

5 Aug 2016

Activity: Talk or presentation typesInvited talk