Worst-case complexity of smoothing quadratic regularization methods for non-lipschitzian optimization

Wei Bian, Xiaojun Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

30 Citations (Scopus)

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 languageEnglish
Pages (from-to)1718-1741
Number of pages24
JournalSIAM Journal on Optimization
Volume23
Issue number3
DOIs
Publication statusPublished - 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

Cite this