On the O(1/N) Convergence Rate of the Douglas–Rachford Alternating Direction Method

Bingsheng He; Xiaoming Yuan

doi:10.1137/110836936

On the O(1/N) Convergence Rate of the Douglas–Rachford Alternating Direction Method

Bingsheng He^*, Xiaoming Yuan

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Review article › peer-review

634 Citations (Scopus)

146 Downloads (Pure)

Abstract

Alternating direction methods (ADMs) have been well studied in the literature, and they have found many efficient applications in various fields. In this note, we focus on the Douglas-Rachford ADM scheme proposed by Glowinski and Marrocco, and we aim at providing a simple approach to estimating its convergence rate in terms of the iteration number. The linearized version of this ADM scheme, which is known as the split inexact Uzawa method in the image processing literature, is also discussed.

Original language	English
Pages (from-to)	700-709
Number of pages	10
Journal	SIAM Journal on Numerical Analysis
Volume	50
Issue number	2
DOIs	https://doi.org/10.1137/110836936
Publication status	Published - 10 Apr 2012

Scopus Subject Areas

Numerical Analysis
Computational Mathematics
Applied Mathematics

User-Defined Keywords

Alternating direction method
Convergence rate
Convex programming
Split inexact Uzawa method
Variational inequalities

Access to Document

10.1137/110836936

Full TextFinal published version, 169 KB

Cite this

@article{0185bea2fe7a49ab90c9d21eff07af57,

title = "On the O(1/N) Convergence Rate of the Douglas–Rachford Alternating Direction Method",

abstract = "Alternating direction methods (ADMs) have been well studied in the literature, and they have found many efficient applications in various fields. In this note, we focus on the Douglas-Rachford ADM scheme proposed by Glowinski and Marrocco, and we aim at providing a simple approach to estimating its convergence rate in terms of the iteration number. The linearized version of this ADM scheme, which is known as the split inexact Uzawa method in the image processing literature, is also discussed.",

keywords = "Alternating direction method, Convergence rate, Convex programming, Split inexact Uzawa method, Variational inequalities",

author = "Bingsheng He and Xiaoming Yuan",

note = "Funding information: Departement of Mathematics, Nanjing University, Nanjing 210093, China (hebma@nju.edu.cn). This author{\textquoteright}s work was supported by NSFC grants 10971095 and 91130007, the Cultivation Fund of KSTIP-MOEC 708044, and the MOEC fund 20110091110004. t Department of Mathematics, Hong Kong Baptist University, Hong Kong, China (xmyuan@hkbu. edu.hk). This author{\textquoteright}s work was supported by the Hong Kong General Research Fund 203311 and by HKBU grant FRG2/10-11/069. Publisher copyright: Copyright {\textcopyright} 2012 Society for Industrial and Applied Mathematics",

year = "2012",

month = apr,

day = "10",

doi = "10.1137/110836936",

language = "English",

volume = "50",

pages = "700--709",

journal = "SIAM Journal on Numerical Analysis",

issn = "0036-1429",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

number = "2",

}

TY - JOUR

T1 - On the O(1/N) Convergence Rate of the Douglas–Rachford Alternating Direction Method

AU - He, Bingsheng

AU - Yuan, Xiaoming

N1 - Funding information: Departement of Mathematics, Nanjing University, Nanjing 210093, China (hebma@nju.edu.cn). This author’s work was supported by NSFC grants 10971095 and 91130007, the Cultivation Fund of KSTIP-MOEC 708044, and the MOEC fund 20110091110004. t Department of Mathematics, Hong Kong Baptist University, Hong Kong, China (xmyuan@hkbu. edu.hk). This author’s work was supported by the Hong Kong General Research Fund 203311 and by HKBU grant FRG2/10-11/069. Publisher copyright: Copyright © 2012 Society for Industrial and Applied Mathematics

PY - 2012/4/10

Y1 - 2012/4/10

N2 - Alternating direction methods (ADMs) have been well studied in the literature, and they have found many efficient applications in various fields. In this note, we focus on the Douglas-Rachford ADM scheme proposed by Glowinski and Marrocco, and we aim at providing a simple approach to estimating its convergence rate in terms of the iteration number. The linearized version of this ADM scheme, which is known as the split inexact Uzawa method in the image processing literature, is also discussed.

AB - Alternating direction methods (ADMs) have been well studied in the literature, and they have found many efficient applications in various fields. In this note, we focus on the Douglas-Rachford ADM scheme proposed by Glowinski and Marrocco, and we aim at providing a simple approach to estimating its convergence rate in terms of the iteration number. The linearized version of this ADM scheme, which is known as the split inexact Uzawa method in the image processing literature, is also discussed.

KW - Alternating direction method

KW - Convergence rate

KW - Convex programming

KW - Split inexact Uzawa method

KW - Variational inequalities

UR - http://www.scopus.com/inward/record.url?scp=84861398963&partnerID=8YFLogxK

U2 - 10.1137/110836936

DO - 10.1137/110836936

M3 - Review article

AN - SCOPUS:84861398963

SN - 0036-1429

VL - 50

SP - 700

EP - 709

JO - SIAM Journal on Numerical Analysis

JF - SIAM Journal on Numerical Analysis

IS - 2

ER -

On the O(1/N) Convergence Rate of the Douglas–Rachford Alternating Direction Method

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this