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
Etat de la publicationPublié - juin 2019

Série de publications

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

Financement

Acknowledgements The work of the second author was supported by EPSRC grants EP/I013067/1 and EP/M025179/1. The third author gratefully acknowledges the financial support of the Belgian Fund for Scientific Research, the Leverhulme Trust and Balliol College (Oxford).

Bailleurs de fondsNuméro du bailleur de fonds
Engineering and Physical Sciences Research CouncilEP/I013067/1, EP/M025179/1
Leverhulme Trust
Fonds De La Recherche Scientifique - FNRS
Balliol college

    Empreinte digitale

    Examiner les sujets de recherche de « Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models ». Ensemble, ils forment une empreinte digitale unique.

    Contient cette citation