On the complexity of a quadratic regularization algorithm for minimizing nonsmooth and nonconvex functions

In this paper, we consider the problem of minimizing the function f (x) =g1 (x) +g2 (x) −h (x) over Rn, where g1 is a proper and lower semicontinuous function, g2 is continuously differentiable with a Hölder continuous gradient and h is a convex function that may be nondifferentiable. This problem has important practical applications but is challenging to solve due to the presence of nonconvexities and nonsmoothness. To address this issue, we propose an algorithm based on a proximal gradient method that uses a quadratic approximation of the function g2 and a nonconvex regularization term. We show that the number of iterations required to reach our stopping criterion is O (maxϵ−β+1β, η2βϵ−2 (β+1) β). Our approach offers a promising strategy for solving this challenging optimization problem and has potential applications in various fields. Numerical examples are provided to illustrate the theoretical results.