On high-order multilevel optimization strategies
| Autor: | Serge Gratton, Henri Calandra, Elisa Riccietti, Xavier Vasseur |
|---|---|
| Přispěvatelé: | Total E&P, Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut National Polytechnique (Toulouse) (Toulouse INP), École normale supérieure - Lyon (ENS Lyon), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), Gratton, Serge, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), École normale supérieure de Lyon (ENS de Lyon), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), Centre National de la Recherche Scientifique - CNRS (FRANCE), Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE), Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE), Total (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), Institut de Recherche en Informatique de Toulouse - IRIT (Toulouse, France) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
Multilevel methods 0211 other engineering and technologies 010103 numerical & computational mathematics 02 engineering and technology Global convergence Complexity estimation 01 natural sciences Mathematics::Numerical Analysis Theoretical Computer Science Nonlinear programming Multilevel optimization Tensor methods FOS: Mathematics High-order optimization model Mathematics - Numerical Analysis 0101 mathematics High order Computer Science::Operating Systems Mathematics 021103 operations research Numerical Analysis (math.NA) Taylor models [MATH.MATH-NA] Mathematics [math]/Numerical Analysis [math.NA] Nonlinear optimization Optimization methods Error bound Minification Recherche opérationnelle Software [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA] |
| Zdroj: | SIAM Journal on Optimization SIAM Journal on Optimization, 2020, 31 (1), pp.307-330. ⟨10.1137/19M1255355⟩ SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2020, 31 (1), pp.307-330. ⟨10.1137/19M1255355⟩ HAL |
| ISSN: | 1052-6234 |
| Popis: | SIAM: Society for Industrial and Applied Mathematics; International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|