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.

Key words： Alternating direction method; separable structure; contraction method; linearly constrained convex programming

References

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

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

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

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

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. Some reformulation and applications of the alternating direction method of multipliers. In: Hager W W, Hearn D W, Pardalos P M, eds. Large Scale Optimization: State of the Art. Dordrecht: Kluwer Academic Publishers, 1994, 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. Berlin: Springer-Verlag, 2003

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. New York, Berlin, Heidelberg, Tokyo: Springer-Verlag, 1984

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

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 MJ. 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/DB FILE/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/DB FILE/2009/10/ 2434.pdf

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

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 ILE/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)