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 & 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).   Google Scholar

[2]

N. Bose and K. Boo, High-resolution image reconstruction with multisensors,, Int. J. Imag. Syst. Tech, 9 (1998), 294.  doi: 10.1002/(SICI)1098-1098(1998)9:4<294::AID-IMA11>3.0.CO;2-X.  Google Scholar

[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.  doi: 10.1561/2200000016.  Google Scholar

[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.  doi: 10.1137/100807247.  Google Scholar

[5]

T. F. Chan and R. Glowinski, Finite element approximation and iterative solution of a class of mildly non-linear elliptic equations,, Technical report, (1978).   Google Scholar

[6]

C. H. Chen, B. S. He and X. M. Yuan, Matrix completion via alternating direction method,, IMA J. Numer. Anal., 32 (2012), 227.  doi: 10.1093/imanum/drq039.  Google Scholar

[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.  doi: 10.1090/S0002-9947-1956-0084194-4.  Google Scholar

[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.  doi: 10.1007/BF01581204.  Google Scholar

[9]

E. Esser, Applications of Lagrangian-Based alternating direction methods and connections to split Bregman,, UCLA CAM Report 09-31, (2009), 09.   Google Scholar

[10]

M. Fortin and R. Glowinski, "Augmented Lagrangian Methods: Applications to the Numerical Solutions of Boundary Value Problems,", Stud. Math. Appl., 15 (1983).   Google Scholar

[11]

M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems,, Comput. Optim. Appli., 2 (1992), 93.  doi: 10.1007/BF00247655.  Google Scholar

[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.  doi: 10.1007/BF02592328.  Google Scholar

[13]

D. Gabay, Applications of the method of multipliers to variational inequalities,, in, (1983), 299.  doi: 10.1016/S0168-2024(08)70034-1.  Google Scholar

[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.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[15]

R. Glowinski, "Numerical Methods for Nonlinear Variational Problems,", Springer-Verlag, (1984).   Google Scholar

[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.   Google Scholar

[17]

R. Glowinski and P. Le Tallec, "Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics,", SIAM Studies in Applied Mathematics, (1989).  doi: 10.1137/1.9781611970838.  Google Scholar

[18]

R. Glowinski, T. Kärkkäinen and K. Majava, On the convergence of operator-splitting methods,, in, (2003).   Google Scholar

[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.  doi: 10.1007/s101070100280.  Google Scholar

[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, ().   Google Scholar

[21]

B. S. He, M. Tao and X. M. Yuan, A splitting method for separable convex programming,, IMA J. Num. Anal., ().   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  doi: 10.1137/110836936.  Google Scholar

[25]

M. R. Hestenes, Multiplier and gradient methods,, J. Optim. Theory Appli., 4 (1969), 303.   Google Scholar

[26]

P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators,, SIAM J. Num. Anal., 16 (1979), 964.   Google Scholar

[27]

B. Martinet, Regularization d'inequations variationelles par approximations sucessives,, Revue Francaise d'Informatique et de Recherche Opérationelle, 4 (1970), 154.   Google Scholar

[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.  doi: 10.1137/090774823.  Google Scholar

[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.  doi: 10.1016/0022-247X(79)90234-8.  Google Scholar

[30]

M. J. D. Powell, A method for nonlinear constraints in minimization problems,, in, (1969), 283.   Google Scholar

[31]

R. T. Rockafellar, "Convex Analysis,", Princeton, (1970).   Google Scholar

[32]

A. Ruszczyński, Parallel decomposition of multistage stochastic programming problems,, Math. Program., 58 (1993), 201.   Google Scholar

[33]

S. Setzer, G. Steidl and T. Tebuber, Deblurring Poissonian images by split Bregman techniques,, J. Visual Commun. Image Repres., 21 (2010), 193.  doi: 10.1016/j.jvcir.2009.10.006.  Google Scholar

[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.  doi: 10.1016/j.ejor.2010.07.020.  Google Scholar

[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.  doi: 10.1137/100781894.  Google Scholar

[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.  doi: 10.1111/j.1467-9868.2005.00490.x.  Google Scholar

[37]

Z. Wen, D. Goldfarb and W. Yin, Alternating direction augmented Lagrangian methods for semideffinite programming,, Math. Program. Comput., 2 (2010), 203.  doi: 10.1007/s12532-010-0017-1.  Google Scholar

[38]

X. M. Yuan, Alternating direction methods for covariance selection models,, J. Sci. Comput., 51 (2012), 261.  doi: 10.1007/s10915-011-9507-1.  Google Scholar

[39]

S. Zhang, J. Ang and J. Sun, An alternating direction method for solving convex nonlinear semidefinite programming problem,, Optimization, ().   Google Scholar

[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.  doi: 10.1137/090746379.  Google Scholar

[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.  doi: 10.1007/s10915-010-9408-8.  Google Scholar

show all references

References:
[1]

E. Blum and W. Oettli, "Mathematische Optimierung, Econometrics and Operations Research XX,", Springer Verlag, (1975).   Google Scholar

[2]

N. Bose and K. Boo, High-resolution image reconstruction with multisensors,, Int. J. Imag. Syst. Tech, 9 (1998), 294.  doi: 10.1002/(SICI)1098-1098(1998)9:4<294::AID-IMA11>3.0.CO;2-X.  Google Scholar

[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.  doi: 10.1561/2200000016.  Google Scholar

[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.  doi: 10.1137/100807247.  Google Scholar

[5]

T. F. Chan and R. Glowinski, Finite element approximation and iterative solution of a class of mildly non-linear elliptic equations,, Technical report, (1978).   Google Scholar

[6]

C. H. Chen, B. S. He and X. M. Yuan, Matrix completion via alternating direction method,, IMA J. Numer. Anal., 32 (2012), 227.  doi: 10.1093/imanum/drq039.  Google Scholar

[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.  doi: 10.1090/S0002-9947-1956-0084194-4.  Google Scholar

[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.  doi: 10.1007/BF01581204.  Google Scholar

[9]

E. Esser, Applications of Lagrangian-Based alternating direction methods and connections to split Bregman,, UCLA CAM Report 09-31, (2009), 09.   Google Scholar

[10]

M. Fortin and R. Glowinski, "Augmented Lagrangian Methods: Applications to the Numerical Solutions of Boundary Value Problems,", Stud. Math. Appl., 15 (1983).   Google Scholar

[11]

M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems,, Comput. Optim. Appli., 2 (1992), 93.  doi: 10.1007/BF00247655.  Google Scholar

[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.  doi: 10.1007/BF02592328.  Google Scholar

[13]

D. Gabay, Applications of the method of multipliers to variational inequalities,, in, (1983), 299.  doi: 10.1016/S0168-2024(08)70034-1.  Google Scholar

[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.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[15]

R. Glowinski, "Numerical Methods for Nonlinear Variational Problems,", Springer-Verlag, (1984).   Google Scholar

[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.   Google Scholar

[17]

R. Glowinski and P. Le Tallec, "Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics,", SIAM Studies in Applied Mathematics, (1989).  doi: 10.1137/1.9781611970838.  Google Scholar

[18]

R. Glowinski, T. Kärkkäinen and K. Majava, On the convergence of operator-splitting methods,, in, (2003).   Google Scholar

[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.  doi: 10.1007/s101070100280.  Google Scholar

[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, ().   Google Scholar

[21]

B. S. He, M. Tao and X. M. Yuan, A splitting method for separable convex programming,, IMA J. Num. Anal., ().   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  doi: 10.1137/110836936.  Google Scholar

[25]

M. R. Hestenes, Multiplier and gradient methods,, J. Optim. Theory Appli., 4 (1969), 303.   Google Scholar

[26]

P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators,, SIAM J. Num. Anal., 16 (1979), 964.   Google Scholar

[27]

B. Martinet, Regularization d'inequations variationelles par approximations sucessives,, Revue Francaise d'Informatique et de Recherche Opérationelle, 4 (1970), 154.   Google Scholar

[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.  doi: 10.1137/090774823.  Google Scholar

[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.  doi: 10.1016/0022-247X(79)90234-8.  Google Scholar

[30]

M. J. D. Powell, A method for nonlinear constraints in minimization problems,, in, (1969), 283.   Google Scholar

[31]

R. T. Rockafellar, "Convex Analysis,", Princeton, (1970).   Google Scholar

[32]

A. Ruszczyński, Parallel decomposition of multistage stochastic programming problems,, Math. Program., 58 (1993), 201.   Google Scholar

[33]

S. Setzer, G. Steidl and T. Tebuber, Deblurring Poissonian images by split Bregman techniques,, J. Visual Commun. Image Repres., 21 (2010), 193.  doi: 10.1016/j.jvcir.2009.10.006.  Google Scholar

[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.  doi: 10.1016/j.ejor.2010.07.020.  Google Scholar

[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.  doi: 10.1137/100781894.  Google Scholar

[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.  doi: 10.1111/j.1467-9868.2005.00490.x.  Google Scholar

[37]

Z. Wen, D. Goldfarb and W. Yin, Alternating direction augmented Lagrangian methods for semideffinite programming,, Math. Program. Comput., 2 (2010), 203.  doi: 10.1007/s12532-010-0017-1.  Google Scholar

[38]

X. M. Yuan, Alternating direction methods for covariance selection models,, J. Sci. Comput., 51 (2012), 261.  doi: 10.1007/s10915-011-9507-1.  Google Scholar

[39]

S. Zhang, J. Ang and J. Sun, An alternating direction method for solving convex nonlinear semidefinite programming problem,, Optimization, ().   Google Scholar

[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.  doi: 10.1137/090746379.  Google Scholar

[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.  doi: 10.1007/s10915-010-9408-8.  Google Scholar

[1]

Honglei Lang, Yunhe Sheng. Linearization of the higher analogue of Courant algebroids. Journal of Geometric Mechanics, 2020, 12 (4) : 585-606. doi: 10.3934/jgm.2020025

[2]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[3]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[4]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[5]

Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436

[6]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[7]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[8]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[9]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[10]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[11]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[12]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[13]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[14]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

[15]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

[16]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[17]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[18]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[19]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

 Impact Factor: 

Metrics

  • PDF downloads (42)
  • HTML views (0)
  • Cited by (15)

Other articles
by authors

[Back to Top]