Projets par an
Résumé
We introduce the concept of strong highorder approximate minimizers for
nonconvex optimization problems. These apply in both standard smooth and
composite nonsmooth settings, and additionally allow convex or inexpensive
constraints. An adaptive regularization algorithm is then proposed to find such
approximate minimizers. Under suitable Lipschitz continuity assumptions, whenever the feasible set is convex, it is shown that using a model of degree p, this algorithm will find a strong approximate qthorder minimizer in at most
O(max_{1 \leq j \leq q}\epsilon_j^{(p+1)/(pj+1)})
evaluations of the problem’s functions and their derivatives, where \epsilon_j is the jth order accuracy tolerance; this bound applies when either q = 1 or the problem is not composite with q \leq 2. For general noncomposite problems, even when the feasible set is nonconvex, the bound becomes
O(max_{1 \leq j \leq q}\epsilon_j^{q(p+1)/p})
evaluations. If the problem is composite, and either q > 1 or the
feasible set is not convex, the bound is then
O(max_{1 \leq j \leq q}\epsilon_j^{(q+1)})
evaluations. These results not only provide, to our knowledge, the first known
bound for (unconstrained or inexpensivelyconstrained) composite problems for optimality orders exceeding one, but also give the first sharp bounds for highorder strong approximate qth order minimizers of standard (unconstrained and inexpensively constrained) smooth problems, thereby complementing known results for weak minimizers.
langue originale  Anglais 

Éditeur  Arxiv 
Volume  200110802 
Etat de la publication  Publié  30 janv. 2020 
Empreinte digitale Examiner les sujets de recherche de « Strong Evaluation Complexity Bounds for ArbitraryOrder Optimization of Nonconvex Nonsmooth Composite Functions ». 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é