×

Analysis of fully preconditioned alternating direction method of multipliers with relaxation in Hilbert spaces. (English) Zbl 1468.65075

Summary: Alternating direction method of multipliers is a powerful first-order method for non-smooth optimization problems including various applications in inverse problems and imaging. However, there is no clear result on the weak convergence of alternating direction method of multipliers in infinite-dimensional Hilbert spaces with relaxation. In this paper, by employing a kind of partial gap analysis, we prove the weak convergence of a general preconditioned and relaxed version in infinite-dimensional Hilbert spaces, with preconditioning for solving all the involved implicit equations under mild conditions. We also give the corresponding ergodic convergence rates respecting to the partial gap function. Furthermore, the connections between certain preconditioned and relaxed alternating direction method of multipliers and the corresponding Douglas-Rachford splitting methods are discussed. Numerical tests show the efficiency of the proposed overrelaxation variants with preconditioning.

MSC:

65K05 Numerical mathematical programming methods
65J15 Numerical solutions to equations with nonlinear operators
90C25 Convex programming
90C48 Programming in abstract spaces
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Software:

GADMM
PDFBibTeX XMLCite
Full Text: DOI

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) · Zbl 1229.90122 · doi:10.1561/2200000016
[2] Chambolle, A., Pock, T.: An introduction to continuous optimization for imaging. Acta Numerica 25, 161-319 (2016) · Zbl 1343.65064 · doi:10.1017/S096249291600009X
[3] 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ér. 9(2), 41-76 (1975) · Zbl 0368.65053
[4] Chan, T., Glowinski, R.: Finite Element Approximation and Iterative Solution of a Class of Mildly Non-linear Elliptic Equations. Stanford University, Stanford (1978)
[5] Glowinski, R., Osher, S., Yin, W. (eds.): Splitting Methods in Communication, Imaging, Science, and Engineering. Springer, Berlin (2016) · Zbl 1362.65002
[6] Glowinski, R.; Fitzgibbon, W. (ed.); Kuznetsov, YA (ed.); Neittaanmäki, P. (ed.); Pironneau, O. (ed.), On alternating direction methods of multipliers: a historical perspective, No. 34, 59-82 (2014), Berlin · Zbl 1320.65098
[7] Glowinski, R.: Variational Methods for the Numerical Solution of Nonlinear Elliptic Problems. SIAM, Philadelphia (2015) · Zbl 1333.65065 · doi:10.1137/1.9781611973785
[8] 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) · Zbl 1379.65036 · doi:10.1007/s10915-015-0048-x
[9] 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) · Zbl 0765.90073 · doi:10.1007/BF01581204
[10] 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) · Zbl 1338.90305 · doi:10.1137/140999025
[11] Zhang, X., Burger, M., Osher, S.: A unified primal-dual algorithm framework based on Bregman iteration. J. Sci. Comput. 46(1), 20-46 (2011) · Zbl 1227.65052 · doi:10.1007/s10915-010-9408-8
[12] 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) · Zbl 1267.90181 · doi:10.1137/110849468
[13] Fang, E.X., He, B., Liu, H., Yuan, X.: Generalized alternating direction method of multipliers: new theoretical insights and applications. Math. Program. Comput. 7(2), 149-187 (2015) · Zbl 1353.90110 · doi:10.1007/s12532-015-0078-2
[14] Glowinski, R., Le Tallec, P.: Augmented Lagrangians and Operator-Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia (1989) · Zbl 0698.73001 · doi:10.1137/1.9781611970838
[15] Glowinski, R.: Numerical Methods for Nonlinear Variational Problems. Springer, New York (1984) · Zbl 0536.65054 · doi:10.1007/978-3-662-12613-4
[16] Bredies, K., Sun, H.: A proximal-point analysis of preconditioned alternating direction method of multipliers. J. Optim. Theory Appl. 173(3), 878-907 (2017) · Zbl 1380.65101 · doi:10.1007/s10957-017-1112-5
[17] Bourgat, J.F., Dumay, J.M., Glowinski, R.: Large displacement calculations of flexible pipelines by finite element and nonlinear programming methods. SIAM J. Sci. Stat. Comput. 1(1), 34-81 (1980) · Zbl 0453.73090 · doi:10.1137/0901003
[18] Bermudez, A., Moreno, C.: Duality methods for solving variational inequalities. Comput. Math. Appl. 7(1), 43-85 (1981) · Zbl 0456.65036 · doi:10.1016/0898-1221(81)90006-7
[19] Fortin, M.; Glowinski, R.; Fortin, M. (ed.); Glowinski, R. (ed.), On decomposition-coordination methods using an augmented Lagrangian, 97-146 (1983), Amsterdam · doi:10.1016/S0168-2024(08)70028-6
[20] Bredies, K., Sun, H.: Accelerated Douglas-Rachford methods for the solution of convex-concave saddle-point problems. arXiv eprints, arXiv:1604.06282 · Zbl 1314.65084
[21] Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal-dual algorithm. Math. Program. 159(1), 253-287 (2016) · Zbl 1350.49035 · doi:10.1007/s10107-015-0957-3
[22] 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) · Zbl 1161.65332
[23] Gabay, D.; Fortin, M. (ed.); Glowinski, R. (ed.), Applications of the method of multipliers to variational inequalities, 299-331 (1983), Amsterdam · doi:10.1016/S0168-2024(08)70034-1
[24] 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) · Zbl 1343.94003 · doi:10.1007/s10851-015-0564-1
[25] Nien, H., Fessler, J.A.: Relaxed linearized algorithms for faster X-ray CT image reconstruction. IEEE Trans. Med. Imaging 35(4), 1090-8 (2016) · doi:10.1109/TMI.2015.2508780
[26] Yuan, J., Bae, E., Tai, X.: A study on continuous max-flow and min-cut approaches. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2217-2224 (2010)
[27] Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120-145 (2011) · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1
[28] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011) · Zbl 1218.47001 · doi:10.1007/978-1-4419-9467-7
[29] Ito, K., Kunisch, K.: Lagrange Multiplier Approach to Variational Problems and Applications. SIAM, Philadelphia (2008) · Zbl 1156.49002 · doi:10.1137/1.9780898718614
[30] 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)
[31] Chen, L., Sun, D., Toh, K.C.: An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming. Math. Program. 161(1-2), 237-270 (2017) · Zbl 1356.90105 · doi:10.1007/s10107-016-1007-5
[32] Ouyang, Y., Chen, Y., Lan Jr., G.E.P.: An accelerated linearized alternating direction method of multipliers. SIAM J. Imaging Sci. 8(1), 644-681 (2015) · Zbl 1321.90105 · doi:10.1137/14095697X
[33] Lions, P., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964-979 (1979) · Zbl 0426.65050 · doi:10.1137/0716071
[34] Setzer, S.: Split Bregman Algorithm, Douglas-Rachford Splitting and Frame Shrinkage. Scale Space and Variational Methods in Computer Vision, pp. 464-476. Springer, Berlin (2009)
[35] Reed, M., Simon, B.: Methods of Modern Mathematical Physics I: Functional Analysis. Academic Press, San Diego (1980) · Zbl 0459.46001
[36] Sun, H.: Analysis of fully preconditioned ADMM with relaxation in Hilbert spaces. arXiv eprints, arXiv:1611.04801 (2016)
[37] Bredies, K., Kunisch, K., Pock, T.: Total generalized variation. SIAM J. Imaging Sci. 3(3), 492-526 (2010) · Zbl 1195.49025 · doi:10.1137/090769521
[38] Xu, Y.: Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. SIAM J. Optim. 27(3), 1459-1484 (2017) · Zbl 1373.90111 · doi:10.1137/16M1082305
[39] Hintermüller, M., Rautenberg, C. N., Hahn, J.: Functional-analytic and numerical issues in splitting methods for total variation-based image reconstruction, Inverse Problems 30, 055014 (34pp) (2014) · Zbl 1293.94015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.