# American Institute of Mathematical Sciences

July  2018, 14(3): 833-855. doi: 10.3934/jimo.2017078

## Linearized block-wise alternating direction method of multipliers for multiple-block convex programming

 1 School of Economics and Management, Southeast University, Nanjing 210096, China 2 School of Mathematical Sciences, Jiangsu Key Labratory for NSLSCS, Nanjing Normal University, Nanjing 210023, China

1 Corresponding author

Received  June 2016 Revised  August 2017 Published  July 2018 Early access  September 2017

The alternating direction method of multipliers (ADMM) is an efficient approach for two-block separable convex programming, while it is not necessarily convergent when extending this method to multiple-block case directly. One appealing method is that converts the multiple-block variables into two groups firstly and then adopts the classic ADMM with inexact solving to the resulting model, which is so-called block-wise ADMM. However, solving the subproblems in block-wise ADMM are usually difficult when the linear mappings in the constraints are not diagonal or the proximal operator of the objective function is not easy to evaluate. Therefore, in this paper, we adopt the linearization technique to different terms presented in the block-wise ADMM subproblems, and obtain three kinds of linearized block-wise ADMM which make the subproblems easy to solve in general case. Moreover, under some mild conditions, we prove the global convergence of the three new methods and report some preliminary numerical results to indicate the feasibility and effectiveness of the linearization strategy.

Citation: Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial and Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078
##### References:
 [1] X. J. Cai, D. R. Han and X. M. Yuan, The direct extension of ADMM for three-block separable convex minimization models is convergent when one function is strongly convex, Comput. Optim. Appl., 66 (2017), 39-73.  doi: 10.1007/s10589-016-9860-y. [2] A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20 (2004), 89-97.  doi: 10.1023/B:JMIV.0000011321.19549.88. [3] R. H. Chan, M. Tao and X. M. Yuan, Linearized alternating direction method of multipliers for constrained linear least-squares problem, E. Asia J. Appl. Math., 2 (2012), 326-341.  doi: 10.4208/eajam.270812.161112a. [4] C. H. Chen, B. S. He, Y. Y. Ye and X. M. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5. [5] W. Deng, M. J. Lai, Z. M. Peng and W. T. Yin, Parallel multi-block ADMM with o(1/t) convergence, J. Sci. Comput., 71 (2017), 712-736.  doi: 10.1007/s10915-016-0318-2. [6] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1. [7] R. Glowinski and A. Marroco, 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, ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 9 (1975), 41-76. [8] T. Goldstein and S. Osher, The split Bregman method for $L_1$-regularized problems, SIAM J. Imaging Sci., 2 (2009), 323-343.  doi: 10.1137/080725891. [9] D. R. Han, H. J. He and L. L. Xu, A proximal parallel splitting method for minimizing sum of convex functions with linear constraints, J Comput. Appl. Math., 256 (2014), 36-51.  doi: 10.1016/j.cam.2013.07.010. [10] D. R. Han and X. M. Yuan, A note on the alternating direction method of multipliers, J. Optim. Theory Appl., 155 (2012), 227-238.  doi: 10.1007/s10957-012-0003-z. [11] D. R. Han, X. M. Yuan and W. X. Zhang, An augmented lagrangian based parallel splitting method for separable convex minimization with applications to image processing, Math. Comput., 83 (2014), 2263-2291.  doi: 10.1090/S0025-5718-2014-02829-9. [12] P. T. Harker and J. S. Pang, A damped-newton method for the linear complementarity problem, Lect. Appl. Math., 26 (1990), 265-284. [13] B. S. He, L. S. Hou and X. M. Yuan, On full jacobian decompositon of the augmented lagrangian method for separable convex programming, SIAM J. Optim., 25 (2015), 2274-2312.  doi: 10.1137/130922793. [14] B. S. He, M. Tao and X. M. Yuan, Alternating direction method with gaussian back substitution for separable convex programming, SIAM J. Optim., 22 (2012), 313-340.  doi: 10.1137/110822347. [15] B. S. He, M. Tao and X. M. Yuan, Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming, Math. Oper. Res. , (2017). doi: 10.1287/moor. 2016. 0822. [16] B. S. He, M. Tao and X. M. Yuan, A splitting method for separable convex programming, IMA J. Numer. Anal., 35 (2015), 394-426.  doi: 10.1093/imanum/drt060. [17] B. S. He, M. H. Xu and X. M. Yuan, Solving large-scale least squares covariance matrix problems by alternating direction methods, SIAM J. Matrix Anal. A., 32 (2011), 136-152.  doi: 10.1137/090768813. [18] B. S. He and X. M. Yuan, Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond, SMAI J Comput. Math., 1 (2015), 145-174.  doi: 10.5802/smai-jcm.6. [19] H. J. He, D. R. Han and Z. B. Li, Some projection methods with the BB step sizes for variational inequalities, J. Comput. Appl. Math., 236 (2012), 2590-2604.  doi: 10.1016/j.cam.2011.12.017. [20] M. Y. Hong and Z. Q. Luo, On the linear convergence of the alternating direction method of multipliers, Math. Program., 162 (2017), 165-199.  doi: 10.1007/s10107-016-1034-2. [21] M. Li, D. F. Sun and K. C. Toh, A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block Asia Pac. J. Oper. Res. , 32 (2015), 1550024, 19pp. doi: 10.1142/S0217595915500244. [22] T. Y. Lin, S. Q. Ma and S. Z. Zhang, On the sublinear convergence rate of multi-block ADMM, J. Oper. Res. Soc. China, 3 (2015), 251-274.  doi: 10.1007/s40305-015-0092-0. [23] Z. C. Lin, R. S. Liu and Z. X. Su, Linearized alternating direction method with adaptive penalty for low-rank representation, Adv. Neural. Inform. Pr., (2011), 612-620. [24] S. Q. Ma, Alternating proximal gradient method for convex minimization, J. Sci. Comput., 68 (2016), 546-572.  doi: 10.1007/s10915-015-0150-0. [25] J. Nocedal and S. Wright, Numerical Optimization, Springer Science & Business Media, 2006. [26] Y. Y. Ouyang, Y. M. Chen, G. H. Lan and E. P. Pasiliao Jr, An accelerated linearized alternating direction method of multipliers, SIAM J. Imaging Sci., 8 (2015), 644-681.  doi: 10.1137/14095697X. [27] X. Ren and Z. C. Lin, Linearized alternating direction method with adaptive penalty and warm starts for fast solving transform invariant low-rank textures, Int. J. Comput. Vis., 104 (2013), 1-14.  doi: 10.1007/s11263-013-0611-6. [28] H. Schaeffer and S. Osher, A low patch-rank interpretation of texture, SIAM J. Imaging Sci., 6 (2013), 226-262.  doi: 10.1137/110854989. [29] D. F. Sun, K. C. Toh and L. Yang, A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-type of constraints, SIAM J. Optim., 25 (2015), 882-915.  doi: 10.1137/140964357. [30] Y. L. Wang, J. F. Yang, W. T. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1 (2008), 248-272.  doi: 10.1137/080724265.

