American Institute of Mathematical Sciences

Advanced
July  2014, 10(3): 743-759. doi: 10.3934/jimo.2014.10.743

Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints

Yuan Shen 1, , Wenxing Zhang 2, and  Bingsheng He 3,

1. 

School of Applied Mathematics, Nanjing University of Finance & Economics, Nanjing, 210023, China
2. 

School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu, 611731, China
3. 

Department of Mathematics, Nanjing University, Nanjing, 210093

Received  February 2012 Revised  December 2012 Published  November 2013

The classical augmented Lagrangian method (ALM) is an efficient method for solving convex optimization with linear constraints. However, the efficiency of ALM, to some extent, is hinged by the computational efforts on solving the resulting subproblems. For the convex optimization with some favorable structures, e.g., either the objective function is separable or the matrices in linear constraints are well-posed, a relaxation to the subproblems of ALM can substantially result in solutions with closed-form. Unfortunately, the relaxation skill can not be extended directly to the generic convex optimization without special structures, particularly for the case of objective function with coupled variables. In this paper, by further relaxing the resulting subproblems of ALM, we propose several novel augmented Lagrangian-based proximal point algorithms. Algorithmically, the next iterate is produced by integrating the predictor, which is obtained in either primal-dual or dual-primal order, with the current iterate. Numerical results demonstrate the promising performances of the proposed algorithms.
Keywords: augmented Lagrangian method, Convex optimization, relaxation., proximal point algorithm.
Mathematics Subject Classification: Primary: 65K05, 90C25; Secondary: 49M29, 90C3.
Citation: Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743
References:
[1]

M. V. Afonso, J. M. Bioucas-Dias and M. A. Figueiredo, An augmented lagrangian approach to the constrained optimization formulation of imaging inverse problems, IEEE Trans. Imag. Process., 20 (2011), 681-695. doi: 10.1109/TIP.2010.2076294.  Google Scholar

[2]

D. P. Bertsekas, Multiplier methods: A survey, Automatica, 12 (1976), 133-145. doi: 10.1016/0005-1098(76)90077-7.  Google Scholar

[3]

D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 1982.  Google Scholar

[4]

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. Learn., 3 (2010), 1-122. doi: 10.1561/2200000016.  Google Scholar

[5]

G. Chen and M. Teboulle, A proximal-based decomposition method for convex minimization problems, Math. Program., 64 (1994), 81-101. doi: 10.1007/BF01582566.  Google Scholar

[6]

J. Eckstein, Some saddle-function splitting methods for convex programming, Optim. Methods Softw., 4 (1994), 75-83. doi: 10.1080/10556789408805578.  Google Scholar

[7]

J. Eckstein and D. P. 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.  Google Scholar

[8]

J. Eckstein and M. Fukushima, Some reformulation and applications of the alternating direction method of multipliers, in Large Scale Optimization: State of the Art (Eds. W. W. Hager, et al.), Kluwer Academic Publishers, 1994, 115-134.  Google Scholar

[9]

E. Esser, Applications of Lagrangian-Based Alternating Direction Methods and Connections to Split Bregman, UCLA CAM Report, 2009, 9-31. Google Scholar

[10]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003. Google Scholar

[11]

X. L. Fu and B. S. He, Self-adaptive projection-based prediction-correction method for constrained variational inequalities, Front. Math. China, 5 (2010), 3-21. doi: 10.1007/s11464-009-0045-1.  Google Scholar

[12]

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

[13]

D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems (eds. M. Fortin and R. Glowinski), 299-331, North-Holland, Amsterdam, 1983. doi: 10.1016/S0168-2024(08)70034-1.  Google Scholar

[14]

R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, 1984.  Google Scholar

[15]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, 1989. doi: 10.1137/1.9781611970838.  Google Scholar

[16]

T. Goldstein and S. Osher, The split bregman method for l1-regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343. doi: 10.1137/080725891.  Google Scholar

[17]

G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, 1996.  Google Scholar

[18]

B. He, L. Liao, D. Han and H. Yang, A new inexact alternating directions method for monotone variational inequalities, Math. Program., 92 (2002), 103-118. doi: 10.1007/s101070100280.  Google Scholar

[19]

B. He, L. Liao and X. Wang, Proximal-like contraction methods for monotone variational inequalities in a unified framework, Comput. Optim. Appl., 51 (2012), 649-679. doi: 10.1007/s10589-010-9372-0.  Google Scholar

[20]

B. He and H. Yang, Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities, Oper. Res. Lett., 23 (1998), 151-161. doi: 10.1016/S0167-6377(98)00044-3.  Google Scholar

