Proximal alternating direction-based contraction methods for separable linearly constrained convex optimization

Abstract

Alternating direction method (ADM) has been well studied in the context of linearly constrained convex programming problems. Recently, because of its significant efficiency and easy implementation in novel applications, ADM is extended to the case where the number of separable parts is a finite number. The algorithmic framework of the extended method consists of two phases. At each iteration, it first produces a trial point by using the usual alternating direction scheme, and then the next iterate is updated by using a distance-descent direction offered by the trial point. The generated sequence approaches the solution set monotonically in the Fejér sense, and the method is called alternating direction-based contraction (ADBC) method. In this paper, in order to simplify the subproblems in the first phase, we add a proximal term to the objective function of the minimization subproblems. The resulted algorithm is called proximal alternating direction-based contraction (PADBC) methods. In addition, we present different linearized versions of the PADBC methods which substantially broaden the applicable scope of the ADBC method. All the presented algorithms are guided by a general framework of the contraction methods for monotone variational inequalities, and thus, the convergence follows directly.

Keywords

Alternating direction method / separable structure / contraction method / linearly constrained convex programming

References

[1] Bertsekas D. P. Constrained Optimization and Lagrange Multiplier Methods, 1982, New York: Academic Press.

[2] Bertsekas D. P., Tsitsiklis J. N. Parallel and Distributed Computation, Numerical Methods, 1989, Englewood Cliffs: Prentice-Hall.

[3] Blum E., Oettli W. Mathematische Optimierung. Econometrics and Operations Research XX, 1975, Berlin: Springer-Verlag.

[4] Brézis H. Opérateurs Miximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert, 1973, Amsterdam: North-Holland.

[5] Chen G., Teboulle M. A proximal-based decomposition method for convex minimization problems. Mathematical Programming, 1994, 64, 81-101

[6] Combettes P. L., Pesquet J. -C. A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE J Selected Topics Signal Process, 2009, 1, 564-574

[7] Daubechies I., Defrise M., De Mol C. An iterative threshilding algorithm for linear inverse problems with a sparsity constraint. Comm Pure and Appl Math, 2004, 57 11 1413-1457

[8] Eckstein J. Some saddle-function splitting methods for convex programming. Optimization Methods and Software, 1994, 4, 75-83

[9] Eckstein J., Fukushima M. Hager W. W., Hearn D. W., Pardalos P. M. Some reformulation and applications of the alternating direction method of multipliers. Large Scale Optimization: State of the Art, 1994, Dordrecht: Kluwer Academic Publishers 115-134

[10] Esser E. Applications of Lagrangian-Based alternating direction methods and connections to split Bregman. UCLA CAM Report 09-31, 2009

[11] Facchinei F., Pang J. -S. Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. I. Springer Series in Operations Research, 2003, Berlin: Springer-Verlag.

[12] Fukushima M. Application of the alternating direction method of multipliers to separable convex programming problems. Computational Optimization and Applications, 1992, 2, 93-111

[13] Gabay D., Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite-element approximations. Computer and Mathematics with Applications, 1976, 2, 17-40

[14] Glowinski R. Numerical Methods for Nonlinear Variational Problems, 1984, New York, Berlin, Heidelberg, Tokyo: Springer-Verlag.

[15] Glowinski R., Le Tallec P. Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, 1989, Philadelphia: SIAM.

[16] Goldstein T., Osher S. The split Bregman algorithm for L1 regularized problems. SIAM J Imag Science, 2009, 2 2 323-343

[17] He B. S. A class of projection and contraction methods for monotone variational inequalities. Appl Math Optim, 1997, 35, 69-76

[18] He B. S., Liao L. Z., Han D., Yang H. A new inexact alternating directions method for monotone variational inequalities. Mathematical Programming, 2002, 92, 103-118

[19] He B. S., Liao L. Z., Qian M.J. Alternating projection based prediction-correction methods for structured variational inequalities. Journal of Computational Mathematics, 2006, 24, 693-710

[20] He B S, Tao M, Xu M H, Yuan X M. Alternating directions based contraction method for generally separable linearly constrained convex programming problems. Optimization Online, http://www.optimization-online.org/DBFILE/2009/11/2465.pdf

[21] He B. S., Xu M. H. A general framework of contraction methods for monotone variational inequalities. Pacific J Optimization, 2008, 4, 195-212

[22] He B S, Xu M H, Yuan X M. Solving large-scale least squares covariance matrix problems by alternating direction methods. Preprint

[23] He B. S., Yang H. Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities. Operations Research Letters, 1998, 23, 151-161

[24] He B. S., Yuan X. M., Zhang J. Z. Comparison of two kinds of prediction-correction methods for monotone variational inequalities. Comput Optim Appl, 2004, 27, 247-267

[25] Kontogiorgis S., Meyer R. R. A variable-penalty alternating directions method for convex optimization. Mathematical Programming, 1998, 83, 29-53

[26] Martinet B. Regularization d’inequations variationelles par approximations sucessives. Revue Francaise d’Informatique et de Recherche Opérationelle, 1970, 4, 154-159

[27] Ng M, Weiss P A, Yuan X M. Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods. ICM Research Report, 2009; Optimization Online, http://www.optimization-online.org/DBFILE/2009/10/2434.pdf

[28] Nocedal J., Wright S. J. Numerical Optimization, 2006, 2nd ed., Berlin: Springer-Verlag.

[29] Rockafellar R. T. Monotone operators and the proximal point algorithm. SIAM J Contr Optim, 1976, 14, 877-898

[30] Stephanopoulos G., Westerberg A. W. The use of Hestenes’ method of multipliers to resolve dual gaps in engineering system optimization. Journal of Optimization Theory and Applications, 1975, 15, 285-309

[31] Sun J, Zhang S. A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs. European Journal of Operational Research (to appear)

[32] Wen Z, Goldfarb D, Yin W. Alternating direction augmented Lagrangian methods for semidefinite programming. Mathematical Programming Computation (to appear)

[33] Yang J, Zhang Y. Alternating direction algorithms for l ₁-problems in compressive sensing. TR09-37, CAAM, Rice University, 2009

[34] Ye C. H., Yuan X. M. A descent method for structured monotone variational inequalities. Optimization Methods and Software, 2007, 22, 329-338

[35] Yuan X M. Alternating direction methods for sparse covariance selection. Optimizaton Online, http://www.optimization-online.org/DB_FILE/2009/09/2390.pdf

[36] Yuan X M, Yang J. Sparse and low rank sparse matrix decomposition via alternating directions method. Optimization Online, http://www.optimization-online.org/DB_FILE/2009/11/2447.pdf

[37] Zhang X, Burger M, Osher S. A unified proximal-dual algorithm framework based on Bregman iteration. SIAM J Imag Science (to appear)

[38] Zhang X, Burger M, Bresson X, Osher S. Bregmanized nonlocal regularization for deconvolution and sparse reconstruction. SIAM J Imag Science (to appear)