Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization

C. Cartis, Phillipe Rodrigues Sampaio, Ph L. Toint

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

94 Téléchargements (Pure)

Résumé

The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth non-convex and unconstrained problems is investigated. The analysis covers a practical linesearch implementation of these popular methods, allowing for an unknown number of evaluations of the objective function (and its gradient) per iteration. It is shown that this class of methods shares the known complexity properties of a simple steepest-descent scheme and that an approximate first-order critical point can be computed in at most (Formula presented.) function and gradient evaluations, where (Formula presented.) is the user-defined accuracy threshold on the gradient norm.

langue originaleAnglais
Pages (de - à)1349-1361
Nombre de pages13
journalOptimization
Volume64
Numéro de publication5
Les DOIs
Etat de la publicationPublié - 4 mai 2015

Empreinte digitale Examiner les sujets de recherche de « Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained 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
    • 2 Recherche/Enseignement dans une institution externe
    • 1 Discours invité
    • 1 Visite à une institution académique externe

    A path and some adventures in the jungle of high-order nonlinear optimization

    Philippe Toint (Orateur)

    24 oct. 2017

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

    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

    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