[21]

B. He and X. Yuan, On the $\mathcalO(1/t)$ convergence rate of the alternating direction method, SIAM J. Numer. Anal., 50 (2012), 700-709. doi: 10.1137/110836936.  Google Scholar

[22]

M. R. Hestenes, Multiplier and gradient methods, J. Optim. Theory App., 4 (1969), 303-320. doi: 10.1007/BF00927673.  Google Scholar

[23]

Z. Lin, M. Chen, L. Wu and Y. Ma, The augmented lagrange multiplier method for exact recovery of a corrupted low-rank matrices,, preprint, ().   Google Scholar

[24]

A. Nagurney, Network Economics, A Variational Inequality Approach, Kluwer Academics Publishers, London, 1993. doi: 10.1007/978-94-011-2178-1.  Google Scholar

[25]

M. J. D. Powell, A method for nonlinear constraints in minimization problems, in Optimization (ed. R. Fletcher), Academic Press, New York, 1969, 283-298.  Google Scholar

[26]

S. Ramani and J. A. Fessler, Parallel mr image reconstruction using augmented lagrangian methods, IEEE Trans. Medical Imaging, 30 (2011), 694-706. doi: 10.1109/TMI.2010.2093536.  Google Scholar

[27]

R. T. 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.  Google Scholar

[28]

Y. Shen, Partial convolution total variation problem by augmented Lagrangian-based proximal point descent algorithm, submitted to J. Comput. Math., (2013). Google Scholar

[29]

Y. Shen and B. He, New augmented Lagrangian-based proximal point algorithms for constrained optimization,, Submitted to Front. Math. China, ().   Google Scholar

[30]

Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging. Sci., 1 (2008), 248-272. doi: 10.1137/080724265.  Google Scholar

[31]

J. Yang and Y. Zhang, Alternating direction algorithms for $l_1$-problems in compressive sensing, SIAM J. Sci. Comput., 33 (2011), 250-278. doi: 10.1137/090777761.  Google Scholar

[32]

J. Yang, Y. Zhang and W. Yin, An efficient tvl1 algorithm for deblurring multichannel images corrupted by impulsive noise, SIAM J. Sci. Comput., 31 (2009), 2842-2865. doi: 10.1137/080732894.  Google Scholar

[33]

W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), 143-168. doi: 10.1137/070703983.  Google Scholar

show all references

References:
[1]

M. V. Afonso, J. M. Bioucas-Dias and M. A. Figueiredo, An augmented lagrangian approach to the constrained optimization formulation of imaging inverse problems, IEEE Trans. Imag. Process., 20 (2011), 681-695. doi: 10.1109/TIP.2010.2076294.  Google Scholar

[2]

D. P. Bertsekas, Multiplier methods: A survey, Automatica, 12 (1976), 133-145. doi: 10.1016/0005-1098(76)90077-7.  Google Scholar

[3]

D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 1982.  Google Scholar

[4]

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. Learn., 3 (2010), 1-122. doi: 10.1561/2200000016.  Google Scholar

[5]

G. Chen and M. Teboulle, A proximal-based decomposition method for convex minimization problems, Math. Program., 64 (1994), 81-101. doi: 10.1007/BF01582566.  Google Scholar

[6]

J. Eckstein, Some saddle-function splitting methods for convex programming, Optim. Methods Softw., 4 (1994), 75-83. doi: 10.1080/10556789408805578.  Google Scholar

[7]

J. Eckstein and D. P. 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.  Google Scholar

[8]

J. Eckstein and M. Fukushima, Some reformulation and applications of the alternating direction method of multipliers, in Large Scale Optimization: State of the Art (Eds. W. W. Hager, et al.), Kluwer Academic Publishers, 1994, 115-134.  Google Scholar

[9]

E. Esser, Applications of Lagrangian-Based Alternating Direction Methods and Connections to Split Bregman, UCLA CAM Report, 2009, 9-31. Google Scholar

[10]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003. Google Scholar

[11]

X. L. Fu and B. S. He, Self-adaptive projection-based prediction-correction method for constrained variational inequalities, Front. Math. China, 5 (2010), 3-21. doi: 10.1007/s11464-009-0045-1.  Google Scholar

[12]

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

[13]

D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems (eds. M. Fortin and R. Glowinski), 299-331, North-Holland, Amsterdam, 1983. doi: 10.1016/S0168-2024(08)70034-1.  Google Scholar

[14]

R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, 1984.  Google Scholar

