Optimization Online


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

He Bingsheng(hebma***at***nju.edu.cn)
Peng Zheng(pzheng008***at***gmail.com)
Wang XiangFeng(xfwang.nju***at***gmail.com)

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. On each iteration it first produces a trial point by using the usual alternating direction scheme. 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$\acute{e}$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 resultant 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 straightforwardly.

Keywords: alternating direction method, linearly constrained convex programming, separable structure, contraction method

Category 1: Complementarity and Variational Inequalities

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 05/25/2010
Entry Accepted: 05/25/2010
Entry Last Modified: 05/25/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society