Convergence Analysis of Primal-Dual Algorithms for a Saddle-Point Problem: From Contraction Perspective

Bingsheng He, Xiaoming Yuan*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

261 Citations (Scopus)
137 Downloads (Pure)


Recently, some primal-dual algorithms have been proposed for solving a saddle-point problem, with particular applications in the area of total variation image restoration. This paper focuses on the convergence analysis of these primal-dual algorithms and shows that their involved parameters (including step sizes) can be significantly enlarged if some simple correction steps are supplemented. Some new primal-dual–based methods are thus proposed for solving the saddle-point problem. We show that these new methods are of the contraction type: the iterative sequences generated by these new methods are contractive with respect to the solution set of the saddle-point problem. The global convergence of these new methods thus can be obtained within the analytic framework of contraction-type methods. The novel study on these primal-dual algorithms from the perspective of contraction methods substantially simplifies existing convergence analysis. Finally, we show the efficiency of the new methods numerically.

Original languageEnglish
Pages (from-to)119-149
Number of pages31
JournalSIAM Journal on Imaging Sciences
Issue number1
Publication statusPublished - 24 Jan 2012

Scopus Subject Areas

  • Mathematics(all)
  • Applied Mathematics

User-Defined Keywords

  • Contraction method
  • Image restoration
  • Primal-dual method
  • Proximal point algorithm
  • saddle-point problem
  • Total variation


Dive into the research topics of 'Convergence Analysis of Primal-Dual Algorithms for a Saddle-Point Problem: From Contraction Perspective'. Together they form a unique fingerprint.

Cite this