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]

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 & Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030

[2]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053

[3]

Christoforidou Amalia, Christian-Oliver Ewald. A lattice method for option evaluation with regime-switching asset correlation structure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1729-1752. doi: 10.3934/jimo.2020042

[4]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

[5]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080

[6]

Yaonan Ma, Li-Zhi Liao. The Glowinski–Le Tallec splitting method revisited: A general convergence and convergence rate analysis. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1681-1711. doi: 10.3934/jimo.2020040

[7]

Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068

[8]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050

[9]

Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3295-3317. doi: 10.3934/dcds.2020406

[10]

Yusi Fan, Chenrui Yao, Liangyun Chen. Structure of sympathetic Lie superalgebras. Electronic Research Archive, , () : -. doi: 10.3934/era.2021020

[11]

Alexander Tolstonogov. BV solutions of a convex sweeping process with a composed perturbation. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021012

[12]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021035

[13]

Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022

[14]

Claudianor O. Alves, Giovany M. Figueiredo, Riccardo Molle. Multiple positive bound state solutions for a critical Choquard equation. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021061

[15]

Kai Cai, Guangyue Han. An optimization approach to the Langberg-Médard multiple unicast conjecture. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021001

[16]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[17]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[18]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058

[19]

Joel Fotso Tachago, Giuliano Gargiulo, Hubert Nnang, Elvira Zappale. Multiscale homogenization of integral convex functionals in Orlicz Sobolev setting. Evolution Equations & Control Theory, 2021, 10 (2) : 297-320. doi: 10.3934/eect.2020067

[20]

Youjun Deng, Hongyu Liu, Xianchao Wang, Dong Wei, Liyan Zhu. Simultaneous recovery of surface heat flux and thickness of a solid structure by ultrasonic measurements. Electronic Research Archive, , () : -. doi: 10.3934/era.2021027

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (314)
  • HTML views (1207)
  • Cited by (1)

Other articles
by authors

[Back to Top]