Relative-error approximate versions of Douglas–Rachford splitting and special cases of the ADMM

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

We derive a new approximate version of the alternating direction method of multipliers (ADMM) which uses a relative error criterion. The new version is somewhat restrictive and allows only one of the two subproblems to be minimized approximately, but nevertheless covers commonly encountered special cases. The derivation exploits the long-established relationship between the ADMM and both the proximal point algorithm (PPA) and Douglas–Rachford (DR) splitting for maximal monotone operators, along with a relative-error of the PPA due to Solodov and Svaiter. In the course of analysis, we also derive a version of DR splitting in which one operator may be evaluated approximately using a relative error criterion. We computationally evaluate our method on several classes of test problems and find that it significantly outperforms several alternatives on one problem class.

Original languageEnglish (US)
Pages (from-to)417-444
Number of pages28
JournalMathematical Programming
Volume170
Issue number2
DOIs
StatePublished - Aug 1 2018

Fingerprint

Method of multipliers
Alternating Direction Method
Relative Error
Proximal Point Algorithm
Maximal Monotone Operator
Test Problems
Cover
Evaluate
Alternatives
Operator
Class

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • ADMM
  • Convex programming
  • Decomposition methods
  • Monotone operators

Cite this

@article{f1890b58b85247fcb67bb2bdd2eb8064,
title = "Relative-error approximate versions of Douglas–Rachford splitting and special cases of the ADMM",
abstract = "We derive a new approximate version of the alternating direction method of multipliers (ADMM) which uses a relative error criterion. The new version is somewhat restrictive and allows only one of the two subproblems to be minimized approximately, but nevertheless covers commonly encountered special cases. The derivation exploits the long-established relationship between the ADMM and both the proximal point algorithm (PPA) and Douglas–Rachford (DR) splitting for maximal monotone operators, along with a relative-error of the PPA due to Solodov and Svaiter. In the course of analysis, we also derive a version of DR splitting in which one operator may be evaluated approximately using a relative error criterion. We computationally evaluate our method on several classes of test problems and find that it significantly outperforms several alternatives on one problem class.",
keywords = "ADMM, Convex programming, Decomposition methods, Monotone operators",
author = "Jonathan Eckstein and Wang Yao",
year = "2018",
month = "8",
day = "1",
doi = "10.1007/s10107-017-1160-5",
language = "English (US)",
volume = "170",
pages = "417--444",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "2",

}

Relative-error approximate versions of Douglas–Rachford splitting and special cases of the ADMM. / Eckstein, Jonathan; Yao, Wang.

In: Mathematical Programming, Vol. 170, No. 2, 01.08.2018, p. 417-444.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Relative-error approximate versions of Douglas–Rachford splitting and special cases of the ADMM

AU - Eckstein, Jonathan

AU - Yao, Wang

PY - 2018/8/1

Y1 - 2018/8/1

N2 - We derive a new approximate version of the alternating direction method of multipliers (ADMM) which uses a relative error criterion. The new version is somewhat restrictive and allows only one of the two subproblems to be minimized approximately, but nevertheless covers commonly encountered special cases. The derivation exploits the long-established relationship between the ADMM and both the proximal point algorithm (PPA) and Douglas–Rachford (DR) splitting for maximal monotone operators, along with a relative-error of the PPA due to Solodov and Svaiter. In the course of analysis, we also derive a version of DR splitting in which one operator may be evaluated approximately using a relative error criterion. We computationally evaluate our method on several classes of test problems and find that it significantly outperforms several alternatives on one problem class.

AB - We derive a new approximate version of the alternating direction method of multipliers (ADMM) which uses a relative error criterion. The new version is somewhat restrictive and allows only one of the two subproblems to be minimized approximately, but nevertheless covers commonly encountered special cases. The derivation exploits the long-established relationship between the ADMM and both the proximal point algorithm (PPA) and Douglas–Rachford (DR) splitting for maximal monotone operators, along with a relative-error of the PPA due to Solodov and Svaiter. In the course of analysis, we also derive a version of DR splitting in which one operator may be evaluated approximately using a relative error criterion. We computationally evaluate our method on several classes of test problems and find that it significantly outperforms several alternatives on one problem class.

KW - ADMM

KW - Convex programming

KW - Decomposition methods

KW - Monotone operators

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

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

U2 - 10.1007/s10107-017-1160-5

DO - 10.1007/s10107-017-1160-5

M3 - Article

AN - SCOPUS:85019576971

VL - 170

SP - 417

EP - 444

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -