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

Abstract

In this paper, we consider the problem of minimizing the function $f(x)=g_1(x)+g_2(x)-h(x)$ over ${\mathbb{R}}^n$, where $g_1$ is a proper and lower semicontinuous function, $g_2$ 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 $g_2$ and a nonconvex regularization term. We show that the number of iterations required to reach our stopping criterion is $\mathcal{O}(max\{{ϵ}^{-\frac{\beta +1}{\beta }},{\eta }^{\frac{2}{\beta }}{ϵ}^{-\frac{2(\beta +1)}{\beta }}\})$. 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.

Keywords:

• Nonconvex optimization
• nonsmooth optimization
• quadratic regularization
• worst-case evaluation complexity

2020 Mathematics Subject Classifications:

• 65Y20
• 65K05
• 65K15
• 49M15
• 49M37

Acknowledgments

The authors would like to thank the anonymous referees and the associated editor for their constructive comments which have helped to substantially improve the presentation of the paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The third author was supported in part by CNPq grant 309552/2022-2. The fourth author was supported in part by CNPq grants 401864/2022-7 and 306593/2022-0.

Notes on contributors

V. S. Amaral

V. S. Amaral received his PhD in Applied Mathematics at the University of Campinas (UNICAMP) in 2024. He obtained the MSc and degrees in Mathematics from the Federal University of Piauí (UFPI) in 2013 and 2011, respectively. His research interests broadly focus on optimization, and the development and analysis of algorithms for nonlinear optimization.

J. O. Lopes

J. O. Lopes received his DSc in Systems Engineering and Computer Science at Federal University of Rio de Janeiro (2002). He received a MSc degree from the Federal University of Ceará (1997) and a degree in Mathematics at the Federal University of Piaui (1994). His research interests broadly focus on the designing, developing and analyzing of algorithms for nonlinear optimization, equilibrium problems and multiobjective optimization.

P. S. M. Santos

P. S. M. Santos received his Dsc in Systems Engineering and Computer Science at Federal University of Rio de Janeiro (2007). He received the MSc in Mathematics at Federal University of Ceará and a degree in Mathematics at the Federal University of Piaui. His research interests broadly focus on designing, developing, and analyzing algorithms for nonlinear optimization, multiobjective programming and general equilibrium problems.

G. N. Silva

G. N. Silva received his Ph.D. from the Federal University of Goiás at Goiânia in 2017. He received the MSc (2013) and BS (2011) in Mathematics at the Federal University of Piauí. He spent the last year working with Renato D. C. Monteiro as a Postdoctoral Researcher at Georgia Tech. In 2022 he joined the Department of Mathematics in the Federal University of Piaui. His primary research area is optimization with specific interest in analysis of efficient algorithms for large-scale convex and nonconvex problems, with particular interest in Newton-type methods.