Second-order optimality and beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Résultats de recherche: Contribution à un journal/une revueArticle

Résumé

High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order ϵ-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order q≥ 1 can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most O(ϵ - ( q + 1 )) evaluations of f and its derivatives to compute an ϵ-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.

langue originaleAnglais
Pages (de - à)1073-1107
Nombre de pages35
journalFoundations of Computational Mathematics
Volume18
Numéro de publication5
Les DOIs
Etat de la publicationPublié - 1 oct. 2018

Empreinte digitale Examiner les sujets de recherche de « Second-order optimality and beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization ». Ensemble, ils forment une empreinte digitale unique.

  • Projets

    Complexity in nonlinear optimization

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

    1/11/08 → …

    Projet: Recherche

    Activités

    • 7 Discours invité
    • 2 Participation à une conférence, un congrès
    • 2 Visite à une institution académique externe

    Oxford University

    Philippe Toint (Chercheur visiteur)

    20 nov. 20196 déc. 2019

    Activité: Types de Visite d'une organisation externeVisite à une institution académique externe

    Departement of Applied Mathematics, Polytechnic University of Hong Kong

    Philippe Toint (Chercheur visiteur)

    15 nov. 201815 déc. 2018

    Activité: Types de Visite d'une organisation externeVisite à une institution académique externe

    Recent Advances in Evaluation Complexity for Nonconvex Optimization

    Philippe Toint (Orateur)

    28 nov. 2018

    Activité: Types de discours ou de présentationDiscours invité

    Contient cette citation