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

Yuan Shen; Wenxing Zhang; Bingsheng He

doi:10.3934/jimo.2014.10.743

Article Contents

2014, Volume 10, Issue 3: 743-759. Doi: 10.3934/jimo.2014.10.743

This issue Previous Article Globally convergent homotopy method for designing piecewise linear deterministic contractual function Next Article A hydrothermal problem with non-smooth Lagrangian

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

1.
School of Applied Mathematics, Nanjing University of Finance & Economics, Nanjing, 210023
2.
School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu, 611731
3.
Department of Mathematics, Nanjing University, Nanjing, 210093

Received: January 31, 2012

Revised: November 30, 2012

Published: June 2014

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 65K05, 90C25; Secondary: 49M29, 90C30.

Citation:

Related Papers

Cited by

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.
[2]	D. P. Bertsekas, Multiplier methods: A survey, Automatica, 12 (1976), 133-145.doi: 10.1016/0005-1098(76)90077-7.
[3]	D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 1982.
[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.
[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.
[6]	J. Eckstein, Some saddle-function splitting methods for convex programming, Optim. Methods Softw., 4 (1994), 75-83.doi: 10.1080/10556789408805578.
[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.
[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.
[9]	E. Esser, Applications of Lagrangian-Based Alternating Direction Methods and Connections to Split Bregman, UCLA CAM Report, 2009, 9-31.
[10]	F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003.
[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.
[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.
[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.
[14]	R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, 1984.
[15]	R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, 1989.doi: 10.1137/1.9781611970838.
[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.
[17]	G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, 1996.
[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.
[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.
[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.
[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.
[22]	M. R. Hestenes, Multiplier and gradient methods, J. Optim. Theory App., 4 (1969), 303-320.doi: 10.1007/BF00927673.
[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, arXiv:1009.5055
[24]	A. Nagurney, Network Economics, A Variational Inequality Approach, Kluwer Academics Publishers, London, 1993.doi: 10.1007/978-94-011-2178-1.
[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.
[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.
[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.
[28]	Y. Shen, Partial convolution total variation problem by augmented Lagrangian-based proximal point descent algorithm, submitted to J. Comput. Math., (2013).
[29]	Y. Shen and B. He, New augmented Lagrangian-based proximal point algorithms for constrained optimization, Submitted to Front. Math. China, (2011X).
[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.
[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.
[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.
[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.