• Previous Article
    Selection of DRX scheme for voice traffic in LTE-A networks: Markov modeling and performance analysis
  • JIMO Home
  • This Issue
  • Next Article
    Three concepts of robust efficiency for uncertain multiobjective optimization problems via set order relations
April  2019, 15(2): 723-737. 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  April 2019 Early access  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 and Management Optimization, 2019, 15 (2) : 723-737. 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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021028

[12]

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

[13]

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

[14]

Yanfei You, Suhong Jiang. Improved Lagrangian-PPA based prediction correction method for linearly constrained convex optimization. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021174

[15]

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

[16]

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

[17]

Yan Gu, Nobuo Yamashita. A proximal ADMM with the Broyden family for convex optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2715-2732. doi: 10.3934/jimo.2020091

[18]

Fan Jiang, Zhongming Wu, Xingju Cai. Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. Journal of Industrial and Management Optimization, 2020, 16 (2) : 835-856. doi: 10.3934/jimo.2018181

[19]

Yuan Shen, Chang Liu, Yannian Zuo, Xingying Zhang. A modified self-adaptive dual ascent method with relaxed stepsize condition for linearly constrained quadratic convex optimization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022101

[20]

Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial and Management Optimization, 2019, 15 (2) : 757-774. doi: 10.3934/jimo.2018069

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (476)
  • HTML views (1787)
  • Cited by (0)

Other articles
by authors

[Back to Top]