article

A Proximal Point Analysis of the Preconditioned Alternating Direction Method of Multipliers

Authors:

Kristian Bredies,

Hongpeng SunAuthors Info & Claims

Journal of Optimization Theory and Applications, Volume 173, Issue 3

Pages 878 - 907

https://doi.org/10.1007/s10957-017-1112-5

Published: 01 June 2017 Publication History

Abstract

We study preconditioned algorithms of alternating direction method of multipliers type for nonsmooth optimization problems. The alternating direction method of multipliers is a popular first-order method for general constrained optimization problems. However, one of its drawbacks is the need to solve implicit subproblems. In various applications, these subproblems are either easily solvable or linear, but nevertheless challenging. We derive a preconditioned version that allows for flexible and efficient preconditioning for these linear subproblems. The original and preconditioned version is written as a new kind of proximal point method for the primal problem, and the weak (strong) convergence in infinite (finite) dimensional Hilbert spaces is proved. Various efficient preconditioners with any number of inner iterations may be used in this preconditioned framework. Furthermore, connections between the preconditioned version and the recently introduced preconditioned Douglas---Rachford method for general nonsmooth problems involving quadratic---linear terms are established. The methods are applied to total variation denoising problems, and their benefits are shown in numerical experiments.

References

[1]

Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1---122 (2011)

Digital Library

[2]

Eckstein, J., Yao, W.: Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives. Pac. J. Optim. 11(4), 619---644 (2015)

[3]

Esser, E.: Application of Lagrangian-based alternating direction methods and connections to split Bregman. CAM Report 09-31, UCLA, Center for Applied Math. (2009)

[4]

Ramani, S., Fessler, J.A.: A splitting-based iterative algorithm for accelerated statistical X-ray CT reconstruction. IEEE Trans. Med. Imag. 31(3), 677---688 (2012)

[5]

Wu, C., Tai, X.C.: Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models. SIAM J. Imaging Sci. 3(3), 300---339 (2010)

Digital Library

[6]

Fortin, M., Glowinski, R.: On decomposition-coordination methods using an augmented Lagrangian. In: Fortin, M., Glowinski, R. (eds.) Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, pp. 97---146. North-Holland, Amsterdam (1983)

[7]

Glowinski, R., Marrocco, A.: Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires. ESAIM Math. Model. Num. 9(2), 41---76 (1975)

[8]

Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Fortin, M., Glowinski, R. (eds.) Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, pp. 299---331. North-Holland, Amsterdam (1983)

[9]

Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1), 17---40 (1976)

[10]

Mercier, B.: Approximation par éléments finis et résolution par un algorithme de pénalisation-dualité d'un problème d'élasto-plasticité. C.R. Acad. Sci. Math. 280, 287---290 (1975)

[11]

Glowinski, R.: Variational Methods for the Numerical Solution of Nonlinear Elliptic Problems. SIAM, Philadelphia, PA (2015)

Digital Library

[12]

Glowinski, R.: On alternating direction methods of multipliers: a historical perspective. In: Fitzgibbon, W., Kuznetsov, Y.A., Neittaanmäki, P., Pironneau, O. (eds.) Modeling, Simulation and Optimization for Science and Technology, vol. 34 of the series Computational Methods in Applied Sciences, pp. 59---82. Springer, Berlin (2014)

[13]

Chan, T., Glowinski, R.: Finite Element Approximation and Iterative Solution of a Class of Mildly Non-Linear Elliptic Equations. Computer Science Department, Stanford University, Stanford (1978)

[14]

Glowinski, R., Osher, S., Yin, W. (eds.): Splitting Methods in Communication, Imaging, Science, and Engineering. Springer, Berlin (2016)

Digital Library

[15]

Glowinski, R., Le Tallec, P.: Augmented Lagrangians and Operator-Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia, PA (1989)

[16]

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

Digital Library

[17]

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

Digital Library

[18]

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

Digital Library

[19]

Li, M., Sun, D., Toh, K.C.: A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization. SIAM J. Optim. 26(2), 922---950 (2016)

Digital Library

[20]

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

Digital Library

[21]

Bredies, K., Sun, H.: Preconditioned Douglas---Rachford algorithms for TV- and TGV-regularized variational imaging problems. J. Math. Imaging Vis. 52(3), 317---344 (2015)

Digital Library

[22]

Bredies, K., Sun, H.: Preconditioned Douglas---Rachford splitting methods for convex---concave saddle-point problems. SIAM J. Numer. Anal. 53(1), 421---444 (2015)

[23]

Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889---916 (2016)

Digital Library

[24]

Fang, E.X., He, B., Liu, H., Yuan, X.: Generalized alternating direction method of multipliers: new theoretical insights and applications. Math. Prog. Comp. 7(2), 149---187 (2015)

[25]

Monteiro, R.D.C., Svaiter, B.F.: Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23(1), 475---507 (2013)

Digital Library

[26]

Shefi, R., Teboulle, M.: Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization. SIAM J. Optim. 24(1), 269---297 (2014)

Digital Library

[27]

Attouch, H., Soueycatt, M.: Augmented Lagrangian and proximal alternating direction methods of multipliers in Hilbert spaces. Applications to games, PDE's and control. Pac. J. Optim. 5(1), 17---37 (2008)

[28]

Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)

Digital Library

[29]

Ito, K., Kunisch, K.: Lagrange Multiplier Approach to Variational Problems and Applications. SIAM, Philadelphia (2008)

Digital Library

[30]

