×

The augmented Lagrangian method with full Jacobian decomposition and logarithmic-quadratic proximal regularization for multiple-block separable convex programming. (English) Zbl 1418.90197

Summary: We consider a separable convex minimization model whose variables are coupled by linear constraints and they are subject to the positive orthant constraints, and its objective function is in form of \(m\) functions without coupled variables. It is well recognized that when the augmented Lagrangian method (ALM) is applied to solve some concrete applications, the resulting subproblem at each iteration should be decomposed to generate solvable subproblems. When the Gauss-Seidel decomposition is implemented, this idea has inspired the alternating direction method of multiplier (for \(m=2\)) and its variants (for \(m\geq 3\)). When the Jacobian decomposition is considered, it has been shown that the ALM with Jacobian decomposition in its subproblem is not necessarily convergent even when \(m=2\) and it was suggested to regularize the decomposed subproblems with quadratic proximal terms to ensure the convergence. In this paper, we focus on the multiple-block case with \(m\geq 3\). We consider implementing the full Jacobian decomposition to ALM’s subproblems and using the logarithmic-quadratic proximal (LQP) terms to regularize the decomposed subproblems. The resulting subproblems are all unconstrained minimization problems because the positive orthant constraints are all inactive; and they are fully eligible for parallel computation. Accordingly, the ALM with full Jacobian decomposition and LQP regularization is proposed. We also consider its inexact version which allows the subproblems to be solved inexactly. For both the exact and inexact versions, we comprehensively discuss their convergence, including their global convergence, worst-case convergence rates measured by the iteration-complexity in both the ergodic and nonergodic senses, and linear convergence rates under additional assumptions. Some preliminary numerical results are reported to demonstrate the efficiency of the ALM with full Jacobian decomposition and LQP regularization.

MSC:

90C25 Convex programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods

Software:

UNLocBoX
PDFBibTeX XMLCite
Full Text: DOI Numdam

References:

[1] A. Auslender & M. Teboulle, “Entropic proximal decomposition methods for convex programs and variational inequalities”, Math. Program.91 (2001), p. 33-47 · Zbl 1051.90017
[2] A. Auslender & M. Teboulle, “Interior projection-like methods for monotone variational inequalities”, Math. Program.104 (2005), p. 39-68 · Zbl 1159.90517
[3] A. Auslender, M. Teboulle & S. Ben-Tiba, “A logarithmic-quadratic proximal method for variational inequalities”, Comput. Optim. Appl.12 (1999), p. 31-40 · Zbl 1039.90529
[4] D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, 1982 · Zbl 0572.90067
[5] S. Boyd, N. Parikh, E. Chu, B. Peleato & J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers”, Foundations and Trends in Machine Learning3 (2010), p. 1-122 · Zbl 1229.90122
[6] C. H. Chen, B. S. He, Ye Y. Y. & X. M. Yuan, “The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent”, Math. Program., Ser A155 (2016), p. 57-79 · Zbl 1332.90193
[7] C. H. Chen, M. Li & X. M. Yuan, “Further study on the convergence rate of alternating direction method of multipliers with logarithmic-quadratic proximal regularization”, J. Optim. Theory Appli.166 (2015), p. 906-929 · Zbl 1327.90199
[8] P. L. Combettes & J. C. Pesquet, Proximal splitting methods in signal processing, in H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, H. Wolkowicz, ed., Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, 2011, p. 185-212 · Zbl 1242.90160
[9] D. Davis & W. T. Yin, Convergence rate analysis of several splitting schemes, in R. Glowinski, S. J. Osher, W. T. Yin, ed., Splitting Methods in Communication, Imaging, Science, and Engineering, Springer, 2017, p. 115-163 · Zbl 1372.65168
[10] W. Deng, M. J. Lai, Z. M. Peng & W. T. Yin, “Parallel multi-block ADMM with o(1/k) convergence”, J. Sci. Comput.71 (2017), p. 712-736 · Zbl 1398.65121
[11] B. C. Eaves, “On the basic theorem of complementarity”, Math. Program.1 (1971), p. 68-75 · Zbl 0227.90044
[12] J. Eckstein & D. P. Bertsekas, “On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators”, Math. Program.55 (1992), p. 293-318 · Zbl 0765.90073
[13] J. Eckstein & W. Yao, “Augmented Lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results”, RUTCOR Research Report RRR 32-2012, 2012
[14] F. Facchinei & J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems. Vol. I. Springer Series in Operations Research, Springer-Verlag, New York, 2003 · Zbl 1062.90002
[15] R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, Berlin, Heidelberg, Tokyo, 1984 · Zbl 0536.65054
[16] R. Glowinski, On alternating direction methods of multipliers: A historical perspective, Modeling, Simulation and Optimization for Science and Technology, Volume 34 of the series Computational Methods in Applied Sciences, Springer, 2014, p. 59-82 · Zbl 1320.65098
[17] R. Glowinski & A. Marrocco, “Approximation par éléments finis d’ordre un et résolution par pénalisation-dualité d’une classe de problèmes non linéaires”, R.A.I.R.O.R2 (1975), p. 41-76 · Zbl 0368.65053
[18] R. Glowinski & P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM Studies in Applied Mathematics, Philadelphia, PA, 1989 · Zbl 0698.73001
[19] E. G. Gol’shtein & N. V. Tret’yakov, “Modified Lagrangian in convex programming and their generalizations”, Math. Program. Studies10 (1979), p. 86-97 · Zbl 0404.90069
[20] D. R. Han, X. M. Yuan & W. X. Zhang, “An augmented-Lagrangian-based parallel splitting method for separable convex programming with applications to image processing”, Math. Comput.83 (2014), p. 2263-2291 · Zbl 1311.90100
[21] P. C. Hansen, J. G. Nagy & D. P. O’Leary, Deblurring Images: Matrices, Spectra, and Filtering, SIAM, Philadelphia, 2006 · Zbl 1112.68127
[22] B. S. He, L. S. Hou & X. M. Yuan, “On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming”, SIAM J. Optim.25 (2015), p. 2274-2312 · Zbl 1327.90209
[23] B. S. He, H. Liu, Wang Z. R. & X. M. Yuan, “A strictly contractive Peaceman-Rachford splitting method for convex programming”, SIAM J. Optim.24 (2014), p. 1101-1140 · Zbl 1327.90210
[24] B. S. He, M. Tao & X. M. Yuan, “Alternating direction method with Gaussian back substitution for separable convex programming”, SIAM J. Optim.22 (2012), p. 313-340 · Zbl 1273.90152
[25] B. S. He, H. K. Xu & X. M. Yuan, “On the proximal Jacobian decomposition of ALM for multiple-block separable convex minimization problems and its relationship to ADMM”, J. Sci. Comput.66 (2016), p. 1204-1217 · Zbl 1371.65052
[26] B. S. He & X. M. Yuan, “On the O(1/n) convergence rate of Douglas-Rachford alternating direction method”, SIAM J. Numer. Anal.50 (2012), p. 700-709 · Zbl 1245.90084
[27] B. S. He & X. M. Yuan, “On nonergodic convergence rate of Douglas-Rachford alternating direction method of multipliers”, Numer. Math.130 (2015), p. 567-577 · Zbl 1320.90060
[28] M. Hong & Z. Q. Luo, “On the linear convergence of the alternating direction method of multipliers”, Math. Program.162 (2017), p. 165-199 · Zbl 1362.90313
[29] M. Li, L.-Z. Liao & X. M. Yuan, “Inexact alternating direction method of multipliers with logarithmic-quadratic proximal regularization”, J. Optim. Theory Appli.159 (2013), p. 412-436 · Zbl 1282.90197
[30] M. Li, D. F. Sun & K.-C. Toh, “A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization”, SIAM J. Optim.26 (2016), p. 922-950 · Zbl 1338.90305
[31] M. Li & X. M. Yuan, “A strictly contractive Peaceman-Rachford splitting method with logarithmic-quadratic proximal regularization for convex programming”, Math. Oper. Res.40 (2015), p. 842-858 · Zbl 1329.90106
[32] T. Y. Lin, S. Q. Ma & S. Z. Zhang, “On the global linear convergence of the ADMM with multiblock variables”, SIAM J. Optim.25 (2015), p. 1478-1497 · Zbl 1333.90095
[33] T. Y. Lin, S. Q. Ma & S. Z. Zhang, “On the sublinear convergence rate of multi-block ADMM”, J. Oper. Res. Soc. China3 (2015), p. 251-274 · Zbl 1323.90052
[34] B. Martinet, “Regularization d’inequations variationelles par approximations successives”, Revue Francaise d’Informatique et de Recherche Opérationelle4 (1970), p. 154-159 · Zbl 0215.21103
[35] J. G. Melo & R. D. C. Monteiro, “Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs”, arXiv:1705.07229v1, 2017
[36] A. S. Nemirovsky & D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, New York, 1983
[37] Y. E. Nesterov, “A method for unconstrained convex minimization problem with the rate of convergence O(1/k2)”, Doklady AN SSSR269 (1983), p. 543-547
[38] Y. E. Nesterov, “Gradient methods for minimizing composite objective function”, Math. Program., Ser. B140 (2013), p. 125-161 · Zbl 1287.90067
[39] M. Patriksson, “A survey on the continuous nonlinear resource allocation problem”, European J. Oper. Res.185 (2008), p. 1-46 · Zbl 1146.90493
[40] Y. G. Peng, A. Ganesh, J. Wright, W. L. Xu & Y. Ma, “Robust alignment by sparse and low-rank decomposition for linearly correlated images”, IEEE Tran. Pattern Anal. Mach. Intel.34 (2012), p. 2233-2246
[41] M. J. D. Powell, A method for nonlinear constraints in minimization problems, in R. Fletcher, ed., Optimization, Academic Press, New York, 1969, p. 283-298
[42] R. T. Rockafellar, “Augmented Lagrangians and applications of the proximal point algorithm in convex programming”, Math. Oper. Res.1 (1976), p. 97-116 · Zbl 0402.90076
[43] M. Tao & X. M. Yuan, “Recovering low-rank and sparse components of matrices from incomplete and noisy observations”, SIAM J. Optim.21 (2011), p. 57-81 · Zbl 1218.90115
[44] M. Tao & X. M. Yuan, “On the O(1/t) convergence rate of alternating direction method with logarithmic-quadratic proximal regularization”, SIAM J. Optim.22 (2012), p. 1431-1448 · Zbl 1263.90103
[45] H. Uzawa, “Market mechanisms and mathematical programming”, Econometrica28 (1960), p. 872-881 · Zbl 0098.33602
[46] X. M. Yuan & M. Li, “An LQP-based decomposition method for solving a class of variational inequalities”, SIAM J. Optim21 (2011), p. 1309-1318 · Zbl 1241.65063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.