Efficient Implementation of Third-Order Tensor Methods with Adaptive Regularization for Unconstrained Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917161344172032 |
|---|---|
| author | Cartis, Coralia Hauser, Raphael Liu, Yang Welzel, Karl Zhu, Wenqi |
| author_facet | Cartis, Coralia Hauser, Raphael Liu, Yang Welzel, Karl Zhu, Wenqi |
| contents | High-order tensor methods that employ local Taylor models of degree $p$ within adaptive regularization frameworks (AR$p$) have recently received significant attention, due to their optimal/improved global and local rates of convergence, for both convex and nonconvex optimization problems. In this paper, we showcase the numerical performance of standard second- and third-order variants ($p=2,3$) and propose novel techniques for key algorithmic aspects when $p\geq 3$. In particular, we extend the interpolation-based updating strategy for the regularization parameter introduced in [Gould, Porcelli and Toint, Comput Optim Appl (2012) 53:1--22] for $p=2$, to the case when $p \geq 3$. We identify fundamental differences between the different local minima of the regularised subproblems for $p=2$ and $p \geq 3$ and their effect on algorithm performance. For $p\geq 3$, we introduce a novel pre-rejection technique that rejects poor/unsuccessful subproblem minimizers prior to any function evaluation. Numerical studies showcase the efficiency improvements generated by our proposed modifications of the AR$3$ algorithm. We also assess numerically, the effect of different subproblem termination conditions and the choice of the initial regularization parameter on the overall algorithm performance. Finally, we benchmark our best-performing AR$3$ variants, as well as those in [Birgin et al., Optim Lett (2020) 14:815--838], against second-order ones (AR$2$). Encouraging results on standard test problems are obtained, confirming that AR$3$ variants can be made to outperform second-order variants in terms of objective evaluations, derivative evaluations, and number of subproblem solves. We provide an efficient, extensive and modular software package in MATLAB that includes many AR$2$ and AR$3$ variants, including Hessian- and tensor-free ones, allowing ease of use and experimentation for interested users. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_00404 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Implementation of Third-Order Tensor Methods with Adaptive Regularization for Unconstrained Optimization Cartis, Coralia Hauser, Raphael Liu, Yang Welzel, Karl Zhu, Wenqi Optimization and Control 90C30, 65K05, 49M37 High-order tensor methods that employ local Taylor models of degree $p$ within adaptive regularization frameworks (AR$p$) have recently received significant attention, due to their optimal/improved global and local rates of convergence, for both convex and nonconvex optimization problems. In this paper, we showcase the numerical performance of standard second- and third-order variants ($p=2,3$) and propose novel techniques for key algorithmic aspects when $p\geq 3$. In particular, we extend the interpolation-based updating strategy for the regularization parameter introduced in [Gould, Porcelli and Toint, Comput Optim Appl (2012) 53:1--22] for $p=2$, to the case when $p \geq 3$. We identify fundamental differences between the different local minima of the regularised subproblems for $p=2$ and $p \geq 3$ and their effect on algorithm performance. For $p\geq 3$, we introduce a novel pre-rejection technique that rejects poor/unsuccessful subproblem minimizers prior to any function evaluation. Numerical studies showcase the efficiency improvements generated by our proposed modifications of the AR$3$ algorithm. We also assess numerically, the effect of different subproblem termination conditions and the choice of the initial regularization parameter on the overall algorithm performance. Finally, we benchmark our best-performing AR$3$ variants, as well as those in [Birgin et al., Optim Lett (2020) 14:815--838], against second-order ones (AR$2$). Encouraging results on standard test problems are obtained, confirming that AR$3$ variants can be made to outperform second-order variants in terms of objective evaluations, derivative evaluations, and number of subproblem solves. We provide an efficient, extensive and modular software package in MATLAB that includes many AR$2$ and AR$3$ variants, including Hessian- and tensor-free ones, allowing ease of use and experimentation for interested users. |
| title | Efficient Implementation of Third-Order Tensor Methods with Adaptive Regularization for Unconstrained Optimization |
| topic | Optimization and Control 90C30, 65K05, 49M37 |
| url | https://arxiv.org/abs/2501.00404 |