On the complexity of finding first-order critical points in constrained nonlinear optimization

Coralia Cartis, Nicholas I M Gould, Philippe L. Toint

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

86 Téléchargements (Pure)

Résumé

The complexity of finding e-Approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that O(e-2) in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

langue originaleAnglais
Pages (de - à)93-106
Nombre de pages14
journalMathematical Programming
Volume144
Numéro de publication1-2
Les DOIs
Etat de la publicationPublié - 2014

Empreinte digitale Examiner les sujets de recherche de « On the complexity of finding first-order critical points in 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

    • 4 Présentation orale
    • 3 Recherche/Enseignement dans une institution externe
    • 1 Participation à un atelier/workshop, un séminaire, un cours
    • 1 Visite à une institution académique externe

    How much patience do you have? Issues in complexity for nonlinear optimization

    Philippe Toint (Orateur invité)

    5 févr. 2016

    Activité: Types de discours ou de présentationPrésentation orale

    Polytechnic University of Hong Kong

    Philippe Toint (Chercheur visiteur)

    31 janv. 201614 févr. 2016

    Activité: Types de Visite d'une organisation externeRecherche/Enseignement dans une institution externe

    How much patience do you have? Issues in complexity for nonlinear optimization

    Philippe Toint (Orateur)

    31 janv. 2016

    Activité: Types de discours ou de présentationPrésentation orale

    Prix

    Leverhulme Fellow

    TOINT, Philippe (Bénéficiaire), sept. 2015

    Prix: Bourse attribuée par concours

    Contient cette citation