Relaxed inertial proximal Peaceman-Rachford splitting method for separable convex programming

Abstract

The strictly contractive Peaceman-Rachford splitting method is one of effective methods for solving separable convex optimization problem, and the inertial proximal Peaceman-Rachford splitting method is one of its important variants. It is known that the convergence of the inertial proximal Peaceman-Rachford splitting method can be ensured if the relaxation factor in Lagrangian multiplier updates is underdetermined, which means that the steps for the Lagrangian multiplier updates are shrunk conservatively. Although small steps play an important role in ensuring convergence, they should be strongly avoided in practice. In this article, we propose a relaxed inertial proximal Peaceman-Rachford splitting method, which has a larger feasible set for the relaxation factor. Thus, our method provides the possibility to admit larger steps in the Lagrangian multiplier updates. We establish the global convergence of the proposed algorithm under the same conditions as the inertial proximal Peaceman-Rachford splitting method. Numerical experimental results on a sparse signal recovery problem in compressive sensing and a total variation based image denoising problem demonstrate the effectiveness of our method.

Keywords

Convex programming / inertial proximal Peaceman-Rachford splitting method / relaxation factor / global convergence

References

[1] Alvarez F, Attouch H. An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping. Set-Valued Analysis, 2001, 9(1-2): 3–11

[2] Beck A, Teboulle M. A fast iterative Shrinkage-Thresholding algorithm for linear inverse problems. SIAM J Imaging Sci, 2009, 2(1): 183–202

[3] Bertsekas D P. Constrained Optimization and Lagrange Multiplier Methods.New York: Academic Press, 1982

[4] Cao S H, Xiao Y H, Zhu H. Linearized alternating directions method for l₁-norm inequality constrained l₁-norm minimization. Appl Numer Math, 2014, 85: 142–153

[5] Chen C H, Chan R H, Ma S Q, Yang J F. Inertial proximal ADMM for linearly constrained separable convex optimization. SIAM J Imaging Sci, 2015, 8(4): 2239–2267

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

[7] Dou M Y, Li H Y, Liu X W. An inertial proximal Peaceman-Rachford splitting method. Sci China Math (Chin Ser), 2016, 47(2): 333–348 (in Chinese)

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

[9] Gao B, Ma F. Symmetric ADMM with positive-indefinite proximal regularization for linearly constrained convex optimization. 2016, http://www.optimization-online.org/DB FILE/2017/03/5915.pdf

[10] Glowinski R. On alternating direction methods of multipliers: a historical perspective. In: Fitzgibbon W, Kuznetsov Yu A, Neittaanmäki P, Pironneau O, eds. Modeling, Simulation and Optimization for Science and Technology. Computational Methods in Applied Sciences, Vol 34. Dordrecht: Springer, 2014, 59–82

[11] Gu Y. An improved strictly contractive Peaceman-Rachford splitting method. M S Thesis, Nanjing Normal University. Nanjing, 2015

[12] Gu Y, Jiang B, Han D R. A semi-proximal-based strictly contractive Peaceman-Rachford splitting method. arXiv: 1506.02221

[13] Guo K, Han D R, Wang D Z W, Wu T T. Convergence of ADMM for multi-block nonconvex separable optimization models. Front Math China, 2017, 12(5): 1139–1162

[14] Han D R, Yuan X M. Local linear convergence of the alternating direction method of multipliers for quadratic programs. SIAM J Numer Anal, 2013, 51(6): 3446–3457

[15] He B S, Liu H, Lu J W, Yuan X M. Application of the strictly contractive Peaceman-Rachford splitting method to multi-block separable convex programming. In: Glowinski R, Osher S J, Yin W T, eds. Splitting Methods in Communication, Imaging, Science, and Engineering. Scientific Computation.Cham: Springer, 2016: 195–235

[16] He B S, Liu H, Wang Z R, Yuan X M. A strictly contractive Peaceman-Rachford splitting method for convex programming. SIAM J Optim, 2014, 24(3): 1011–1040

[17] He B S, Ma F. Convergence study on the proximal alternating direction method with larger step size. 2017, http://www.optimization-online.org/DB FILE/2017/02/5856.pdf

[18] He B S, Ma F, Yuan X M. On the step size of symmetric alternating directions method of multipliers. 2015, http://www.optimization-online.org/DB FILE/2015/05/4925.pdf

[19] He B S, Ma F, Yuan X M. Convergence study on the symmetric version of ADMM with larger step sizes. SIAM J Imaging Sci, 2016, 9(3): 1467–1501

[20] He B S, Yuan X M. Alternating direction method of multipliers for linear programming. J Oper Res Soc China, 2016, 4(4): 1–12

[21] Li X X, Yuan X M. A proximal strictly contractive Peaceman-Rachford splitting method for convex programming with applications to imaging. SIAM J Imaging Sci, 2015, 8(2): 1332–1365

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

[23] Liu J, Duan Y R, Sun M. A symmetric version of the generalized alternating direction method of multipliers for two-block separable convex programming. J Inequal Appl, 2017, 2017(1): 129

[24] Na S, Hsieh C J. Sparse learning with semi-proximal-based strictly contractive Peaceman-Rachford splitting method. arXiv: 1612.09357

[25] Rudin L I, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms. Phys D, 1992, 60(1-4): 259–268

[26] Sun M, Liu J. A proximal Peaceman-Rachford splitting method for compressive sensing. J Appl Math Comput, 2016, 50(1-2): 349–363

[27] Sun M, Liu J. Generalized Peaceman-Rachford splitting method for separable convex programming with applications to image processing. J Appl Math Comput, 2016, 51(1-2): 605–622

[28] Sun M,Wang Y J, Liu J. Generalized Peaceman-Rachford splitting method for multipleblock separable convex programming with applications to robust PCA. Calcolo, 2017, 54(1): 77–94

[29] Wang Y L, Yang J F, Yin W T, Zhang Y. A new alternating minimization algorithm for total variation image reconstruction. SIAM J Imaging Sci, 2008, 1(3): 248–272

[30] Wen Z W, Yin W T, Liu X, Zhang Y. Introduction to compressive sensing and sparse optimization. Oper Res Trans, 2012, 16(3): 49–64 (in Chinese)

[31] Yuan Y X. Nonlinear Optimization Methods.Beijing: Sciences Press, 2008 (in Chinese)

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature