Calandra, Henri and Gratton, Serge and Riccietti, Elisa
and Vasseur, Xavier
On High-Order Multilevel Optimization Strategies.
(2021)
SIAM Journal on Optimization, 31 (1). 307-330. ISSN 1052-6234
|
(Document in English)
PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 502kB |
Official URL: https://doi.org/10.1137/19M1255355
Abstract
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-th 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 worst-case complexity bound to reach first-order stationary points is also derived. A multilevel version of the well-known adaptive regularization by cubics (corresponding to q= 2 in our setting) has been implemented, as well as a multilevel third-order method (q= 3). Numerical experiments clearly highlight the relevance of the new multilevel approaches leading to considerable computational savings compared to their one-level counterparts.
Item Type: | Article |
---|---|
Audience (journal): | International peer-reviewed journal |
Uncontrolled Keywords: | |
Institution: | French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE) Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE) Université de Toulouse > Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE) Other partners > Total (FRANCE) Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE) Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE) Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE) |
Laboratory name: | |
Statistics: | download |
Deposited On: | 27 Jan 2021 13:58 |
Repository Staff Only: item control page