Abstract
In this paper, we propose a smoothing quadratic regularization (SQR) algorithm for solving a class of nonsmooth nonconvex, perhaps even non-Lipschitzian minimization problems, which has wide applications in statistics and sparse reconstruction. The proposed SQR algorithm is a first order method. At each iteration, the SQR algorithm solves a strongly convex quadratic minimization problem with a diagonal Hessian matrix, which has a simple closed-form solution that is inexpensive to calculate. We show that the worst-case complexity of reaching an ε scaled stationary point is O(ε-2). Moreover, if the objective function is locally Lipschitz continuous, the SQR algorithm with a slightly modified updating scheme for the smoothing parameter and iterate can obtain an ε Clarke stationary point in at most Oε-3) iterations.
Original language | English |
---|---|
Pages (from-to) | 1718-1741 |
Number of pages | 24 |
Journal | SIAM Journal on Optimization |
Volume | 23 |
Issue number | 3 |
DOIs | |
Publication status | Published - 29 Oct 2013 |
Keywords
- Convergence
- Nonsmooth nonconvex optimization
- Quadratic regularization
- Smoothing approximation
- Stationary point
- Worst-case complexity
ASJC Scopus subject areas
- Theoretical Computer Science
- Software