Please wait a minute...
Frontiers of Mathematics in China

ISSN 1673-3452

ISSN 1673-3576(Online)

CN 11-5739/O1

Postal Subscription Code 80-964

2018 Impact Factor: 0.565

Front Math Chin    0, Vol. Issue () : 79-114    https://doi.org/10.1007/s11464-010-0092-7
RESEARCH ARTICLE
Proximal alternating direction-based contraction methods for separable linearly constrained convex optimization
Bingsheng HE1,2(), Zheng PENG3, Xiangfeng WANG1
1. Department of Mathematics, Nanjing University, Nanjing 210093, China; 2. National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China; 3. Department of Mathematics, Fuzhou University, Fuzhou 350108, China
 Download: PDF(371 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): HE Bingsheng,Email:hebma@nju.edu.cn   
Issue Date: 01 February 2011
 Cite this article:   
Bingsheng HE,Zheng PENG,Xiangfeng WANG. Proximal alternating direction-based contraction methods for separable linearly constrained convex optimization[J]. Front Math Chin, 0, (): 79-114.
 URL:  
https://academic.hep.com.cn/fmc/EN/10.1007/s11464-010-0092-7
https://academic.hep.com.cn/fmc/EN/Y0/V/I/79
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
doi: 10.1007/BF01582566
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
doi: 10.1109/JSTSP.2007.910264
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
doi: 10.1002/cpa.20042
8 Eckstein J. Some saddle-function splitting methods for convex programming. Optimization Methods and Software , 1994, 4: 75-83
doi: 10.1080/10556789408805578
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
doi: 10.1016/0898-1221(76)90003-1
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
doi: 10.1137/080725891
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
doi: 10.1007/s101070100280
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
doi: 10.1016/S0167-6377(98)00044-3
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
doi: 10.1023/B:COAP.0000013058.17185.90
25 Kontogiorgis S, Meyer R R. A variable-penalty alternating directions method for convex optimization. Mathematical Programming , 1998, 83: 29-53
doi: 10.1007/BF02680549
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
doi: 10.1137/0314056
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
doi: 10.1007/BF00933339
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 l1-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
doi: 10.1080/10556780600552693
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)
[1] Ke GUO, Deren HAN, David Z. W. WANG, Tingting WU. Convergence of ADMM for multi-block nonconvex separable optimization models[J]. Front. Math. China, 2017, 12(5): 1139-1162.
[2] Yangyang XU, Wotao YIN, Zaiwen WEN, Yin ZHANG. An alternating direction algorithm for matrix completion with nonnegative factors[J]. Front Math Chin, 2012, 7(2): 365-384.
[3] LI Min, HE Bingsheng. Prediction-correction alternating direction method for a class of constrained min-max problems[J]. Front. Math. China, 2007, 2(1): 103-121.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed