Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author

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

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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] 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.
  • 加载中



Article Metrics

HTML views(2345) PDF downloads(511) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint