Optimization Online


Convergence analysis of primal-dual algorithms for total variation image restoration

Bingsheng He(hebma***at***nju.edu.cn)
Xiaoming Yuan(xmyuan***at***hkbu.edu.hk)

Abstract: Recently, some attractive primal-dual algorithms have been proposed for solving a saddle-point problem, with particular applications in the area of total variation (TV) image restoration. This paper focuses on the convergence analysis of existing primal-dual algorithms and shows that the involved parameters of those primal-dual algorithms (including the step sizes) can be significantly enlarged if some simple correction steps are supplemented. As a result, we present some primal-dual-based contraction methods for solving the saddle-point problem. These contraction methods are in the prediction-correction fashion in the sense that the predictor is generated by a primal-dual method and it is corrected by some simple correction step at each iteration. In addition, based on the context of contraction type methods, we provide a novel theoretical framework for analyzing the convergence of primal-dual algorithms which simplifies existing convergence analysis substantially.

Keywords: Saddle-point problem, total variation, primal-dual, contraction method, variational inequality, proximal point algorithm

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 11/03/2010
Entry Accepted: 11/03/2010
Entry Last Modified: 11/03/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society