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

Foxiang Liu; Lingling Xu; Yuehong Sun; Deren Han

doi:10.3934/jimo.2018067

Article Contents

2019, Volume 15, Issue 2: 723-737. Doi: 10.3934/jimo.2018067

This issue Previous Article Three concepts of robust efficiency for uncertain multiobjective optimization problems via set order relations Next Article Selection of DRX scheme for voice traffic in LTE-A networks: Markov modeling and performance analysis

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
* Corresponding author

Received: July 31, 2016

Revised: November 30, 2017

Early access: June 2018

Published: January 2019

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

Abstract Full Text(HTML) Figure(5) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C25, 65K25; Secondary: 58E35.

Citation:

Full Text(HTML)

Figure 1. Convergence precision of all algorithms, the error is given by $\|Ax-b\|.$.

Download: Full-size image PowerPoint slide

Figure 2. Solve GNEP with self-adaptive stepsize

Download: Full-size image PowerPoint slide

Figure 3. Solve GNEP with fixed stepsize $\alpha_k = 0.2$

Download: Full-size image PowerPoint slide

Figure 4. The Basis Pursuit Problem, $Q = 10, \beta = 0.08.$

Download: Full-size image PowerPoint slide

Figure 5. The Constrained LASSO with $\beta = 0.4,\lambda = 0.1,Q = 190$.

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	A. Agarwal, S. 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. Boyd, N. Parikh, E. Chu, B. 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. Cai, D. 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. Chen, B. He, X. 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. Chen, M. Li, X. 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. Cui, X. Li, D. 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. Feng, H. 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. Han, X. 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. Han, X. Yuan, W. 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. He, H. Yang, Q. 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. He, M. 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. He, M. 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. He, L. 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. Hong, Z. 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. Li, D. 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. Lin, S. 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. Mota, J. M. Xavier, P. 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. Peng, A. Ganesh, J. Wright, W. 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. Sun, K. 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.