research-article

Preconditioned Douglas--Rachford Splitting Methods for Convex-concave Saddle-point Problems

Authors:

Kristian Bredies,

Hongpeng SunAuthors Info & Claims

SIAM Journal on Numerical Analysis, Volume 53, Issue 1

Pages 421 - 444

https://doi.org/10.1137/140965028

Published: 01 January 2015 Publication History

Abstract

We propose a preconditioned version of the Douglas--Rachford splitting method for solving convex-concave saddle-point problems associated with Fenchel--Rockafellar duality. Our approach makes it possible to use approximate solvers for the linear subproblem arising in this context. We prove weak convergence in Hilbert space under minimal assumptions. In particular, various efficient preconditioners are introduced in this framework for which only a few inner iterations are needed instead of computing an exact solution or controlling the error. The method is applied to a discrete total-variation denoising problem. Numerical experiments show that the proposed algorithms with appropriate preconditioners are very competitive with existing fast algorithms including the first-order primal-dual algorithm for saddle-point problems of Chambolle and Pock.

References

[1]

G. Alefeld, On the convergence of the symmetric SOR method for matrices with red-black ordering, Numer. Math., 39 (1982), pp. 113--117.

[2]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183--202.

[3]

J. Bramble and J. Pasciak, New estimates for multilevel algorithms including the $V$-cycle, Math. Comp., 60 (1993), pp. 447--471.

[4]

J. H. Bramble, J. E. Pasciak, and A. T. Vassilev, Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM J. Numer. Anal., 34 (1997), pp. 1072--1092.

[5]

K. Bredies, Recovering piecewise smooth multichannel images by minimization of convex functionals with total generalized variation penalty, in Efficient Algorithms for Global Optimization Methods in Computer Vision, A. Bruhn, T. Pock, and X.-C. Tai, eds., Lecture Notes in Comput. Sci., Springer, Berlin, 2014, pp. 44--77.

[6]

K. Bredies, K. Kunisch, and T. Pock, Total generalized variation, SIAM J. Imaging Sci., 3 (2010), pp. 492--526.

[7]

L. M. Bricen͂o-Arias and P. L. Combettes, A monotone$+$skew splitting model for composite monotone inclusions in duality, SIAM J. Optim., 21 (2011), pp. 1230--1250.

[8]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), pp. 120--145.

[9]

P. L. Combettes, Solving monotone inclusions via compositions of nonexpansive averaged operators, Optimization, 53 (2004), pp. 475--504.

[10]

P. L. Combettes and J. Pesquet, A Douglas--Rachford splitting approach to nonsmooth convex variational signal recovery, IEEE J. Sel. Topics Signal Process., 1 (2007), pp. 564--574.

[11]

J. Douglas and H. H. Rachford, On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., 82 (1956), pp. 421--439.

[12]

J. Eckstein and D. P. Bertsekas, On the Douglas--Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), pp. 293--318.

[13]

I. Ekeland and R. Témam, Convex Analysis and Variational Problems, Classics Appl. Math. 28, SIAM, Philadelphia, 1999.

[14]

E. Esser, Applications of Lagrangian-Based Alternating Direction Methods and Connections to Split Bregman, CAM Report 09-2009, UCLA, Los Angeles, 2009.

[15]

D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, M. Fortin and R. Glowinski, eds., Stud. Math. Appl. 15, Elsevier, New York, 1983, pp. 299--331.

[16]

T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems, SIAM J. Imaging Sci., 2 (2009), pp. 323--343.

[17]

Q. Hu and J. Zou, Nonlinear inexact Uzawa algorithms for linear and nonlinear saddle-point problems, SIAM Journal on Optimization, 16 (2006), pp. 798--825.

[18]

K. Ito and K. Kunisch, Lagrange Multiplier Approach to Variational Problems and Applications, Ad. Des. Control 15, SIAM, Philadelphia, 2008.

[19]

C. S. Kubrusly, Spectral Theory of Operators on Hilbert Spaces, Springer, New York, 2012.

[20]

P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), pp. 964--979.

[21]

G. J. Minty, Monotone (nonlinear) operators in Hilbert space, Duke Math. J., 29 (1962), pp. 341--346.

[22]

Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc., 73 (1967), pp. 591--597.

[23]

T. Pock and A. Chambolle, Diagonal preconditioning for first order primal-dual algorithms in convex optimization, in Proceedings of the 2011 IEEE International Conference on Computer Vision (ICCV), 2011, pp. 1762--1769.

[24]

M. Reed and B. Simon, Methods of Modern Mathematical Physics: Functional Analysis, Methods Modern Math. Phys. 1, Academic Press, New York, 1980.

[25]

L. I. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), pp. 259--268.

[26]

Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003.

[27]

J. W. Thomas, Numerical Partial Differential Equations: Conservation Laws and Elliptic Equations, Texts Appl. Math. 33, Springer, New York, 1999.

[28]

U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, New York, 2001.

[29]

Wikipedia, Fronalpstock, http://en.wikipedia.org/wiki/File:Fronalpstock_big.jpg, accessed on February 7, 2014.

[30]

X. Q. Zhang, M. Burger, and S. Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46 (2011), pp. 20--46.

[31]

M. Q. Zhu and T. Chan, An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration, CAM Report 08-2008, UCLA, Los Angeles, 2008.

Cited By

Ding WNg MZhang W(2024)A generalized alternating direction implicit method for consensus optimization: application to distributed sparse logistic regressionJournal of Global Optimization10.1007/s10898-024-01418-990:3(727-753)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1007/s10898-024-01418-9
Zhang ZChang HDuan Y(2023)Fast Non-overlapping Domain Decomposition Methods for Continuous Multi-phase Labeling ProblemJournal of Scientific Computing10.1007/s10915-023-02382-497:3Online publication date: 2-Nov-2023
https://dl.acm.org/doi/10.1007/s10915-023-02382-4

Recommendations

A distributed Douglas-Rachford splitting method for multi-block convex minimization problems

A customized Douglas-Rachford splitting method (DRSM) was recently proposed to solve two-block separable convex optimization problems with linear constraints and simple abstract constraints. The algorithm has advantage over the well-known alternating ...
Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results

Although originally designed and analyzed for convex problems, the alternating direction method of multipliers (ADMM) and its close relatives, Douglas--Rachford splitting (DRS) and Peaceman--Rachford splitting (PRS), have been observed to perform ...
Convergence Rate Analysis of the Forward-Douglas-Rachford Splitting Scheme

Operator splitting schemes are a class of powerful algorithms that solve complicated monotone inclusion and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which all simple pieces of the decomposition ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Numerical Analysis

SIAM Journal on Numerical Analysis Volume 53, Issue 1

2015

633 pages

ISSN:0036-1429

DOI:10.1137/sjnaam.53.1

Issue’s Table of Contents

© 2015, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2015

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ding WNg MZhang W(2024)A generalized alternating direction implicit method for consensus optimization: application to distributed sparse logistic regressionJournal of Global Optimization10.1007/s10898-024-01418-990:3(727-753)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1007/s10898-024-01418-9
Zhang ZChang HDuan Y(2023)Fast Non-overlapping Domain Decomposition Methods for Continuous Multi-phase Labeling ProblemJournal of Scientific Computing10.1007/s10915-023-02382-497:3Online publication date: 2-Nov-2023
https://dl.acm.org/doi/10.1007/s10915-023-02382-4

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents