Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints

Philippe Toint, Coralia Cartis, N. I. M. Gould

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

2 Téléchargements (Pure)

Résumé

We provide sharp worst-case evaluation complexity bounds for nonconvex minimization problems with general inexpensive constraints, i.e., problems where the cost of evaluating/ enforcing of the (possibly nonconvex or even disconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend, or improve all known upper and lower complexity bounds for nonconvex unconstrained and convexly constrained problems. It is shown that, given an accuracy level ∈, a degree of highest available Lipschitz continuous derivatives p, and a desired optimality order q between one and p, a conceptual regularization algorithm requires no more than O(∈ - p+1/p-q+1 ) evaluations of the objective function and its derivatives to compute a suitably approximate qth order minimizer. With an appropriate choice of the regularization, a similar result also holds if the pth derivative is merely Holder rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems; we also give reasons for the optimality of regularization methods from a worst-case complexity point of view, within a large class of algorithms that use the same derivative information.

langue originaleAnglais
Pages (de - à)513-541
Nombre de pages29
journalSIAM Journal on Optimization
Volume30
Numéro de publication1
Les DOIs
Etat de la publicationPublié - janv. 2020

Empreinte digitale Examiner les sujets de recherche de « Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints ». 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

    • 1 Discours invité

    Recent results in worst-case evaluation complexity for smooth and non-smooth, exact and inexact, nonconvex optimization

    Philippe TOINT (Orateur)

    8 mai 2020

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

    Contient cette citation