Métodos de regularização cúbica com aproximações preguiçosas da hessiana

Abstract

In this work, we present variants of the Cubic Regularization Newton's (CRN) method incorporating lazy Hessian approximations for solving general non-convex optimization problems (0-3). We propose two approaches: the first (Algorithm 1) employs the exact gradient while reusing the same Hessian approximation for a block of \( m \) iterations, whereas the second (Algorithm 2) extends this idea by additionally allowing the use of inexact gradients. Implementations of methods, where information about derivatives are computed through finite difference strategies, are presented. One interesting feature of our algorithms is that the regularization parameter and the accuracy of the derivative approximations (when they are updated) are jointly adjusted using a nonmonotone line search criterion. We establish first-order complexity results for both methods. Specifically, for a given precision $\epsilon$, it is shown that the Algorithm~1 and Algorithm~2 require at most {$\mathcal{O}\left( m^{1/2} \epsilon^{-3/2}\right)$} outer iterations to generate an $\epsilon-$approximate critical point for aforementioned problem. When the derivatives are computed by finite difference approaches, we show that Algorithm~1 (resp. Algorithm~2) needs at most {$\mathcal{O}\left((n+m)m^{-1/2}\epsilon^{-3/2}+(n+m)\right)$} (resp. {$\mathcal{O}\left((n^2+mn)m^{-1/2}\epsilon^{-3/2}+(n^2+mn)\right)$}) gradient and function (resp. function) evaluations to generate an $\epsilon$-approximate critical point, where $n$ is the dimension of the domain of the objective function.