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

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférenceChapitre

Résumé

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.

langue originaleAnglais
titreSpringer Optimization and Its Applications
Sous-titreAlgorithms, Complexity and Applications
rédacteurs en chefIannis Demetriou, Panos Pardalos
EditeurSpringer Heidelberg
Chapitre1
Pages5-26
Nombre de pages22
ISBN (Electronique)978-3-030-12766-4
Les DOIs
étatPublié - juin 2019

Série de publications

NomSpringer Optimization and Its Applications
Volume145
ISSN (imprimé)1931-6828
ISSN (Electronique)1931-6836

    Empreinte digitale

Contient cette citation

Cartis, C., Gould, N. I. M., & Toint, P. (2019). Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. Dans I. Demetriou, & P. Pardalos (eds.), Springer Optimization and Its Applications: Algorithms, Complexity and Applications (p. 5-26). (Springer Optimization and Its Applications; Vol 145). Springer Heidelberg. https://doi.org/10.1007/978-3-030-12767-1_2