Randomized Primal–Dual Proximal Block Coordinate Updates

doi:10.1007/s40305-018-0232-4

Abstract

Abstract: In this paper, we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its O(1/t) convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such as a primal-dual method for bilinear saddle-point problems (PD-S), the proximal Jacobian alternating direction method of multipliers (Prox-JADMM) and a randomized variant of the ADMM for multi-block convex optimization. Our analysis recovers and/or strengthens the convergence properties of several existing algorithms. For example, for PD-S our result leads to the same order of convergence rate without the previously assumed boundedness condition on the constraint sets, and for Prox-JADMM the new result provides convergence rate in terms of the objective value and the feasibility violation. It is well known that the original ADMM may fail to converge when the number of blocks exceeds two. Our result shows that if an appropriate randomization procedure is invoked to select the updating blocks, then a sublinear rate of convergence in expectation can be guaranteed for multi-block ADMM, without assuming any strong convexity. The new approach is also extended to solve problems where only a stochastic approximation of the subgradient of the objective is available, and we establish an O(1/√t) convergence rate of the extended approach for solving stochastic programming.

Key words: Primal-dual method, Alternating direction method of multipliers (ADMM), Randomized algorithm, Iteration complexity, First-order stochastic approximation

CLC Number:

Xiang Gao, Yang-Yang Xu, Shu-Zhong Zhang. Randomized Primal–Dual Proximal Block Coordinate Updates[J]. Journal of the Operations Research Society of China, 2019, 7(2): 205-250.

TrendMD

References 47