show all references

##### References:
 [1] X. J. Cai, D. R. Han and X. M. Yuan, The direct extension of ADMM for three-block separable convex minimization models is convergent when one function is strongly convex, Comput. Optim. Appl., 66 (2017), 39-73.  doi: 10.1007/s10589-016-9860-y. [2] A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20 (2004), 89-97.  doi: 10.1023/B:JMIV.0000011321.19549.88. [3] R. H. Chan, M. Tao and X. M. Yuan, Linearized alternating direction method of multipliers for constrained linear least-squares problem, E. Asia J. Appl. Math., 2 (2012), 326-341.  doi: 10.4208/eajam.270812.161112a. [4] C. H. Chen, B. S. He, Y. Y. Ye and X. M. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5. [5] W. Deng, M. J. Lai, Z. M. Peng and W. T. Yin, Parallel multi-block ADMM with o(1/t) convergence, J. Sci. Comput., 71 (2017), 712-736.  doi: 10.1007/s10915-016-0318-2. [6] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1. [7] R. Glowinski and A. Marroco, 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, ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 9 (1975), 41-76. [8] T. Goldstein and S. Osher, The split Bregman method for $L_1$-regularized problems, SIAM J. Imaging Sci., 2 (2009), 323-343.  doi: 10.1137/080725891. [9] D. R. Han, H. J. He and L. L. Xu, A proximal parallel splitting method for minimizing sum of convex functions with linear constraints, J Comput. Appl. Math., 256 (2014), 36-51.  doi: 10.1016/j.cam.2013.07.010. [10] D. R. Han and X. M. Yuan, A note on the alternating direction method of multipliers, J. Optim. Theory Appl., 155 (2012), 227-238.  doi: 10.1007/s10957-012-0003-z. [11] D. R. Han, X. M. Yuan and W. X. Zhang, An augmented lagrangian based parallel splitting method for separable convex minimization with applications to image processing, Math. Comput., 83 (2014), 2263-2291.  doi: 10.1090/S0025-5718-2014-02829-9. [12] P. T. Harker and J. S. Pang, A damped-newton method for the linear complementarity problem, Lect. Appl. Math., 26 (1990), 265-284. [13] B. S. He, L. S. Hou and X. M. Yuan, On full jacobian decompositon of the augmented lagrangian method for separable convex programming, SIAM J. Optim., 25 (2015), 2274-2312.  doi: 10.1137/130922793. [14] B. S. He, M. Tao and X. M. Yuan, Alternating direction method with gaussian back substitution for separable convex programming, SIAM J. Optim., 22 (2012), 313-340.  doi: 10.1137/110822347. [15] B. S. He, M. Tao and X. M. Yuan, Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming, Math. Oper. Res. , (2017). doi: 10.1287/moor. 2016. 0822. [16] B. S. He, M. Tao and X. M. Yuan, A splitting method for separable convex programming, IMA J. Numer. Anal., 35 (2015), 394-426.  doi: 10.1093/imanum/drt060. [17] B. S. He, M. H. Xu and X. M. Yuan, Solving large-scale least squares covariance matrix problems by alternating direction methods, SIAM J. Matrix Anal. A., 32 (2011), 136-152.  doi: 10.1137/090768813. [18] B. S. He and X. M. Yuan, Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond, SMAI J Comput. Math., 1 (2015), 145-174.  doi: 10.5802/smai-jcm.6. [19] H. J. He, D. R. Han and Z. B. Li, Some projection methods with the BB step sizes for variational inequalities, J. Comput. Appl. Math., 236 (2012), 2590-2604.  doi: 10.1016/j.cam.2011.12.017. [20] M. Y. Hong and Z. Q. Luo, On the linear convergence of the alternating direction method of multipliers, Math. Program., 162 (2017), 165-199.  doi: 10.1007/s10107-016-1034-2. [21] M. Li, D. F. Sun and K. C. Toh, A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block Asia Pac. J. Oper. Res. , 32 (2015), 1550024, 19pp. doi: 10.1142/S0217595915500244. [22] T. Y. Lin, S. Q. Ma and S. Z. Zhang, On the sublinear convergence rate of multi-block ADMM, J. Oper. Res. Soc. China, 3 (2015), 251-274.  doi: 10.1007/s40305-015-0092-0. [23] Z. C. Lin, R. S. Liu and Z. X. Su, Linearized alternating direction method with adaptive penalty for low-rank representation, Adv. Neural. Inform. Pr., (2011), 612-620. [24] S. Q. Ma, Alternating proximal gradient method for convex minimization, J. Sci. Comput., 68 (2016), 546-572.  doi: 10.1007/s10915-015-0150-0. [25] J. Nocedal and S. Wright, Numerical Optimization, Springer Science & Business Media, 2006. [26] Y. Y. Ouyang, Y. M. Chen, G. H. Lan and E. P. Pasiliao Jr, An accelerated linearized alternating direction method of multipliers, SIAM J. Imaging Sci., 8 (2015), 644-681.  doi: 10.1137/14095697X. [27] X. Ren and Z. C. Lin, Linearized alternating direction method with adaptive penalty and warm starts for fast solving transform invariant low-rank textures, Int. J. Comput. Vis., 104 (2013), 1-14.  doi: 10.1007/s11263-013-0611-6. [28] H. Schaeffer and S. Osher, A low patch-rank interpretation of texture, SIAM J. Imaging Sci., 6 (2013), 226-262.  doi: 10.1137/110854989. [29] D. F. Sun, K. C. Toh and L. Yang, A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-type of constraints, SIAM J. Optim., 25 (2015), 882-915.  doi: 10.1137/140964357. [30] Y. L. Wang, J. F. Yang, W. T. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1 (2008), 248-272.  doi: 10.1137/080724265.
