A general framework for ADMM acceleration. (English) Zbl 1450.65051
Summary: The Alternating Direction Multipliers Method (ADMM) is a very popular algorithm for computing the solution of convex constrained minimization problems. Such problems are important from the application point of view, since they occur in many fields of science and engineering. ADMM is a powerful numerical tool, but unfortunately its main drawback is that it can exhibit slow convergence. Several approaches for its acceleration have been proposed in the literature and in this paper we present a new general framework devoted to this aim. In particular, we describe an algorithmic framework that makes possible the application of any acceleration step while still having the guarantee of convergence. This result is achieved thanks to a guard condition that ensures the monotonic decrease of the combined residual. The proposed strategy is applied to image deblurring problems. Several acceleration techniques are compared; to the best of our knowledge, some of them are investigated for the first time in connection with ADMM. Numerical results show that the proposed framework leads to a faster convergence with respect to other acceleration strategies recently introduced for ADMM.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
Software:
EPSfunReferences:
| [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] | Chen, C.; Chan, RH; Ma, S.; Yang, J., Inertial proximal ADMM for linearly constrained separable convex optimization, SIAM J. Imag. Sci., 8, 4, 2239-2267 (2015) · Zbl 1328.65134 · doi:10.1137/15100463X |
| [3] | Goldstein, T.; O’Donoghue, B.; Setzer, S.; Baraniuk, R., Fast alternating direction optimization methods, SIAM J. Imag. Sci., 7, 3, 1588-1623 (2014) · Zbl 1314.49019 · doi:10.1137/120896219 |
| [4] | Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Img. Sci., 2, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542 |
| [5] | Nesterov, Y.: Introductory Lectures on Convex Optimization: a Basic Course. Kluwer Academic Publishers (2004) · Zbl 1086.90045 |
| [6] | Biggs, DSC; Andrews, M., Acceleration of iterative image restoration algorithms, Appl. Opt., 36, 1766-1775 (1997) · doi:10.1364/AO.36.001766 |
| [7] | Dell’Acqua, P., ν acceleration of statistical iterative methods for image restoration, Signal Image Vid Process, 10, 927-934 (2016) · doi:10.1007/s11760-015-0842-9 |
| [8] | Hanke, M., Accelerated Landweber iterations for the solutions of ill-posed equations, Numer. Math., 60, 341-373 (1991) · Zbl 0745.65038 · doi:10.1007/BF01385727 |
| [9] | Landweber, L., An iteration formula for Fredholm integral equations of the first kind, Am. J. Math., 73, 615-624 (1951) · Zbl 0043.10602 · doi:10.2307/2372313 |
| [10] | Brezinski, C.; Redivo-Zaglia, M., The simplified topological ε-algorithms for accelerating sequences in a vector space, SIAM J. Sci. Comput., 36, A2227-A2247 (2014) · Zbl 1308.65006 · doi:10.1137/140957044 |
| [11] | Chan, RH; Tao, M.; Yuan, X., Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers, SIAM J. Imaging Sci., 6, 1, 680-697 (2013) · Zbl 1279.68322 · doi:10.1137/110860185 |
| [12] | Lanza, A., Morigi, S., Pragliola, M., Sgallari, F.: Space-variant TV regularization for image restoration. In: European Congress on Computational Methods in Applied Sciences and Engineering, pp 160-169. Springer (2017) |
| [13] | Almeida, MS; Figueiredo, M., Deconvolving images with unknown boundaries using the alternating direction method of multipliers, IEEE Trans. Image Process., 22, 8, 3074-3086 (2013) · Zbl 1373.94019 · doi:10.1109/TIP.2013.2258354 |
| [14] | Rudin, L.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Physica D, 60, 259-268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [15] | Lanza, A.; Morigi, S.; Sgallari, F., Convex image denoising via non-convex regularization with parameter selection, J. Math. Imag. Vis., 56, 2, 195-220 (2016) · Zbl 1391.94088 · doi:10.1007/s10851-016-0655-7 |
| [16] | Almeida, M.S., Figueiredo, M.A.: Frame-based image deblurring with unknown boundary conditions using the alternating direction method of multipliers. In: 2013 20th IEEE International Conference on Image Processing (ICIP), pp 582-585. IEEE (2013) |
| [17] | Hansen, PC; Nagy, JG; O’leary, DP, Deblurring Images: Matrices, Spectra, and Filtering, vol. 3 (2006), Philadelphia: Siam, Philadelphia · Zbl 1112.68127 |
| [18] | He, B.; Yuan, X., On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numer. Math., 130, 3, 567-577 (2015) · Zbl 1320.90060 · doi:10.1007/s00211-014-0673-6 |
| [19] | Gazzola, S.; Karapiperi, A., Image reconstruction and restoration using the simplified ε-algorithm, Appl. Math. Comput., 274, 539-555 (2016) · Zbl 1410.94005 |
| [20] | Shanks, D., Nonlinear transformations of divergent and slowly convergent sequences, J. Math. Phys., 34, 1-42 (1955) · Zbl 0067.28602 · doi:10.1002/sapm19553411 |
| [21] | Wynn, P., On a device for computing the em(Sn) transformation, MTAC, 10, 91-96 (1956) · Zbl 0074.04601 |
| [22] | Brezinski, C., Généralisations de la transformation de Shanks, de la table de Padé et de l’ε-algorithme, Calcolo, 12, 317-360 (1975) · Zbl 0329.65006 · doi:10.1007/BF02575753 |
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.
