### Abstract

Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε-
^{−3∕2} ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-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 (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε-
_{P} and ε-
_{D} being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.

Original language | English |
---|---|

Title of host publication | Springer Optimization and Its Applications |

Subtitle of host publication | Algorithms, Complexity and Applications |

Editors | Iannis Demetriou, Panos Pardalos |

Publisher | Springer Heidelberg |

Chapter | 1 |

Pages | 5-26 |

Number of pages | 22 |

ISBN (Electronic) | 978-3-030-12766-4 |

DOIs | |

Publication status | Published - Jun 2019 |

### Publication series

Name | Springer Optimization and Its Applications |
---|---|

Volume | 145 |

ISSN (Print) | 1931-6828 |

ISSN (Electronic) | 1931-6836 |

### Fingerprint

### Keywords

- Complexity theory
- Nonlinear optimization
- scaled optimality conditions

### Cite this

*Springer Optimization and Its Applications: Algorithms, Complexity and Applications*(pp. 5-26). (Springer Optimization and Its Applications; Vol. 145). Springer Heidelberg. https://doi.org/10.1007/978-3-030-12767-1_2

}

*Springer Optimization and Its Applications: Algorithms, Complexity and Applications.*Springer Optimization and Its Applications, vol. 145, Springer Heidelberg, pp. 5-26. https://doi.org/10.1007/978-3-030-12767-1_2

**Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models.** / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.

Research output: Contribution in Book/Catalog/Report/Conference proceeding › Chapter

TY - CHAP

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

AU - Cartis, Coralia

AU - Gould, Nicholas I M

AU - Toint, Philippe

PY - 2019/6

Y1 - 2019/6

N2 - Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- −3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-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 (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- P and ε- D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.

AB - Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- −3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-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 (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- P and ε- D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.

KW - Complexity theory

KW - Nonlinear optimization

KW - scaled optimality conditions

UR - http://www.scopus.com/inward/record.url?scp=85065814036&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-12767-1_2

DO - 10.1007/978-3-030-12767-1_2

M3 - Chapter

T3 - Springer Optimization and Its Applications

SP - 5

EP - 26

BT - Springer Optimization and Its Applications

A2 - Demetriou, Iannis

A2 - Pardalos, Panos

PB - Springer Heidelberg

ER -