Projets par an
Résumé
A regularization algorithm using inexact function values and inexact derivatives is proposed and its evaluation complexity analyzed. This algorithm is applicable to unconstrained problems and to problems with inexpensive constraints (that is, constraints whose evaluation and enforcement has negligible cost) under the assumption that the derivative of highest degree is βHölder continuous. It features a very flexible adaptive mechanism for determining the inexactness which is allowed, at each iteration, when computing objective function values and derivatives. The complexity analysis covers arbitrary optimality order and arbitrary degree of available approximate derivatives. It extends results of Cartis, Gould, and Toint [SIAM J. Optim., to appear] on the evaluation complexity to the inexact case: if a qthorder minimizer is sought using approximations to the first p derivatives, it is proved that a suitable approximate minimizer within ε is computed by the propposed algorithm in at most O[Formula presented] iterations and at most O[Formula presented] approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in O[Formula presented] evaluations. While the proposed framework remains so far conceptual for high degrees and orders, it is shown to yield simple and computationally realistic inexact methods when specialized to the unconstrained and boundconstrained first and secondorder cases. The deterministic complexity results are finally extended to the stochastic context, yielding adaptive samplesize rules for subsampling methods typical of machine learning.
langue originale  Anglais 

Pages (de  à)  28812915 
Nombre de pages  35 
journal  SIAM Journal on Optimization 
Volume  29 
Numéro de publication  4 
Les DOIs  
Etat de la publication  Publié  2 janv. 2020 
Empreinte digitale Examiner les sujets de recherche de « Adaptive regularization algorithms with inexact evaluations for nonconvex optimization ». 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

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é

5th Conference on Numerical Analysis and Optimization
Philippe Toint (Orateur)
6 janv. 2020 → 9 janv. 2020Activité: Types de Participation ou d'organisation d'un événement › Participation à un atelier/workshop, un séminaire, un cours

ENSEEIHTIRIT
Philippe Toint (Chercheur visiteur)
4 nov. 2019 → 8 nov. 2019Activité: Types de Visite d'une organisation externe › Visite à une institution académique externe