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  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 & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078
References:
[1]

X. J. CaiD. 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.  Google Scholar

[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.  Google Scholar

[3]

R. H. ChanM. 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.  Google Scholar

[4]

C. H. ChenB. S. HeY. 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.  Google Scholar

[5]

W. DengM. J. LaiZ. 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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[9]

D. R. HanH. 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.  Google Scholar

[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.  Google Scholar

[11]

D. R. HanX. 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.  Google Scholar

[12]

P. T. Harker and J. S. Pang, A damped-newton method for the linear complementarity problem, Lect. Appl. Math., 26 (1990), 265-284.   Google Scholar

[13]

B. S. HeL. 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.  Google Scholar

[14]

B. S. HeM. 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.  Google Scholar

[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.  Google Scholar

[16]

B. S. HeM. 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.  Google Scholar

[17]

B. S. HeM. 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.  Google Scholar

[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.  Google Scholar

[19]

H. J. HeD. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[22]

T. Y. LinS. 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.  Google Scholar

[23]

Z. C. LinR. S. Liu and Z. X. Su, Linearized alternating direction method with adaptive penalty for low-rank representation, Adv. Neural. Inform. Pr., (2011), 612-620.   Google Scholar

[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.  Google Scholar

[25]

J. Nocedal and S. Wright, Numerical Optimization, Springer Science & Business Media, 2006.  Google Scholar

[26]

Y. Y. OuyangY. M. ChenG. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[29]

D. F. SunK. 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.  Google Scholar

[30]

Y. L. WangJ. F. YangW. 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.  Google Scholar

show all references

References:
[1]

X. J. CaiD. 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.  Google Scholar

[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.  Google Scholar

[3]

R. H. ChanM. 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.  Google Scholar

[4]

C. H. ChenB. S. HeY. 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.  Google Scholar

[5]

W. DengM. J. LaiZ. 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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[9]

D. R. HanH. 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.  Google Scholar

[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.  Google Scholar

[11]

D. R. HanX. 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.  Google Scholar

[12]

P. T. Harker and J. S. Pang, A damped-newton method for the linear complementarity problem, Lect. Appl. Math., 26 (1990), 265-284.   Google Scholar

[13]

B. S. HeL. 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.  Google Scholar

[14]

B. S. HeM. 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.  Google Scholar

[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.  Google Scholar

[16]

B. S. HeM. 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.  Google Scholar

[17]

B. S. HeM. 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.  Google Scholar

[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.  Google Scholar

[19]

H. J. HeD. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[22]

T. Y. LinS. 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.  Google Scholar

[23]

Z. C. LinR. S. Liu and Z. X. Su, Linearized alternating direction method with adaptive penalty for low-rank representation, Adv. Neural. Inform. Pr., (2011), 612-620.   Google Scholar

[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.  Google Scholar

[25]

J. Nocedal and S. Wright, Numerical Optimization, Springer Science & Business Media, 2006.  Google Scholar

[26]

Y. Y. OuyangY. M. ChenG. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[29]

D. F. SunK. 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.  Google Scholar

[30]

Y. L. WangJ. F. YangW. 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.  Google Scholar

Figure 1.  Test images. (a) 256 × 256 House, (b) 256 × 256 Boy, (c) 512 × 512 Barbara, (d) 512 × 512 Tomandjerry
Figure 2.  The case of $A=I$: decomposed cartoons (above row) and textures (below row) by Algorithm 1
Figure 3.  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)
Figure 4.  Evolutions of objective function values with respect to iterations and computing time for the case of $A=S$ (test image: Boy image)
Figure 5.  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
Table 1.  Numerical results for quadratic programming problem (4.1)
$n_1$ $n_2=l$ $n_3$Algorithm HAlgorithm 1Algorithm 2Algorithm 3
Iter.Initer.TimeIter.Initer.TimeIter.Initer.TimeIter.Time
10010010071.07848.00.3450.01661.00.08162.0825.00.0969.00.04
20020020085.012015.00.7062.02316.00.16255.01685.00.3985.00.05
20030020084.09790.00.8351.01487.00.14327.02311.00.6988.00.05
30030030093.016177.01.5553.01527.00.22348.02784.01.2092.00.11
500300500103.030080.05.7756.02842.00.98441.03528.03.3985.00.59
50050050090.021683.04.5260.02390.01.02507.04161.04.8192.00.66
50060050091.021828.05.2359.02178.01.22548.04615.05.9793.00.70
60060060093.025832.010.1661.02637.02.06710.06390.010.1690.01.20
60080060091.028772.013.7262.02255.02.56692.06228.011.8491.01.31
80080080093.0224730.0270.9864.02185.05.73801.07209.025.8491.03.11
800100080098.0235200.0292.0664.02237.06.251134.010218.040.56105.03.25
100010001000108.0255521.0484.4564.02033.010.701226.011065.062.58195.07.16
$n_1$ $n_2=l$ $n_3$Algorithm HAlgorithm 1Algorithm 2Algorithm 3
Iter.Initer.TimeIter.Initer.TimeIter.Initer.TimeIter.Time
10010010071.07848.00.3450.01661.00.08162.0825.00.0969.00.04
20020020085.012015.00.7062.02316.00.16255.01685.00.3985.00.05
20030020084.09790.00.8351.01487.00.14327.02311.00.6988.00.05
30030030093.016177.01.5553.01527.00.22348.02784.01.2092.00.11
500300500103.030080.05.7756.02842.00.98441.03528.03.3985.00.59
50050050090.021683.04.5260.02390.01.02507.04161.04.8192.00.66
50060050091.021828.05.2359.02178.01.22548.04615.05.9793.00.70
60060060093.025832.010.1661.02637.02.06710.06390.010.1690.01.20
60080060091.028772.013.7262.02255.02.56692.06228.011.8491.01.31
80080080093.0224730.0270.9864.02185.05.73801.07209.025.8491.03.11
800100080098.0235200.0292.0664.02237.06.251134.010218.040.56105.03.25
100010001000108.0255521.0484.4564.02033.010.701226.011065.062.58195.07.16
[1]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[2]

Honglei Lang, Yunhe Sheng. Linearization of the higher analogue of Courant algebroids. Journal of Geometric Mechanics, 2020, 12 (4) : 585-606. doi: 10.3934/jgm.2020025

[3]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020461

[4]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[5]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[6]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[7]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[8]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[9]

Meilan Cai, Maoan Han. Limit cycle bifurcations in a class of piecewise smooth cubic systems with multiple parameters. Communications on Pure & Applied Analysis, 2021, 20 (1) : 55-75. doi: 10.3934/cpaa.2020257

[10]

Xin-Guang Yang, Lu Li, Xingjie Yan, Ling Ding. The structure and stability of pullback attractors for 3D Brinkman-Forchheimer equation with delay. Electronic Research Archive, 2020, 28 (4) : 1395-1418. doi: 10.3934/era.2020074

[11]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[12]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082

[13]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345

[14]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[15]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[16]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[17]

Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081

[18]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHum approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[19]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[20]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (301)
  • HTML views (1204)
  • Cited by (1)

Other articles
by authors

[Back to Top]