Reed, M., Simon, B.: Methods of Modern Mathematical Physics I: Functional Analysis. Academic Press, San Diego (1980)

[31]

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

[32]

Esser, E., Zhang, X., Chan, T.: A general framework for a class of first order primal---dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015---1046 (2010)

Digital Library

[33]

Goldstein, T., Osher, S.: The split Bregman method for $$L^1$$L1 regularized problems. SIAM J. Imaging Sci. 2(2), 323---343 (2009)

Digital Library

[34]

Setzer, S.: Split Bregman algorithm, Douglas---Rachford splitting and frame shrinkage. In: Tai, X.C., MØrken, K., Lysaker, M., Lie, K.A. (eds.) Scale Space and Variational Methods in Computer Vision, pp. 464---476. Springer, Berlin (2009)

Digital Library

[35]

Yan, M., Yin, W.: Self equivalence of the alternating direction method of multipliers. arXiv eprints, 1407:7400 (2014)

[36]

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

Digital Library

[37]

Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259---268 (1992)

Digital Library

[38]

Ekeland, I., Témam, R.: Convex Analysis and Variational Problems. SIAM, Philadelphia (1999)

Digital Library

[39]

Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward---backward splitting. Multiscale Model. Sim. 4(4), 1168---1200 (2005)

[40]

Bredies, K., Sun, H.: Accelerated Douglas---Rachford methods for the solution of convex-concave saddle-point problems. arXiv eprints, 1604:06282 (2016)

[41]

Xu, Y.: Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. arXiv eprints, 1606:09155 (2016)

Cited By

Jin Q(2023)On Convergence Rates of Proximal Alternating Direction Method of MultipliersJournal of Scientific Computing10.1007/s10915-023-02383-397:3Online publication date: 2-Nov-2023
https://dl.acm.org/doi/10.1007/s10915-023-02383-3
Poon CPeyré G(2023)Smooth over-parameterized solvers for non-smooth structured optimizationMathematical Programming: Series A and B10.1007/s10107-022-01923-3201:1-2(897-952)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1007/s10107-022-01923-3
Zhang HPeng Z(2022)Total Generalized Variation for Triangulated Surface DataJournal of Scientific Computing10.1007/s10915-022-02047-893:3Online publication date: 14-Nov-2022
https://dl.acm.org/doi/10.1007/s10915-022-02047-8
Show More Cited By

A Proximal Point Analysis of the Preconditioned Alternating Direction Method of Multipliers

Recommendations

Pointwise and Ergodic Convergence Rates of a Variable Metric Proximal Alternating Direction Method of Multipliers

In this paper, we obtain global pointwise and ergodic convergence rates for a variable metric proximal alternating direction method of multipliers for solving linearly constrained convex optimization problems. We first propose and study nonasymptotic ...
A Partially Inexact Proximal Alternating Direction Method of Multipliers and Its Iteration-Complexity Analysis

This paper proposes a partially inexact proximal alternating direction method of multipliers for computing approximate solutions of a linearly constrained convex optimization problem. This method allows its first subproblem to be solved inexactly using ...
A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming
Abstract
The linearized alternating direction method of multipliers (ADMM), with indefinite proximal regularization, has been proved to be efficient for solving separable convex optimization subject to linear constraints. In this paper, we present a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Optimization Theory and Applications

Journal of Optimization Theory and Applications Volume 173, Issue 3

June 2017

344 pages

ISSN:0022-3239

Issue’s Table of Contents

Copyright © Copyright © 2017 Springer Science+Business Media New York.

Publisher

Plenum Press

United States

Publication History

Published: 01 June 2017

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jin Q(2023)On Convergence Rates of Proximal Alternating Direction Method of MultipliersJournal of Scientific Computing10.1007/s10915-023-02383-397:3Online publication date: 2-Nov-2023
https://dl.acm.org/doi/10.1007/s10915-023-02383-3
Poon CPeyré G(2023)Smooth over-parameterized solvers for non-smooth structured optimizationMathematical Programming: Series A and B10.1007/s10107-022-01923-3201:1-2(897-952)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1007/s10107-022-01923-3
Zhang HPeng Z(2022)Total Generalized Variation for Triangulated Surface DataJournal of Scientific Computing10.1007/s10915-022-02047-893:3Online publication date: 14-Nov-2022
https://dl.acm.org/doi/10.1007/s10915-022-02047-8
Deng SSun H(2021)A Preconditioned Difference of Convex Algorithm for Truncated Quadratic Regularization with Application to ImagingJournal of Scientific Computing10.1007/s10915-021-01547-388:2Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1007/s10915-021-01547-3
Liu YXu YYin W(2021)Acceleration of Primal–Dual Methods by Preconditioning and Simple Subproblem ProceduresJournal of Scientific Computing10.1007/s10915-020-01371-186:2Online publication date: 7-Jan-2021
https://dl.acm.org/doi/10.1007/s10915-020-01371-1
Sun H(2019)Analysis of Fully Preconditioned Alternating Direction Method of Multipliers with Relaxation in Hilbert SpacesJournal of Optimization Theory and Applications10.1007/s10957-019-01535-6183:1(199-229)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10957-019-01535-6
Bitterlich SBo? RCsetnek EWanka G(2019)The Proximal Alternating Minimization Algorithm for Two-Block Separable Convex Optimization Problems with Linear ConstraintsJournal of Optimization Theory and Applications10.1007/s10957-018-01454-y182:1(110-132)Online publication date: 20-Jul-2019
https://dl.acm.org/doi/10.1007/s10957-018-01454-y

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