Test images. (a) 256 × 256 House, (b) 256 × 256 Boy, (c) 512 × 512 Barbara, (d) 512 × 512 Tomandjerry
The case of $A=I$: decomposed cartoons (above row) and textures (below row) by Algorithm 1
Evolutions of objective function values with respect to iterations and computing time for the case of $A=I$ in the first 50 iterations (test image: Boy image)
Evolutions of objective function values with respect to iterations and computing time for the case of $A=S$ (test image: Boy image)
The case of $A=S$: test images with missing pixel (1st column), decomposed cartoon (2nd column) and textures (3rd column) by Algorithm 1, reconstructed images (4th column) by superposing the corresponding cartoons and textures
Numerical results for quadratic programming problem (4.1)
 $n_1$ $n_2=l$ $n_3$ Algorithm H Algorithm 1 Algorithm 2 Algorithm 3 Iter. Initer. Time Iter. Initer. Time Iter. Initer. Time Iter. Time 100 100 100 71.0 7848.0 0.34 50.0 1661.0 0.08 162.0 825.0 0.09 69.0 0.04 200 200 200 85.0 12015.0 0.70 62.0 2316.0 0.16 255.0 1685.0 0.39 85.0 0.05 200 300 200 84.0 9790.0 0.83 51.0 1487.0 0.14 327.0 2311.0 0.69 88.0 0.05 300 300 300 93.0 16177.0 1.55 53.0 1527.0 0.22 348.0 2784.0 1.20 92.0 0.11 500 300 500 103.0 30080.0 5.77 56.0 2842.0 0.98 441.0 3528.0 3.39 85.0 0.59 500 500 500 90.0 21683.0 4.52 60.0 2390.0 1.02 507.0 4161.0 4.81 92.0 0.66 500 600 500 91.0 21828.0 5.23 59.0 2178.0 1.22 548.0 4615.0 5.97 93.0 0.70 600 600 600 93.0 25832.0 10.16 61.0 2637.0 2.06 710.0 6390.0 10.16 90.0 1.20 600 800 600 91.0 28772.0 13.72 62.0 2255.0 2.56 692.0 6228.0 11.84 91.0 1.31 800 800 800 93.0 224730.0 270.98 64.0 2185.0 5.73 801.0 7209.0 25.84 91.0 3.11 800 1000 800 98.0 235200.0 292.06 64.0 2237.0 6.25 1134.0 10218.0 40.56 105.0 3.25 1000 1000 1000 108.0 255521.0 484.45 64.0 2033.0 10.70 1226.0 11065.0 62.58 195.0 7.16
 $n_1$ $n_2=l$ $n_3$ Algorithm H Algorithm 1 Algorithm 2 Algorithm 3 Iter. Initer. Time Iter. Initer. Time Iter. Initer. Time Iter. Time 100 100 100 71.0 7848.0 0.34 50.0 1661.0 0.08 162.0 825.0 0.09 69.0 0.04 200 200 200 85.0 12015.0 0.70 62.0 2316.0 0.16 255.0 1685.0 0.39 85.0 0.05 200 300 200 84.0 9790.0 0.83 51.0 1487.0 0.14 327.0 2311.0 0.69 88.0 0.05 300 300 300 93.0 16177.0 1.55 53.0 1527.0 0.22 348.0 2784.0 1.20 92.0 0.11 500 300 500 103.0 30080.0 5.77 56.0 2842.0 0.98 441.0 3528.0 3.39 85.0 0.59 500 500 500 90.0 21683.0 4.52 60.0 2390.0 1.02 507.0 4161.0 4.81 92.0 0.66 500 600 500 91.0 21828.0 5.23 59.0 2178.0 1.22 548.0 4615.0 5.97 93.0 0.70 600 600 600 93.0 25832.0 10.16 61.0 2637.0 2.06 710.0 6390.0 10.16 90.0 1.20 600 800 600 91.0 28772.0 13.72 62.0 2255.0 2.56 692.0 6228.0 11.84 91.0 1.31 800 800 800 93.0 224730.0 270.98 64.0 2185.0 5.73 801.0 7209.0 25.84 91.0 3.11 800 1000 800 98.0 235200.0 292.06 64.0 2237.0 6.25 1134.0 10218.0 40.56 105.0 3.25 1000 1000 1000 108.0 255521.0 484.45 64.0 2033.0 10.70 1226.0 11065.0 62.58 195.0 7.16
 [1] Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247 [2] Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial and Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067 [3] Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems and Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917 [4] Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047 [5] Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial and Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052 [6] Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1783-1799. doi: 10.3934/jimo.2019029 [7] Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030 [8] Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859 [9] Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial and Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037 [10] Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283 [11] Xin Yang, Nan Wang, Lingling Xu. A parallel Gauss-Seidel method for convex problems with separable structure. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 557-570. doi: 10.3934/naco.2020051 [12] Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317 [13] Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016 [14] Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial and Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135 [15] Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057 [16] Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349 [17] Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems and Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077 [18] Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543 [19] He Huang, Zhen He. A global optimization method for multiple response optimization problems. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022016 [20] Tomás Caraballo, David Cheban. On the structure of the global attractor for non-autonomous dynamical systems with weak convergence. Communications on Pure and Applied Analysis, 2012, 11 (2) : 809-828. doi: 10.3934/cpaa.2012.11.809

2020 Impact Factor: 1.801