On the Convergence of Primal-Dual Hybrid Gradient Algorithm

Bingsheng He, Yanfei You, Xiaoming Yuan

Research output: Contribution to journalJournal articlepeer-review

69 Citations (Scopus)
209 Downloads (Pure)

Abstract

The primal-dual hybrid gradient algorithm (PDHG) has been widely used, especially for some basic image processing models. In the literature, PDHG’s convergence was established only under some restrictive conditions on its step sizes. In this paper, we revisit PDHG’s convergence in the context of a saddle-point problem and try to better understand how to choose its step sizes. More specifically, we show by an extremely simple example that PDHG is not necessarily convergent even when the step sizes are fixed as tiny constants. We then show that PDHG with constant step sizes is indeed convergent if one of the functions of the saddle-point problem is strongly convex, a condition that does hold for some variational models in imaging. With this additional condition, we also establish a worst-case convergence rate measured by the iteration complexity for PDHG with constant step sizes.

Original languageEnglish
Pages (from-to)2526-2537
Number of pages12
JournalSIAM Journal on Imaging Sciences
Volume7
Issue number4
DOIs
Publication statusPublished - 3 Dec 2014

Scopus Subject Areas

  • Mathematics(all)
  • Applied Mathematics

User-Defined Keywords

  • Convergence rate
  • Convex optimization
  • Image restoration
  • Primal-dual hybrid gradient algorithm
  • Saddle-point problem
  • Total variation

Fingerprint

Dive into the research topics of 'On the Convergence of Primal-Dual Hybrid Gradient Algorithm'. Together they form a unique fingerprint.

Cite this