On the convergence analysis of the alternating direction method of multipliers with three blocks. (English) Zbl 1302.90148

Chen, Caihua; Shen, Yuan; You, Yanfei

Abstr. Appl. Anal. 2013, Article ID 183961, 7 p. (2013).

Summary: We consider a class of linearly constrained separable convex programming problems whose objective functions are the sum of three convex functions without coupled variables. For those problems, D. Han and X. Yuan [J. Optim. Theory Appl. 155, No. 1, 227–238 (2012; Zbl 1255.90093)] have shown that the sequence generated by the alternating direction method of multipliers (ADMM) with three blocks converges globally to their KKT points under some technical conditions. In this paper, a new proof of this result is found under new conditions which are much weaker than Han and Yuan’s assumptions. Moreover, in order to accelerate the ADMM with three blocks, we also propose a relaxed ADMM involving an additional computation of optimal step size and establish its global convergence under mild conditions.

MSC:

90C25

Convex programming

Keywords:

separable convex programming problems; KKT points; optimal step size; global convergence

Citations:

Zbl 1255.90093

Software:

Yall1; RecPF; RASL

References:

[1]	Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Computational Mathematics with Applications, 2, 17-40 (1976) · Zbl 0352.65034
[2]	Glowinski, R.; Marrocco, A., Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de Dirichlet non linéaires, 9, R-2, 41-76 (1975) · Zbl 0368.65053
[3]	Eckstein, J.; Bertsekas, D., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55, 3, 293-318 (1992) · Zbl 0765.90073
[4]	Gabay, D., Chapter ix applications of the method of multipliers to variational inequalities, Studies in Mathematics and Its Applications, 15, 299-331 (1983)
[5]	Glowinski, R., Numerical Methods for Nonlinear Variational Problems (1984), New York, NY, USA: Springer, New York, NY, USA · Zbl 0575.65123
[6]	Glowinski, R.; Le Tallec, P., Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, 9 (1989), Philadelphia, Pa, USA: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa, USA · Zbl 0698.73001
[7]	He, B.; Liao, L.; Han, D.; Yang, H., A new inexact alternating directions method for monotone variational inequalities, Mathematical Programming, 92, 1, 103-118 (2002) · Zbl 1009.90108
[8]	He, B.; Yuan, X., On the \(O(1 / n)\) convergence rate of the Douglas-Rachford alternating direction method, SIAM Journal on Numerical Analysis, 50, 2, 700-709 (2012) · Zbl 1245.90084
[9]	Chen, C.; He, B.; Yuan, X., Matrix completion via an alternating direction method, IMA Journal of Numerical Analysis, 32, 1, 227-245 (2012) · Zbl 1236.65043
[10]	Fazel, M.; Pong, T. K.; Sun, D. F.; Tseng, P., Hankel matrix rank minimization with applications to system identification and realization, SIAM Journal on Matrix Analysis and Applications, 34, 3, 946-977 (2012) · Zbl 1302.90127
[11]	He, B.; Xu, M.; Yuan, X., Solving large-scale least squares semidefinite programming by alternating direction methods, SIAM Journal on Matrix Analysis and Applications, 32, 1, 136-152 (2011) · Zbl 1243.49039
[12]	Yang, J.; Zhang, Y.; Yin, W., A fast alternating direction method for tvl1-l2 signal reconstruction from partial fourier data, IEEE Journal of Selected Topics in Signal Processing, 4, 2, 288-297 (2010)
[13]	Yang, J.; Zhang, Y., Alternating direction method algorithms for l1-problems in compressive sensing, SIAM Journal on Scientific Computing, 33, 1, 250-278 (2011) · Zbl 1256.65060
[14]	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
[15]	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
[16]	Yang, J.; Sun, D.; Toh, K., A proximal point algorithm for logdeterminant optimization with group Lasso regularization, SIAM Journal on Optimization, 23, 2, 857-293 (2013)
[17]	Peng, Y.; Ganesh, A.; Wright, J.; Xu, W.; Ma, Y., RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’10)
[18]	Mohan, K.; London, P.; Fazel, M.; Witten, D.; Lee, S. I., Node-based learning of multiple gaussian graphical models · Zbl 1318.62181
[19]	He, B.; Tao, M.; Xu, M. H.; Yuan, X. M., Alternating directions based contraction method for generally separable linearly constrained convex programming problems, Optimization, 62, 4, 573-596 (2013) · Zbl 1273.90122
[20]	He, B.; Tao, M.; Yuan, X., Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization, 22, 2, 313-340 (2012) · Zbl 1273.90152
[21]	Hong, M.; Luo, Z., On the linear convergence of the alternating direction Method of multipliers
[22]	Han, D.; Yuan, X., A note on the alternating direction method of multipliers, Journal of Optimization Theory and Applications, 155, 1, 227-238 (2012) · Zbl 1255.90093
[23]	Rockafellar, R., Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14, 5, 877-898 (1976) · Zbl 0358.90053
[24]	Rockafellar, R., Convex Analysis. Convex Analysis, Princeton Mathematical Series, no. 28 (1970), Princeton, NJ, USA: Princeton University Press, Princeton, NJ, USA · Zbl 0193.18401
[25]	Ye, C.; Yuan, X.-M., A descent method for structured monotone variational inequalities, Optimization Methods & Software, 22, 2, 329-338 (2007) · Zbl 1196.90118