G-2023-65
Complexity of trust-region methods with unbounded Hessian approximations for smooth and nonsmooth optimization
and BibTeX reference
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. (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}\)
deteriorates to \(\epsilon^{-2/(1-p)}\)
, where \(0 \leq 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.
Numerical experiments conducted in double precision arithmetic are consistent with the theoretical analysis.
Published December 2023 , 18 pages
This cahier was revised in March 2024
Research Axis
Research application
Document
G2365R.pdf (700 KB)