[15]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, 1989. doi: 10.1137/1.9781611970838.  Google Scholar

[16]

T. Goldstein and S. Osher, The split bregman method for l1-regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343. doi: 10.1137/080725891.  Google Scholar

[17]

G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, 1996.  Google Scholar

[18]

B. He, L. Liao, D. Han and H. Yang, A new inexact alternating directions method for monotone variational inequalities, Math. Program., 92 (2002), 103-118. doi: 10.1007/s101070100280.  Google Scholar

[19]

B. He, L. Liao and X. Wang, Proximal-like contraction methods for monotone variational inequalities in a unified framework, Comput. Optim. Appl., 51 (2012), 649-679. doi: 10.1007/s10589-010-9372-0.  Google Scholar

[20]

B. He and H. Yang, Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities, Oper. Res. Lett., 23 (1998), 151-161. doi: 10.1016/S0167-6377(98)00044-3.  Google Scholar

[21]

B. He and X. Yuan, On the $\mathcalO(1/t)$ convergence rate of the alternating direction method, SIAM J. Numer. Anal., 50 (2012), 700-709. doi: 10.1137/110836936.  Google Scholar

[22]

M. R. Hestenes, Multiplier and gradient methods, J. Optim. Theory App., 4 (1969), 303-320. doi: 10.1007/BF00927673.  Google Scholar

[23]

Z. Lin, M. Chen, L. Wu and Y. Ma, The augmented lagrange multiplier method for exact recovery of a corrupted low-rank matrices,, preprint, ().   Google Scholar

[24]

A. Nagurney, Network Economics, A Variational Inequality Approach, Kluwer Academics Publishers, London, 1993. doi: 10.1007/978-94-011-2178-1.  Google Scholar

[25]

M. J. D. Powell, A method for nonlinear constraints in minimization problems, in Optimization (ed. R. Fletcher), Academic Press, New York, 1969, 283-298.  Google Scholar

[26]

S. Ramani and J. A. Fessler, Parallel mr image reconstruction using augmented lagrangian methods, IEEE Trans. Medical Imaging, 30 (2011), 694-706. doi: 10.1109/TMI.2010.2093536.  Google Scholar

[27]

R. T. 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.  Google Scholar

[28]

Y. Shen, Partial convolution total variation problem by augmented Lagrangian-based proximal point descent algorithm, submitted to J. Comput. Math., (2013). Google Scholar

[29]

Y. Shen and B. He, New augmented Lagrangian-based proximal point algorithms for constrained optimization,, Submitted to Front. Math. China, ().   Google Scholar

[30]

Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging. Sci., 1 (2008), 248-272. doi: 10.1137/080724265.  Google Scholar

[31]

J. Yang and Y. Zhang, Alternating direction algorithms for $l_1$-problems in compressive sensing, SIAM J. Sci. Comput., 33 (2011), 250-278. doi: 10.1137/090777761.  Google Scholar

[32]

J. Yang, Y. Zhang and W. Yin, An efficient tvl1 algorithm for deblurring multichannel images corrupted by impulsive noise, SIAM J. Sci. Comput., 31 (2009), 2842-2865. doi: 10.1137/080732894.  Google Scholar

[33]

W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), 143-168. doi: 10.1137/070703983.  Google Scholar

[1]

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

Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136
[3]

Tim Hoheisel, Maxime Laborde, Adam Oberman. A regularization interpretation of the proximal point method for weakly convex functions. Journal of Dynamics & Games, 2020, 7 (1) : 79-96. doi: 10.3934/jdg.2020005
[4]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[5]

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

Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027
[7]

Egil Bae, Xue-Cheng Tai, Wei Zhu. Augmented Lagrangian method for an Euler's elastica based segmentation model that promotes convex contours. Inverse Problems & Imaging, 2017, 11 (1) : 1-23. doi: 10.3934/ipi.2017001
[8]

Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157
[9]

Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047
[10]

Ram U. Verma. On the generalized proximal point algorithm with applications to inclusion problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 381-390. doi: 10.3934/jimo.2009.5.381
[11]

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

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

Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495
[14]

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79
[15]

Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053
[16]

Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237
[17]

Wei Zhu, Xue-Cheng Tai, Tony Chan. Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Problems & Imaging, 2013, 7 (4) : 1409-1432. doi: 10.3934/ipi.2013.7.1409
[18]

Fatemeh Bazikar, Saeed Ketabchi, Hossein Moosaei. Smooth augmented lagrangian method for twin bounded support vector machine. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021027
[19]

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

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (62)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences