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.

Key words： 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)