×

zbMATH — the first resource for mathematics

Iteration complexity on the generalized Peaceman-Rachford splitting method for separable convex programming. (English) Zbl 1431.90114
Summary: Recently, a generalized version of Peaceman-Rachford splitting method (GPRSM) for solving a convex minimization model with a general separable structure has been proposed and its global convergence has been proved by M. Sun and J. Liu [J. Appl. Math. Comput. 50, No. 1–2, 349–363 (2016; Zbl 1330.90079)]. In this paper, we establish the worst-case \(\mathcal{O}(1/t)\) convergence rate for the GPRSM in both the ergodic and a nonergodic senses, then we give some numerical results to demonstrate the convergence rate of the GPRSM.
MSC:
90C25 Convex programming
90C60 Abstract computational complexity for mathematical programming problems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Glowinski, R.; Marrocco, A., Approximation par elements finis dordre un, et la resolution, par penalisation-dualite, dune classe de problmes de Dirichlet non lineaires, RAIRO Anal Numer, 9, 41-76, (1975) · Zbl 0368.65053
[2] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput Math Appl, 2, 17-40, (1976) · Zbl 0352.65034
[3] Eckstein, J.; Bertsekas, D., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math Program, 55, 293-318, (1992) · Zbl 0765.90073
[4] Han, D.; Yuan, X., Local linear convergence of the alternating direction method of multipliers for quadratic programs, SIAM J Numer Anal, 51, 6, 3446-3457, (2013) · Zbl 1285.90033
[5] Peaceman, Dh; Rachford, Hh., The numerical solution of parabolic elliptic differential equations, SIAM J Appl Math, 3, 28-41, (1955) · Zbl 0067.35801
[6] Lions, Pl; Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J Numer Anal, 16, 964-979, (1979) · Zbl 0426.65050
[7] He, B.; Liu, H.; Wang, Z., A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM J Optim, 24, 3, 1011-1040, (2014) · Zbl 1327.90210
[8] Bertsekas, Dp., Constrained optimization and Lagrange multiplier methods, (1982), New York (NY): Academic Press, New York (NY)
[9] Sun, M.; Liu, J., A proximal Peaceman-Rachford splitting method for compressive sensing, J Appl Math Comput, 50, 349-363, (2016) · Zbl 1330.90079
[10] Applications of the method of multipliers to variational inequalities. In: Fortin M, Glowinski R, editors. Augmented Lagrange methods: applications to the solution of boundary-valued problems. Amsterdam: North-Holland; 1983. p. 299-331
[11] Glowinski, R.; Le Tallec, P., Augmented Lagrangian and operator splitting methods in nonlinear mechanics, (1989), Philadelphia (PA): SIAM, Philadelphia (PA) · Zbl 0698.73001
[12] Sun, M.; Liu, J., Generalized Peaceman-Rachford splitting method for separable convex programming with applications to image processing, J Appl Math Comput, 51, 605-622, (2016) · Zbl 1338.90307
[13] Sun, M.; Wang, Y.; Liu, J., Generalized Peaceman-Rachford splitting method for multiple-block separable convex programming with applications to robust PCA, Calcolo, 54, 77-94, (2017) · Zbl 1368.90129
[14] Li, M.; Yuan, X., A strictly contractive Peaceman-Rachford splitting method with logarithmic-quadratic proximal regularization for convex programming, Math Oper Res, 40, 4, 842-858, (2015) · Zbl 1329.90106
[15] He, B.; Yang, H., Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities, Oper Res Lett, 23, 151-161, (1998) · Zbl 0963.49006
[16] He, B.; Yuan, X., On the O(1/n) convergence rate of Douglas-Rachford alternating direction method, SIAM J Numer Anal, 50, 700-709, (2012) · Zbl 1245.90084
[17] Rockafellar, Rt., Convex analysis, (1970), Princeton (NJ): Princeton University Press, Princeton (NJ)
[18] Boyd, S.; Parikh, N.; Chu, E., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found Trends Mach Learn, 3, 1-122, (2011) · Zbl 1229.90122
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.