High-order tensor methods that employ local Taylor models of degree p within adaptive regularization frameworks (ARp) have recently received significant attention, due to their improved/optimal global and local rates of convergence, for both convex and nonconvex optimization problems. The numerical performance of tensor methods for general unconstrained optimization problems remains insufficiently explored/understood, which we address in this paper, by showcasing the numerical performance of standard second- and third-order variants (<InlineEquation ID="IEq1"> <EquationSource Format="TEX">$p=2,3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>=</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>) and proposing novel techniques for key algorithmic aspects when <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$p\ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, to improve the numerical efficiency of tensor variants. In particular, to improve the adaptive choice of the regularization parameter, we extend the interpolation-based updating strategy introduced in [Gould, Porcelli and Toint, Comput Optim Appl (2012) 53:1–22] for <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$p=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, to the case when <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$p \ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>. We identify fundamental differences between the different local minima of the regularised subproblems for <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$p=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$p \ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> and their effect on algorithm performance. Then, when <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$p\ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, we introduce a novel pre-rejection technique that rejects poor/unsuccessful subproblem minimizers (that we refer to as ’transient’) prior to any function evaluation, thereby reducing cost and selecting useful (’persistent’) ones. Numerical studies showcase the efficiency improvements generated by our proposed modifications of the AR3 algorithm. We also assess numerically, the effect of different subproblem termination conditions and choice of initial regularization parameter on the overall algorithm performance. Finally, we benchmark our best-performing AR3 variants, as well as those in [Birgin et al, Optim Lett (2020) 14:815–838], against second-order ones (AR2). Encouraging results on standard test problems are obtained, confirming that AR3 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 AR2 and AR3 variants, including Hessian- and tensor-free ones, allowing ease of use and experimentation for interested users.

Efficient Implementation of Third-order Tensor Methods with Adaptive Regularization for Unconstrained Optimization

期刊论文
发表日期：

2026年3月24日

查看全文

Coralia Cartis,
Raphael Hauser,
Yang Liu,
Karl Welzel,
Wenqi Zhu

摘要

High-order tensor methods that employ local Taylor models of degree p within adaptive regularization frameworks (ARp) have recently received significant attention, due to their improved/optimal global and local rates of convergence, for both convex and nonconvex optimization problems. The numerical performance of tensor methods for general unconstrained optimization problems remains insufficiently explored/understood, which we address in this paper, by showcasing the numerical performance of standard second- and third-order variants ( $p=2,3$ $p = 2, 3$ ) and proposing novel techniques for key algorithmic aspects when $p\ge 3$ $p \geq 3$ , to improve the numerical efficiency of tensor variants. In particular, to improve the adaptive choice of the regularization parameter, we extend the interpolation-based updating strategy introduced in [Gould, Porcelli and Toint, Comput Optim Appl (2012) 53:1–22] for $p=2$ $p = 2$ , to the case when $p \ge 3$ $p \geq 3$ . We identify fundamental differences between the different local minima of the regularised subproblems for $p=2$ $p = 2$ and $p \ge 3$ $p \geq 3$ and their effect on algorithm performance. Then, when $p\ge 3$ $p \geq 3$ , we introduce a novel pre-rejection technique that rejects poor/unsuccessful subproblem minimizers (that we refer to as ’transient’) prior to any function evaluation, thereby reducing cost and selecting useful (’persistent’) ones. Numerical studies showcase the efficiency improvements generated by our proposed modifications of the AR3 algorithm. We also assess numerically, the effect of different subproblem termination conditions and choice of initial regularization parameter on the overall algorithm performance. Finally, we benchmark our best-performing AR3 variants, as well as those in [Birgin et al, Optim Lett (2020) 14:815–838], against second-order ones (AR2). Encouraging results on standard test problems are obtained, confirming that AR3 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 AR2 and AR3 variants, including Hessian- and tensor-free ones, allowing ease of use and experimentation for interested users.