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

doi:10.1007/s11464-018-0706-z

Front. Math. China

2018, Vol. 13

Issue (3) : 555-578 https://doi.org/10.1007/s11464-018-0706-z

RESEARCH ARTICLE

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

Yongguang HE¹, Huiyun LI², Xinwei LIU¹(

)

¹. Institute of Mathematics, Hebei University of Technology, Tianjin 300401, China
². School of Control Science and Engineering, Hebei University of Technology, Tianjin 300401, China

Download: PDF(514 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Xinwei LIU

Issue Date: 11 June 2018

Cite this article:

Yongguang HE,Huiyun LI,Xinwei LIU. Relaxed inertial proximal Peaceman-Rachford splitting method for separable convex programming[J]. Front. Math. China, 2018, 13(3): 555-578.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-018-0706-z
https://academic.hep.com.cn/fmc/EN/Y2018/V13/I3/555

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 https://doi.org/10.1023/A:1011253113155
2	Beck A, Teboulle M. A fast iterative Shrinkage-Thresholding algorithm for linear inverse problems. SIAM J Imaging Sci, 2009, 2(1): 183–202 https://doi.org/10.1137/080716542
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 l1-norm inequality constrained l1-norm minimization. Appl Numer Math, 2014, 85: 142–153 https://doi.org/10.1016/j.apnum.2014.05.012
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 https://doi.org/10.1137/15100463X
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 https://doi.org/10.1007/s10915-015-0048-x
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 https://doi.org/10.1016/0898-1221(76)90003-1
9	Gao B, Ma F. Symmetric ADMM with positive-indefinite proximal regularization for linearly constrained convex optimization. 2016,
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 https://doi.org/10.1007/978-94-017-9054-3_4
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 https://doi.org/10.1007/s11464-017-0631-6
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 https://doi.org/10.1137/120886753
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 https://doi.org/10.1007/978-3-319-41589-5_6
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 https://doi.org/10.1137/13090849X
17	He B S, Ma F. Convergence study on the proximal alternating direction method with larger step size. 2017,
18	He B S, Ma F, Yuan X M. On the step size of symmetric alternating directions method of multipliers. 2015,
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 https://doi.org/10.1137/15M1044448
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 https://doi.org/10.1007/s40305-016-0136-0
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 https://doi.org/10.1137/14099509X
22	Lions P L, Mercier B. Splitting algorithms for the sum of two nonlinear operators. SIAM J Numer Anal, 1979, 16(6): 964–979 https://doi.org/10.1137/0716071
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 https://doi.org/10.1186/s13660-017-1405-0
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 https://doi.org/10.1016/0167-2789(92)90242-F
26	Sun M, Liu J. A proximal Peaceman-Rachford splitting method for compressive sensing. J Appl Math Comput, 2016, 50(1-2): 349–363 https://doi.org/10.1007/s12190-015-0874-x
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 https://doi.org/10.1007/s12190-015-0922-6
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 https://doi.org/10.1007/s10092-016-0177-0
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 https://doi.org/10.1137/080724265
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)

[1]	Lijuan ZHAO,Wenyu SUN,Raimundo J. B. de SAMPAIO. Nonmonotone adaptive trust region method based on simple conic model for unconstrained optimization[J]. Front. Math. China, 2014, 9(5): 1211-1238.
[2]	Bingsheng HE, Zheng PENG, Xiangfeng WANG. Proximal alternating direction-based contraction methods for separable linearly constrained convex optimization[J]. Front Math Chin, 2011, 6(1): 79-114.

Viewed

Full text

Abstract

Cited

Shared

Discussed