# American Institute of Mathematical Sciences

2013, 3(2): 247-260. doi: 10.3934/naco.2013.3.247

## Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming

 1 Department of Mathematics, Nanjing University, Nanjing, 210093 2 Department of Mathematics, Hong Kong Baptist University, Hong Kong

Received  February 2012 Revised  January 2013 Published  April 2013

Recently, we have proposed combining the alternating direction method of multipliers (ADMM) with a Gaussian back substitution procedure for solving the convex minimization model with linear constraints and a general separable objective function, i.e., the objective function is the sum of many functions without coupled variables. In this paper, we further study this topic and show that the decomposed subproblems in the ADMM procedure can be substantially alleviated by linearizing the involved quadratic terms arising from the augmented Lagrangian penalty. When the resolvent operators of the separable functions in the objective have closed-form representations, embedding the linearization into the ADMM subproblems becomes necessary to yield easy subproblems with closed-form solutions. We thus show theoretically that the blend of ADMM, Gaussian back substitution and linearization works effectively for the separable convex minimization model under consideration.
Citation: 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
##### References:
 [1] E. Blum and W. Oettli, "Mathematische Optimierung, Econometrics and Operations Research XX," Springer Verlag, 1975. [2] N. Bose and K. Boo, High-resolution image reconstruction with multisensors, Int. J. Imag. Syst. Tech, 9 (1998), 294-304. doi: 10.1002/(SICI)1098-1098(1998)9:4<294::AID-IMA11>3.0.CO;2-X. [3] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learning, 3 (2010), 1-122. doi: 10.1561/2200000016. [4] R. H. Chan, J. F. Yang and X. M. Yuan, Alternating direction method for image inpainting in wavelet domain, SIAM J. Imaging Sci., 4 (2011), 807-826. doi: 10.1137/100807247. [5] T. F. Chan and R. Glowinski, Finite element approximation and iterative solution of a class of mildly non-linear elliptic equations, Technical report, Stanford University, 1978. [6] C. H. Chen, B. S. He and X. M. Yuan, Matrix completion via alternating direction method, IMA J. Numer. Anal., 32 (2012), 227-245. doi: 10.1093/imanum/drq039. [7] J. Douglas and H. H. Rachford, On the numerical solution of the heat conduction problem in 2 and 3 space variables, Tran. Amer. Math. Soc., 82 (1956), 421-439. doi: 10.1090/S0002-9947-1956-0084194-4. [8] J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal points algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318. doi: 10.1007/BF01581204. [9] E. Esser, Applications of Lagrangian-Based alternating direction methods and connections to split Bregman, UCLA CAM Report 09-31, 2009. [10] M. Fortin and R. Glowinski, "Augmented Lagrangian Methods: Applications to the Numerical Solutions of Boundary Value Problems," Stud. Math. Appl., NorthHolland, Amsterdam, 15 (1983). [11] M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Comput. Optim. Appli., 2 (1992), 93-111. doi: 10.1007/BF00247655. [12] M. Fukushima, The primal Douglas-Rachford splitting algorithm for a class of monotone mappings with application to the traffic equilibrium problem, Math. Program., 72 (1996), 1-15. doi: 10.1007/BF02592328. [13] D. Gabay, Applications of the method of multipliers to variational inequalities, in "Augmented Lagrange Methods: Applications to the Solution of Boundary-valued Problems" (eds. M. Fortin and R. Glowinski), North Holland, Amsterdam, The Netherlands, (1983), 299-331. doi: 10.1016/S0168-2024(08)70034-1. [14] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appli., 2 (1976), 17-40. doi: 10.1016/0898-1221(76)90003-1. [15] R. Glowinski, "Numerical Methods for Nonlinear Variational Problems," Springer-Verlag, New York, Berlin, Heidelberg, Tokyo, 1984. [16] R. Glowinski and A. Marrocco, Approximation par éléments finis d'ordreun et résolution par pénalisation-dualité d'une classe de problèmes non linéaires, R.A.I.R.O., R2 (1975), 41-76. [17] R. Glowinski and P. Le Tallec, "Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics," SIAM Studies in Applied Mathematics, Philadelphia, PA, 1989. doi: 10.1137/1.9781611970838. [18] R. Glowinski, T. Kärkkäinen and K. Majava, On the convergence of operator-splitting methods, in "Numerical Methods for Scienfic computing, Variational Problems and Applications" (eds. Y. Kuznetsov, P. Neittanmaki and O. Pironneau), Barcelona, 2003. [19] B. S. He, L. Z. Liao, D. R. Han and H. Yang, A new inexact alternating directions method for monontone variational inequalities, Math. Program., 92 (2002), 103-118. doi: 10.1007/s101070100280. [20] B. S. He, M. Tao, M. H. Xu and X. M. Yuan, Alternating directions based contraction method for generally separable linearly constrained convex programming problems,, Optimization, (). [21] B. S. He, M. Tao and X. M. Yuan, A splitting method for separable convex programming,, IMA J. Num. Anal., (). [22] B. S. He, M. Tao and X. M. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim., 12 (2012), 313-340. [23] B. S. He, M. H. Xu and X. M. Yuan, Solving large-scale least squares covariance matrix problems by alternating direction methods, SIAM J. Matrix Anal. Appli., 32 (2011), 136-152. [24] B. S. He and X. M. Yuan, On the O(1/n) convergence rate of Douglas-Rachford alternating direction method, SIAM J. Num. Anal., 50 (2012), 700-709. doi: 10.1137/110836936. [25] M. R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appli., 4 (1969), 303-320. [26] P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Num. Anal., 16 (1979), 964-979. [27] B. Martinet, Regularization d'inequations variationelles par approximations sucessives, Revue Francaise d'Informatique et de Recherche Opérationelle, 4 (1970), 154-158. [28] M. K. Ng, P. A. Weiss and X. M. Yuan, Solving constrained total-variation problems via alternating direction methods, SIAM J. Sci. Comput., 32 (2010), 2710-2736. doi: 10.1137/090774823. [29] G. B. Passty, Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Analy. Appli., 72 (1979), 383-390. doi: 10.1016/0022-247X(79)90234-8. [30] M. J. D. Powell, A method for nonlinear constraints in minimization problems, in "Optimization" (eds. R. Fletcher), Academic Press, New York, (1969), 283-298. [31] R. T. Rockafellar, "Convex Analysis," Princeton, NJ, 1970. [32] A. Ruszczyński, Parallel decomposition of multistage stochastic programming problems, Math. Program., 58 (1993), 201-228. [33] S. Setzer, G. Steidl and T. Tebuber, Deblurring Poissonian images by split Bregman techniques, J. Visual Commun. Image Repres., 21 (2010), 193-199. doi: 10.1016/j.jvcir.2009.10.006. [34] J. Sun and S. Zhang, A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, European J. Oper. Res., 207 (2010), 1210-1220. doi: 10.1016/j.ejor.2010.07.020. [35] M. Tao and X. M. Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim., 21 (2011), 57-81. doi: 10.1137/100781894. [36] R. Tibshirani, M. Saunders, S. Rosset, J. Zhu and K. Knight, Sparsity and smoothness via the fused lasso, J. Royal Statist. Soc., 67 (2005), 91-108. doi: 10.1111/j.1467-9868.2005.00490.x. [37] Z. Wen, D. Goldfarb and W. Yin, Alternating direction augmented Lagrangian methods for semideffinite programming, Math. Program. Comput., 2 (2010), 203-230. doi: 10.1007/s12532-010-0017-1. [38] X. M. Yuan, Alternating direction methods for covariance selection models, J. Sci. Comput., 51 (2012), 261-273. doi: 10.1007/s10915-011-9507-1. [39] S. Zhang, J. Ang and J. Sun, An alternating direction method for solving convex nonlinear semidefinite programming problem,, Optimization, (). [40] X. Q. Zhang, M. Burger, X. Bresson and S. Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM J. Imag. Sci., 3 (2010), 253-276. doi: 10.1137/090746379. [41] X. Q. Zhang, M. Burger and S. Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46 (2010), 20-46. doi: 10.1007/s10915-010-9408-8.

