Projets par an
Résumé
We provide sharp worstcase 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/pq+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 worstcase complexity point of view, within a large class of algorithms that use the same derivative information.
langue originale  Anglais 

Pages (de  à)  513541 
Nombre de pages  29 
journal  SIAM Journal on Optimization 
Volume  30 
Numéro de publication  1 
Les DOIs  
Etat de la publication  Publié  janv. 2020 
Empreinte digitale
Examiner les sujets de recherche de « Sharp worstcase evaluation complexity bounds for arbitraryorder nonconvex optimization with inexpensive constraints ». Ensemble, ils forment une empreinte digitale unique.Projets
 2 Actif

Complexity in nonlinear optimization
TOINT, P., Gould, N. I. M. & Cartis, C.
1/11/08 → …
Projet: Recherche

ADALGOPT: ADALGOPT  Algorithmes avancés en optimisation nonlinéaire
1/01/87 → …
Projet: Axe de recherche
Activités
 1 Discours invité

Recent results in worstcase evaluation complexity for smooth and nonsmooth, exact and inexact, nonconvex optimization
Philippe TOINT (Orateur)
8 mai 2020Activité: Types de discours ou de présentation › Discours invité