Convergence analysis of alternating direction method of multipliers for a class of separable convex programming. (English) Zbl 1470.90079

Summary: The purpose of this paper is extending the convergence analysis of D. Han and X. Yuan [J. Optim. Theory Appl. 155, No. 1, 227–238 (2012; Zbl 1255.90093)] for alternating direction method of multipliers (ADMM) from the strongly convex to a more general case. Under the assumption that the individual functions are composites of strongly convex functions and linear functions, we prove that the classical ADMM for separable convex programming with two blocks can be extended to the case with more than three blocks. The problems, although still very special, arise naturally from some important applications, for example, route-based traffic assignment problems.


90C25 Convex programming


Zbl 1255.90093
Full Text: DOI


[1] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers and Mathematics with Applications, 2, 1, 17-40, (1976) · Zbl 0352.65034
[2] Gabay, D.; Fortin, M.; Glowinski, R., Applications of the method of multipliers to variational inequalities, Augmented Lagrangian Methods: Applications to Numerical Solution of Boundary-Value Problems, 299-331, (1983), Amsterdam, The Netherland: North-Holland Publisher, Amsterdam, The Netherland
[3] Tao, M.; Yuan, X., Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM Journal on Optimization, 21, 1, 57-81, (2011) · Zbl 1218.90115
[4] Ng, M. K.; Weiss, P.; Yuan, X., Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods, SIAM Journal on Scientific Computing, 32, 5, 2710-2736, (2010) · Zbl 1217.65071
[5] Rudin, L. I.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Physica D, 60, 1–4, 259-268, (1992) · Zbl 0780.49028
[6] Wen, Z.; Goldfarb, D.; Yin, W., Alternating direction augmented Lagrangian methods for semidefinite programming, Mathematical Programming Computation, 2, 3-4, 203-230, (2010) · Zbl 1206.90088
[7] Han, D.; Yuan, X., A note on the alternating direction method of multipliers, Journal of Optimization Theory and Applications, 155, 227-238, (2012) · Zbl 1255.90093
[8] Han, D. R.; Yuan, X. M.; Zhang, W. X.; Cai, X. J., An ADM-based splitting method for separable convex programming, Computational Optimization and Applications, 54, 343-369, (2013) · Zbl 1269.90078
[9] He, B. S.; Tao, M.; Yuan, X. M., Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization, 22, 313-340, (2012) · Zbl 1273.90152
[10] He, B. S.; Tao, M.; Xu, M. H.; Yuan, X. M., Alternating directions based contraction method for generally separable linearly constrained convex programming problems, Optimization, 62, 573-596, (2013) · Zbl 1273.90122
[11] He, B. S.; Tao, M.; Yuan, X. M., A splitting method for separable convex programming · Zbl 1273.90122
[12] Han, D.; Lo, H. K., Solving non-additive traffic assignment problems: a descent method for co-coercive variational inequalities, European Journal of Operational Research, 159, 3, 529-544, (2012) · Zbl 1065.90015
[13] Facchinei, F.; Pang, J. S., Finite-Dimensional Variational Inequalities and Complementary Problems. Volume I and II, (2003), New York, NY, USA: Springer, New York, NY, USA
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.