Global convergence of splitting methods for nonconvex composite op timization

Guoyin Li, Ting Kei Pong

Research output: Journal article publicationJournal articleAcademic researchpeer-review

161 Citations (Scopus)

Abstract

We consider the problem of minimizing the s um of a smooth function h with a bounded Hessian and a nonsmooth function. We assume that the latter function is a composition of a proper closed function P and a surjective linear map M, with the proximal mappings of tP, τ > 0, simple to compute. This problem is nonconvex in general and encompasses many important applications in engineering and machine learning. In this paper, we examined two types of splitting methods for solving this nonconvex optimization problem: the alternating direction method of multipliers and the proximal gradient algorithm. For the direct adaptation of the alternating direction method of multipliers, we show that if the penalty parameter is chosen sufficiently large and the sequence generated has a cluster point, then it gives a stationary point of the nonconvex problem. We also establish convergence of the whole sequence under an additional assumption that the functions h and P are semialgebraic. Furthermore, we give simple sufficient conditions to guarantee boundedness of the sequence generated. These conditions can be satisfied for a wide range of applications including the least squares problem with the ℓ1/2regularization. Finally, when M is the identity so that the proximal gradient algorithm can be efficiently applied, we show that any cluster point is stationary under a slightly more flexible constant step-size rule than what is known in the literature for a nonconvex h.
Original languageEnglish
Pages (from-to)2434-2460
Number of pages27
JournalSIAM Journal on Optimization
Volume25
Issue number4
DOIs
Publication statusPublished - 1 Dec 2015

Keywords

  • Alternating direction method of multipliers
  • Global convergence
  • Kurdyka-Lojasiewicz property
  • Nonconvex composite optimization
  • Proximal gradient algorithm

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this