doi: 10.3934/jimo.2018067

A proximal alternating direction method for multi-block coupled convex optimization

1. 

Institute of Electromagnetics and Acoustics, Department of Electronic Science, Xiamen University, Xiamen, 361005, China

2. 

School of Mathematical Sciences, Nanjing Normal University, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210023, China

* Corresponding author

Received  August 2016 Revised  December 2017 Published  June 2018

Fund Project: The second author is supported by the National Natural Science Foundation of China [Grant No. 11401314]

In this paper, we propose a proximal alternating direction method (PADM) for solving the convex optimization problems with linear constraints whose objective function is the sum of multi-block separable functions and a coupled quadratic function. The algorithm generates the iterate via a simple correction step, where the descent direction is based on the PADM. We prove the convergence of the generated sequence under some mild assumptions. Finally, some familiar numerical results are reported for the new algorithm.

Citation: Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2018067
References:
[1]

A. AgarwalS. Negahban and M. J. Wainwright, Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions, Ann. Appl. Stat., 40 (2012), 1171-1197. doi: 10.1214/12-AOS1000.

[2]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imag. Sci., 2 (2009), 183-202. doi: 10.1137/080716542.

[3]

S. BoydN. ParikhE. ChuB. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, FnT Mach. Learn., 3 (2010), 1-122. doi: 10.1561/2200000016.

[4]

X. CaiD. Han and X. Yuan, 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 (2017), 39-73. doi: 10.1007/s10589-016-9860-y.

[5]

C. ChenB. HeX. Yuan and Y. Ye, The direct extension of ADMM for Muti-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79. doi: 10.1007/s10107-014-0826-5.

[6]

C. ChenM. LiX. Liu and Y. Ye, Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: Convergence analysis and insights, Mathematics, 65 (2017), 1231-1249. doi: 10.1287/opre.2017.1615.

[7]

C. Chen, Y. Shen and Y. You, On the convergence analysis of the alternating direction method of multipliers with three blocks, Abstr. Appl. Anal., 2013 (2013), Art. ID 183961, 7 pp.

[8]

Y. CuiX. LiD. Sun and K. C. Toh, On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions, J. Optim. Theory Appl., 169 (2016), 1013-1041. doi: 10.1007/s10957-016-0877-2.

[9]

D. Davis and W. Yin, Convergence rate analysis of several splitting schemes, UCLA CAM Report, (2014), 14-51.

[10]

W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, J Sci. Comput., 66 (2016), 889-916. doi: 10.1007/s10915-015-0048-x.

[11]

J. Eckstein and M. Fukushima, Some reformulation and applications of the alternating direction method of multipliers, Scale Optim., (1994), 115-134.

[12]

J. Eckstein and D. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318. doi: 10.1007/BF01581204.

[13]

F. Facchinei and C. Kanzow, Penalty methods for the solution of generalized Nash equilibrium problems, SIAM J. Control. Optim., 20 (2010), 2228-2253. doi: 10.1137/090749499.

[14]

C. FengH. Xu and B. Li, An Alternating direction method approach to cloud traffic management, IEEE T. Parall. Distr., 28 (2017), 2145-2158. doi: 10.1109/TPDS.2017.2658620.

[15]

M. Fortin and R. Glowinski, Augmented Lagrangian methods: Applications to the numerical solution of boundary value problems, Stud. Math. Appl., 15 (1983), xix+340 pp.

[16]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Optim. Appl., 2 (1976), 17-40. doi: 10.1016/0898-1221(76)90003-1.

[17]

X. Gao and S. Zhang, First-Order algorithms for convex optimization with nonseparable objective and coupled constraints, J Oper. Res. Soc. China., 5 (2017), 131-159. doi: 10.1007/s40305-016-0131-5.

[18]

R. Glowinski and A. Marroco, Sur l'approximation, par elements finis d'ordre un, et la resolution, par penalisation-dualite, d'une classe de problemes de dirichlet non lineares, J Equine. Vet. Sci., 9 (1975), 41-76.

[19]

D. HanX. Yuan and W. 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.

[20]

D. Han and X. 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.

[21]

D. HanX. YuanW. Zhang and X. Cai, An ADM-based splitting method for separable convex programming, Comput. Optim. Appl., 54 (2013), 343-369. doi: 10.1007/s10589-012-9510-y.

[22]

B. He, Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities, Comput. Optim. Appl., 42 (2009), 195-212. doi: 10.1007/s10589-007-9109-x.

[23]

B. HeH. YangQ. Meng and D. Han, Modified Goldstein-Levitin-Polyak projection method for asymmetric strongly monotone variational inequalities, J. Optim. Theory Appl., 112 (2002), 129-143. doi: 10.1023/A:1013048729944.

[24]

B. HeM. Tao and X. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim., 22 (2012), 313-340. doi: 10.1137/110822347.

[25]

B. HeM. Tao and X. Yuan, A splitting method for separable convex programming, IMA J Numer. Anal., 35 (2015), 394-426. doi: 10.1093/imanum/drt060.

[26]

B. HeL. Hou and X. Yuan, On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, SIAM J. Optim., 25 (2015), 2274-2312. doi: 10.1137/130922793.

[27]

M. Hong, T. Chang, X. Wang, M. Razaviyayn, S. Ma and Z. Luo, A block successive upper bound minimization method of multipliers for linearly constrained convex optimization, Mathematics, 2014.

[28]

M. HongZ. Luo and M. Razaviyayn, Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim., 26 (2016), 337-364. doi: 10.1137/140990309.

[29]

M. Hong and Z. 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.

[30]

G. James, C. Paulson and P. Rusmevichientong, The Constrained Lasso, Technical report, University of Southern California, 2013.

[31]

X. LiD. Sun and K. C. Toh, A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math. Program., 155 (2016), 333-373. doi: 10.1007/s10107-014-0850-5.

[32]

T. LinS. Ma and S. Zhang, On the global linear convergence of the ADMM with multi-block variables, SIAM J. Optim., 25 (2015), 1478-1497. doi: 10.1137/140971178.

[33]

J. F. MotaJ. M. XavierP. M. Aguiar and M. Puschel, Distributed optimization with local domains: Application in MPF and network flows, IEEE T. Automat. Contr., 60 (2015), 2004-2009. doi: 10.1109/TAC.2014.2365686.

[34]

Y. PengA. GaneshJ. WrightW. Xu and Y. Ma, Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE T. Pattern. Anal., 34 (2012), 2233-2246. doi: 10.1109/CVPR.2010.5540138.

[35]

R. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1 (1976), 97-116. doi: 10.1287/moor.1.2.97.

[36]

D. SunK. C. Toh and L. Yang, A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-block constraints, SIAM J. Optim., 25 (2015), 882-915. doi: 10.1137/140964357.

[37]

L. Xu and D. Han, A proximal alternating direction method for weakly coupled variational inequalities, Pacific J. Optim., 9 (2013), 155-166.

[38]

J. Yang and Y. Zhang, Alternating direction algorithms for $ \ell_1$-Problems in compressive sensing, SIAM J. Sci. Comput., 33 (2011), 250-278. doi: 10.1137/090777761.

[39]

X. Yuan, An improved proximal alternating directions method for monotone variational inequalities with separable structure, Comput. Optim. Appl., 49 (2011), 17-29. doi: 10.1007/s10589-009-9293-y.

show all references

References:
[1]

A. AgarwalS. Negahban and M. J. Wainwright, Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions, Ann. Appl. Stat., 40 (2012), 1171-1197. doi: 10.1214/12-AOS1000.

[2]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imag. Sci., 2 (2009), 183-202. doi: 10.1137/080716542.

[3]

S. BoydN. ParikhE. ChuB. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, FnT Mach. Learn., 3 (2010), 1-122. doi: 10.1561/2200000016.

[4]

X. CaiD. Han and X. Yuan, 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 (2017), 39-73. doi: 10.1007/s10589-016-9860-y.

[5]

C. ChenB. HeX. Yuan and Y. Ye, The direct extension of ADMM for Muti-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79. doi: 10.1007/s10107-014-0826-5.

[6]

C. ChenM. LiX. Liu and Y. Ye, Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: Convergence analysis and insights, Mathematics, 65 (2017), 1231-1249. doi: 10.1287/opre.2017.1615.

[7]

C. Chen, Y. Shen and Y. You, On the convergence analysis of the alternating direction method of multipliers with three blocks, Abstr. Appl. Anal., 2013 (2013), Art. ID 183961, 7 pp.

[8]

Y. CuiX. LiD. Sun and K. C. Toh, On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions, J. Optim. Theory Appl., 169 (2016), 1013-1041. doi: 10.1007/s10957-016-0877-2.

[9]

D. Davis and W. Yin, Convergence rate analysis of several splitting schemes, UCLA CAM Report, (2014), 14-51.

[10]

W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, J Sci. Comput., 66 (2016), 889-916. doi: 10.1007/s10915-015-0048-x.

[11]

J. Eckstein and M. Fukushima, Some reformulation and applications of the alternating direction method of multipliers, Scale Optim., (1994), 115-134.

[12]

J. Eckstein and D. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318. doi: 10.1007/BF01581204.

[13]

F. Facchinei and C. Kanzow, Penalty methods for the solution of generalized Nash equilibrium problems, SIAM J. Control. Optim., 20 (2010), 2228-2253. doi: 10.1137/090749499.

[14]

C. FengH. Xu and B. Li, An Alternating direction method approach to cloud traffic management, IEEE T. Parall. Distr., 28 (2017), 2145-2158. doi: 10.1109/TPDS.2017.2658620.

[15]

M. Fortin and R. Glowinski, Augmented Lagrangian methods: Applications to the numerical solution of boundary value problems, Stud. Math. Appl., 15 (1983), xix+340 pp.

[16]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Optim. Appl., 2 (1976), 17-40. doi: 10.1016/0898-1221(76)90003-1.

[17]

X. Gao and S. Zhang, First-Order algorithms for convex optimization with nonseparable objective and coupled constraints, J Oper. Res. Soc. China., 5 (2017), 131-159. doi: 10.1007/s40305-016-0131-5.

[18]

R. Glowinski and A. Marroco, Sur l'approximation, par elements finis d'ordre un, et la resolution, par penalisation-dualite, d'une classe de problemes de dirichlet non lineares, J Equine. Vet. Sci., 9 (1975), 41-76.

[19]

D. HanX. Yuan and W. 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.

[20]

D. Han and X. 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.

[21]

D. HanX. YuanW. Zhang and X. Cai, An ADM-based splitting method for separable convex programming, Comput. Optim. Appl., 54 (2013), 343-369. doi: 10.1007/s10589-012-9510-y.

[22]

B. He, Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities, Comput. Optim. Appl., 42 (2009), 195-212. doi: 10.1007/s10589-007-9109-x.

[23]

B. HeH. YangQ. Meng and D. Han, Modified Goldstein-Levitin-Polyak projection method for asymmetric strongly monotone variational inequalities, J. Optim. Theory Appl., 112 (2002), 129-143. doi: 10.1023/A:1013048729944.

[24]

B. HeM. Tao and X. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim., 22 (2012), 313-340. doi: 10.1137/110822347.

[25]

B. HeM. Tao and X. Yuan, A splitting method for separable convex programming, IMA J Numer. Anal., 35 (2015), 394-426. doi: 10.1093/imanum/drt060.

[26]

B. HeL. Hou and X. Yuan, On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, SIAM J. Optim., 25 (2015), 2274-2312. doi: 10.1137/130922793.

[27]

M. Hong, T. Chang, X. Wang, M. Razaviyayn, S. Ma and Z. Luo, A block successive upper bound minimization method of multipliers for linearly constrained convex optimization, Mathematics, 2014.

[28]

M. HongZ. Luo and M. Razaviyayn, Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim., 26 (2016), 337-364. doi: 10.1137/140990309.

[29]

M. Hong and Z. 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.

[30]

G. James, C. Paulson and P. Rusmevichientong, The Constrained Lasso, Technical report, University of Southern California, 2013.

[31]

X. LiD. Sun and K. C. Toh, A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math. Program., 155 (2016), 333-373. doi: 10.1007/s10107-014-0850-5.

[32]

T. LinS. Ma and S. Zhang, On the global linear convergence of the ADMM with multi-block variables, SIAM J. Optim., 25 (2015), 1478-1497. doi: 10.1137/140971178.

[33]

J. F. MotaJ. M. XavierP. M. Aguiar and M. Puschel, Distributed optimization with local domains: Application in MPF and network flows, IEEE T. Automat. Contr., 60 (2015), 2004-2009. doi: 10.1109/TAC.2014.2365686.

[34]

Y. PengA. GaneshJ. WrightW. Xu and Y. Ma, Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE T. Pattern. Anal., 34 (2012), 2233-2246. doi: 10.1109/CVPR.2010.5540138.

[35]

R. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1 (1976), 97-116. doi: 10.1287/moor.1.2.97.

[36]

D. SunK. C. Toh and L. Yang, A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-block constraints, SIAM J. Optim., 25 (2015), 882-915. doi: 10.1137/140964357.

[37]

L. Xu and D. Han, A proximal alternating direction method for weakly coupled variational inequalities, Pacific J. Optim., 9 (2013), 155-166.

[38]

J. Yang and Y. Zhang, Alternating direction algorithms for $ \ell_1$-Problems in compressive sensing, SIAM J. Sci. Comput., 33 (2011), 250-278. doi: 10.1137/090777761.

[39]

X. Yuan, An improved proximal alternating directions method for monotone variational inequalities with separable structure, Comput. Optim. Appl., 49 (2011), 17-29. doi: 10.1007/s10589-009-9293-y.

Figure 1.  Convergence precision of all algorithms, the error is given by $\|Ax-b\|.$.
Figure 2.  Solve GNEP with self-adaptive stepsize
Figure 3.  Solve GNEP with fixed stepsize $\alpha_k = 0.2$
Figure 4.  The Basis Pursuit Problem, $Q = 10, \beta = 0.08.$
Figure 5.  The Constrained LASSO with $\beta = 0.4,\lambda = 0.1,Q = 190$.
[1]

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

[2]

Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial & Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052

[3]

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 & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057

[4]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283

[5]

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 & Management Optimization, 2018, 13 (5) : 1-17. doi: 10.3934/jimo.2018037

[6]

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 & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[7]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247

[8]

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 & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317

[9]

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems & Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917

[10]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[11]

Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-18. doi: 10.3934/jimo.2018069

[12]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011

[13]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171

[14]

Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743

[15]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129

[16]

Hssaine Boualam, Ahmed Roubi. Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-24. doi: 10.3934/jimo.2018128

[17]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601

[18]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[19]

Xiaoling Sun, Xiaojin Zheng, Juan Sun. A Lagrangian dual and surrogate method for multi-dimensional quadratic knapsack problems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 47-60. doi: 10.3934/jimo.2009.5.47

[20]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (41)
  • HTML views (385)
  • Cited by (0)

Other articles
by authors

[Back to Top]