On high-order multilevel optimization strategies - Algorithmes Parallèles et Optimisation Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Optimization Année : 2020

On high-order multilevel optimization strategies

Résumé

We propose a new family of multilevel methods for unconstrained minimization. The resulting strategies are multilevel extensions of high-order optimization methods based on q-order Taylor models (with q ≥ 1) that have been recently proposed in the literature. The use of high-order models, while decreasing the worst-case complexity bound, makes these methods computationally more expensive. Hence, to counteract this effect, we propose a multilevel strategy that exploits a hierarchy of problems of decreasing dimension, still approximating the original one, to reduce the global cost of the step computation. A theoretical analysis of the family of methods is proposed. Specifically, local and global convergence results are proved and a complexity bound to reach first order stationary points is also derived. A multilevel version of the well known adaptive method based on cubic regularization (ARC, corresponding to q = 2 in our setting) has been implemented. Numerical experiments clearly highlight the relevance of the new multilevel approach leading to considerable computational savings in terms of floating point operations compared to the classical one-level strategy.
Fichier principal
Vignette du fichier
1904.04692.pdf (307.06 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02943229 , version 1 (18-09-2020)

Identifiants

Citer

Henri Calandra, Serge Gratton, Elisa Riccietti, Xavier Vasseur. On high-order multilevel optimization strategies. SIAM Journal on Optimization, 2020, 31 (1), pp.307-330. ⟨10.1137/19M1255355⟩. ⟨hal-02943229⟩
95 Consultations
87 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More