Projects per year

### 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.

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 |
---|---|

Number of pages | 20 |

Journal | SIAM Journal on Optimization |

Volume | 26 |

Issue number | 2 |

Publication status | 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.

## Projects

- 2 Active

## Complexity in nonlinear optimization

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

1/11/08 → …

Project: Research

## Activities

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

Philippe Toint (Speaker)

23 Oct 2017

Activity: Talk or presentation types › Invited talk

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

Philippe Toint (Speaker)

24 Oct 2017

Activity: Talk or presentation types › Invited talk

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

Philippe Toint (Speaker)

10 Aug 2016

Activity: Talk or presentation types › Invited talk

## Cite this

Birgin, E., Gardenghi, J., Martinez, J-M., Santos, S., & Toint, P. (2016). Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models.

*SIAM Journal on Optimization*,*26*(2).