<p>We develop a worst-case evaluation complexity bound for trust-region methods in the presence of unbounded Hessian approximations. We use the algorithm of Aravkin et al. (SIAM J Optim 32(2):900–929, 2022) as a model, which is designed for nonsmooth regularized problems, but applies to unconstrained smooth problems as a special case. Our analysis assumes that the growth of the Hessian approximation is controlled by the number of successful iterations. We show that the best known complexity bound of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\epsilon ^{-2}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> </math></EquationSource> </InlineEquation> deteriorates to <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\epsilon ^{-2/(1-p)}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>2</mn> <mo stretchy="false">/</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </msup> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$0 \leqslant p < 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo>⩽</mo> <mi>p</mi> <mo><</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> is a parameter that controls the growth of the Hessian approximation. The faster the Hessian approximation grows, the more the bound deteriorates. We construct an objective that satisfies all of our assumptions and for which our complexity bound is attained, which establishes that our bound is sharp. To the best of our knowledge, our complexity result is the first to consider potentially unbounded Hessians and is a first step towards addressing a conjecture of Powell (IMA J Numer Anal 30(1):289–301, 2010) that trust-region methods may require an exponential number of iterations in such a case. Numerical experiments conducted in double precision arithmetic are consistent with the analysis.</p>

Complexity of trust-region methods with potentially unbounded Hessian approximations for smooth and nonsmooth optimization

期刊论文
发表日期：

2026年1月26日

查看全文

Geoffroy Leconte,
Dominique Orban

摘要

We develop a worst-case evaluation complexity bound for trust-region methods in the presence of unbounded Hessian approximations. We use the algorithm of Aravkin et al. (SIAM J Optim 32(2):900–929, 2022) as a model, which is designed for nonsmooth regularized problems, but applies to unconstrained smooth problems as a special case. Our analysis assumes that the growth of the Hessian approximation is controlled by the number of successful iterations. We show that the best known complexity bound of $\epsilon ^{-2}$ $ϵ^{- 2}$ deteriorates to $\epsilon ^{-2/(1-p)}$ $ϵ^{- 2 / (1 - p)}$ , where $0 \leqslant p < 1$ $0 ⩽ p < 1$ is a parameter that controls the growth of the Hessian approximation. The faster the Hessian approximation grows, the more the bound deteriorates. We construct an objective that satisfies all of our assumptions and for which our complexity bound is attained, which establishes that our bound is sharp. To the best of our knowledge, our complexity result is the first to consider potentially unbounded Hessians and is a first step towards addressing a conjecture of Powell (IMA J Numer Anal 30(1):289–301, 2010) that trust-region methods may require an exponential number of iterations in such a case. Numerical experiments conducted in double precision arithmetic are consistent with the analysis.