show all references

##### References:
 [1] E. Blum and W. Oettli, "Mathematische Optimierung, Econometrics and Operations Research XX," Springer Verlag, 1975. [2] N. Bose and K. Boo, High-resolution image reconstruction with multisensors, Int. J. Imag. Syst. Tech, 9 (1998), 294-304. doi: 10.1002/(SICI)1098-1098(1998)9:4<294::AID-IMA11>3.0.CO;2-X. [3] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learning, 3 (2010), 1-122. doi: 10.1561/2200000016. [4] R. H. Chan, J. F. Yang and X. M. Yuan, Alternating direction method for image inpainting in wavelet domain, SIAM J. Imaging Sci., 4 (2011), 807-826. doi: 10.1137/100807247. [5] T. F. Chan and R. Glowinski, Finite element approximation and iterative solution of a class of mildly non-linear elliptic equations, Technical report, Stanford University, 1978. [6] C. H. Chen, B. S. He and X. M. Yuan, Matrix completion via alternating direction method, IMA J. Numer. Anal., 32 (2012), 227-245. doi: 10.1093/imanum/drq039. [7] J. Douglas and H. H. Rachford, On the numerical solution of the heat conduction problem in 2 and 3 space variables, Tran. Amer. Math. Soc., 82 (1956), 421-439. doi: 10.1090/S0002-9947-1956-0084194-4. [8] J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal points algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318. doi: 10.1007/BF01581204. [9] E. Esser, Applications of Lagrangian-Based alternating direction methods and connections to split Bregman, UCLA CAM Report 09-31, 2009. [10] M. Fortin and R. Glowinski, "Augmented Lagrangian Methods: Applications to the Numerical Solutions of Boundary Value Problems," Stud. Math. Appl., NorthHolland, Amsterdam, 15 (1983). [11] M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Comput. Optim. Appli., 2 (1992), 93-111. doi: 10.1007/BF00247655. [12] M. Fukushima, The primal Douglas-Rachford splitting algorithm for a class of monotone mappings with application to the traffic equilibrium problem, Math. Program., 72 (1996), 1-15. doi: 10.1007/BF02592328. [13] D. Gabay, Applications of the method of multipliers to variational inequalities, in "Augmented Lagrange Methods: Applications to the Solution of Boundary-valued Problems" (eds. M. Fortin and R. Glowinski), North Holland, Amsterdam, The Netherlands, (1983), 299-331. doi: 10.1016/S0168-2024(08)70034-1. [14] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appli., 2 (1976), 17-40. doi: 10.1016/0898-1221(76)90003-1. [15] R. Glowinski, "Numerical Methods for Nonlinear Variational Problems," Springer-Verlag, New York, Berlin, Heidelberg, Tokyo, 1984. [16] R. Glowinski and A. Marrocco, Approximation par éléments finis d'ordreun et résolution par pénalisation-dualité d'une classe de problèmes non linéaires, R.A.I.R.O., R2 (1975), 41-76. [17] R. Glowinski and P. Le Tallec, "Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics," SIAM Studies in Applied Mathematics, Philadelphia, PA, 1989. doi: 10.1137/1.9781611970838. [18] R. Glowinski, T. Kärkkäinen and K. Majava, On the convergence of operator-splitting methods, in "Numerical Methods for Scienfic computing, Variational Problems and Applications" (eds. Y. Kuznetsov, P. Neittanmaki and O. Pironneau), Barcelona, 2003. [19] B. S. He, L. Z. Liao, D. R. Han and H. Yang, A new inexact alternating directions method for monontone variational inequalities, Math. Program., 92 (2002), 103-118. doi: 10.1007/s101070100280. [20] B. S. He, M. Tao, M. H. Xu and X. M. Yuan, Alternating directions based contraction method for generally separable linearly constrained convex programming problems,, Optimization, (). [21] B. S. He, M. Tao and X. M. Yuan, A splitting method for separable convex programming,, IMA J. Num. Anal., (). [22] B. S. He, M. Tao and X. M. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim., 12 (2012), 313-340. [23] B. S. He, M. H. Xu and X. M. Yuan, Solving large-scale least squares covariance matrix problems by alternating direction methods, SIAM J. Matrix Anal. Appli., 32 (2011), 136-152. [24] B. S. He and X. M. Yuan, On the O(1/n) convergence rate of Douglas-Rachford alternating direction method, SIAM J. Num. Anal., 50 (2012), 700-709. doi: 10.1137/110836936. [25] M. R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appli., 4 (1969), 303-320. [26] P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Num. Anal., 16 (1979), 964-979. [27] B. Martinet, Regularization d'inequations variationelles par approximations sucessives, Revue Francaise d'Informatique et de Recherche Opérationelle, 4 (1970), 154-158. [28] M. K. Ng, P. A. Weiss and X. M. Yuan, Solving constrained total-variation problems via alternating direction methods, SIAM J. Sci. Comput., 32 (2010), 2710-2736. doi: 10.1137/090774823. [29] G. B. Passty, Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Analy. Appli., 72 (1979), 383-390. doi: 10.1016/0022-247X(79)90234-8. [30] M. J. D. Powell, A method for nonlinear constraints in minimization problems, in "Optimization" (eds. R. Fletcher), Academic Press, New York, (1969), 283-298. [31] R. T. Rockafellar, "Convex Analysis," Princeton, NJ, 1970. [32] A. Ruszczyński, Parallel decomposition of multistage stochastic programming problems, Math. Program., 58 (1993), 201-228. [33] S. Setzer, G. Steidl and T. Tebuber, Deblurring Poissonian images by split Bregman techniques, J. Visual Commun. Image Repres., 21 (2010), 193-199. doi: 10.1016/j.jvcir.2009.10.006. [34] J. Sun and S. Zhang, A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, European J. Oper. Res., 207 (2010), 1210-1220. doi: 10.1016/j.ejor.2010.07.020. [35] M. Tao and X. M. Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim., 21 (2011), 57-81. doi: 10.1137/100781894. [36] R. Tibshirani, M. Saunders, S. Rosset, J. Zhu and K. Knight, Sparsity and smoothness via the fused lasso, J. Royal Statist. Soc., 67 (2005), 91-108. doi: 10.1111/j.1467-9868.2005.00490.x. [37] Z. Wen, D. Goldfarb and W. Yin, Alternating direction augmented Lagrangian methods for semideffinite programming, Math. Program. Comput., 2 (2010), 203-230. doi: 10.1007/s12532-010-0017-1. [38] X. M. Yuan, Alternating direction methods for covariance selection models, J. Sci. Comput., 51 (2012), 261-273. doi: 10.1007/s10915-011-9507-1. [39] S. Zhang, J. Ang and J. Sun, An alternating direction method for solving convex nonlinear semidefinite programming problem,, Optimization, (). [40] X. Q. Zhang, M. Burger, X. Bresson and S. Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM J. Imag. Sci., 3 (2010), 253-276. doi: 10.1137/090746379. [41] X. Q. Zhang, M. Burger and S. Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46 (2010), 20-46. doi: 10.1007/s10915-010-9408-8.
 [1] 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 [2] 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 [3] 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 [4] 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 [5] 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 [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 and Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859 [7] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial and Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135 [13] Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283 [14] Xin Yang, Nan Wang, Lingling Xu. A parallel Gauss-Seidel method for convex problems with separable structure. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 557-570. doi: 10.3934/naco.2020051 [15] 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 [16] Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349 [17] Wen Deng. Resolvent estimates for a two-dimensional non-self-adjoint operator. Communications on Pure and Applied Analysis, 2013, 12 (1) : 547-596. doi: 10.3934/cpaa.2013.12.547 [18] Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103 [19] Junxiang Li, Yan Gao, Tao Dai, Chunming Ye, Qiang Su, Jiazhen Huo. Substitution secant/finite difference method to large sparse minimax problems. Journal of Industrial and Management Optimization, 2014, 10 (2) : 637-663. doi: 10.3934/jimo.2014.10.637 [20] Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79

Impact Factor: