Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction

Research output: Journal article publicationJournal articleAcademic researchpeer-review

55 Citations (Scopus)

Abstract

In this paper, we study a general optimization model, which covers a large class of existing models for many applications in imaging sciences. To solve the resulting possibly nonconvex, nonsmooth, and non-Lipschitz optimization problem, we adapt the alternating direction method of multipliers (ADMM) with a general dual step-size to solve a reformulation that contains three blocks of variables and analyze its convergence. We show that for any dual step-size less than the golden ratio, there exists a computable threshold such that if the penalty parameter is chosen above such a threshold and the sequence thus generated by our ADMM is bounded, then the cluster point of the sequence gives a stationary point of the nonconvex optimization problem. We achieve this via a potential function specifically constructed for our ADMM. Moreover, we establish the global convergence of the whole sequence if, in addition, this special potential function is a Kurdyka–Łojasiewicz function. Furthermore, we present a simple strategy for initializing the algorithm to guarantee boundedness of the sequence. Finally, we perform numerical experiments comparing our ADMM with the proximal alternating linearized minimization proposed in [Bolte, Sabach, and Teboulle, Math. Program., 146 (2014), pp. 459–494] on the background/foreground extraction problem with real data. The numerical results show that our ADMM with a nontrivial dual step-size is efficient.
Original languageEnglish
Pages (from-to)74-110
Number of pages37
JournalSIAM Journal on Imaging Sciences
Volume10
Issue number1
DOIs
Publication statusPublished - 26 Jan 2017

Keywords

  • Alternating direction method of multipliers
  • Background/foreground extraction
  • Dual step-size
  • Nonsmooth and nonconvex optimization

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics

Cite this