[1]	James, G.M., Paulson, C., Rusmevichientong, P.:The constrained lasso. Technical report. University of Southern California (2013)
[2]	Rockafellar, R.T.:Large-scale extended linear-quadratic programming and multistage optimization. Advances in Numerical Partial Differential Equations and Optimization:In:Proceedings of the Fifth Mexico-United States Workshop, vol. 2, pp. 247-261(1991)
[3]	Hong, M., Chang, T.-H., Wang, X., Razaviyayn, M., Ma, S., Luo, Z.-Q.:A block successive upper bound minimization method of multipliers for linearly constrained convex optimization (2014). arXiv:1401.7079
[4]	Cui, Y., Li, X., Sun, D., Toh, K.-C.:On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions. J. Optim. Theory Appl. 169(3), 1013-1041(2016)
[5]	Chen, C., Li, M., Liu, X., Ye, Y.:On the convergence of multi-block alternating direction method of multipliers and block coordinate descent method (2015). arXiv:1508.00193
[6]	Gao, X., Zhang, S.:First-order algorithms for convex optimization with nonseparate objective and coupled constraints. J. Oper. Res. Soc. China 5(2), 131-159(2017)
[7]	Glowinski, R., Marrocco, A.:Sur l'approximation, par eléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de dirichlet non linéaires. ESAIM Math. Model. Numer. Anal. 9(R2), 41-76(1975)
[8]	Gabay, D., Mercier, B.:A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1), 17-40(1976)
[9]	Glowinski, R., Le Tallec, P.:Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, vol. 9. SIAM, Philadelphia (1989)
[10]	Eckstein, J., Bertsekas, D.:On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1-3), 293-318(1992)
[11]	He, B., Yuan, X.:On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J. Numer. Anal. 50(2), 700-709(2012)
[12]	Monteiro, R.D., Svaiter, B.F.:Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23(1), 475-507(2013)
[13]	Deng, W., Yin, W.:On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889-916(2015)
[14]	Lin, T., Ma, S., Zhang, S.:On the sublinear convergence rate of multi-block admm. J. Oper. Res. Soc. China 3(3), 251-274(2015)
[15]	Hong, M., Luo, Z.:On the linear convergence of the alternating direction method of multipliers. Math. Program. 162, 165-199(2017)
[16]	Boley, D.:Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs. SIAM J. Optim. 23(4), 2183-2207(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. IEEE Trans. Pattern Anal. Mach. Intell. 34(11), 2233- 2246(2012)
[18]	Tao, M., Yuan, X.:Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21(1), 57-81(2011)
[19]	Chen, C., He, B., Ye, Y., Yuan, X.:The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program. 155(1-2), 57-79(2016)
[20]	Deng, W., Lai, M.-J., Peng, Z., Yin, W.:Parallel multi-block ADMM with o(1/k) convergence. J. Sci. Comput. 71, 1-25(2016)
[21]	He, B., Tao, M., Yuan, X.:Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming. Math. Oper. Res. 42(3), 662-691(2017)
[22]	He, B., Hou, L., Yuan, X.:On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming. SIAM J. Optim. 25(4), 2274-2312(2015)
[23]	He, B., Tao, M., Yuan, X.:Alternating direction method with gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2), 313-340(2012)
[24]	Xu, Y.:Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming. SIAM J. Optim. 28(1), 646-670(2018)
[25]	Chen, C., Shen, Y., You, Y.:On the convergence analysis of the alternating direction method of multipliers with three blocks. In:Abstract and Applied Analysis, vol. 2013. Hindawi Publishing Corporation (2013)
[26]	Cai, X., Han, D., Yuan, X.:On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function. Comput. Optim. Appl. 66(1), 39-73(2017)
[27]	Lin, T., Ma, S., Zhang, S.:On the global linear convergence of the admm with multiblock variables. SIAM J. Optim. 25(3), 1478-1497(2015)
[28]	Li, M., Sun, D., Toh, K.-C.:A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block. Asia-Pac. J. Oper. Res. 32(04), 1550024(2015)
[29]	Han, D., Yuan, X.:A note on the alternating direction method of multipliers. J. Optim. Theory Appl. 155(1), 227-238(2012)
[30]	Wang, Y., Yin, W., Zeng, J.:Global convergence of ADMM in nonconvex nonsmooth optimization (2015). arXiv:1511.06324
[31]	Lin, T., Ma, S., Zhang, S.:Iteration complexity analysis of multi-block admm for a family of convex minimization without strong convexity. J. Sci. Comput. 69, 1-30(2016)
[32]	Chen, L., Sun, D., Toh, K.-C.:An efficient inexact symmetric gauss-seidel based majorized ADMM for high-dimensional convex composite conic programming. Math. Program. 161, 237-270(2017)
[33]	Li, X., Sun, D., Toh, K.-C.:A schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions. Math. Program. 155(1-2), 333-373(2016)
[34]	Sun, D., Toh, K.-C., Yang, L.:A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints. SIAM J. Optim. 25(2), 882-915(2015)
[35]	Sun, R., Luo, Z.-Q., Ye, Y.:On the expected convergence of randomly permuted ADMM (2015). arXiv:1503.06387
[36]	Dang, C., Lan, G.:Randomized first-order methods for saddle point optimization (2014). arXiv:1409.8625
[37]	Chambolle, A., Pock, T.:A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120-145(2011)
[38]	Peng, Z., Wu, T., Xu, Y., Yan, M., Yin, W.:Coordinate friendly structures, algorithms and applications. Ann. Math. Sci. Appl. 1(1), 57-119(2016)
[39]	Gao, X., Jiang, B., Zhang, S.:On the information-adaptive variants of the ADMM:an iteration complexity perspective. J. Sci. Comput. 76(1), 327-363(2018)
[40]	Xu, Y., Zhang, S.:Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization. Comput. Optim. Appl. 70(1), 91-128(2018)
[41]	Dang, C.D., Lan, G.:Stochastic block mirror descent methods for nonsmooth and stochastic optimization. SIAM J. Optim. 25(2), 856-881(2015)
[42]	Xu, Y., Yin, W.:Block stochastic gradient iteration for convex and nonconvex optimization. SIAM J. Optim. 25(3), 1686-1716(2015)
[43]	Grant, M., Boyd, S., Ye, Y.:CVX:Matlab software for disciplined convex programming, version 2.0 beta. http://cvxr.com/cvx (2013)
[44]	Nesterov, Y.:Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341-362(2012)
[45]	Richtárik, P., Takáč, M.:Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144(1-2), 1-38(2014)
[46]	Lu, Z., Xiao, L.:On the complexity analysis of randomized block-coordinate descent methods. Math. Program. 152(1-2), 615-642(2015)
[47]	Richtárik, P., Takáč,M.:Parallel coordinate descentmethodsfor big data optimization.Math. Program. 156, 1-52(2015)