Optimization Online


Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming

Bingsheng He (hebma***at***nju.edu.cn)
Min Tao (taomin0903***at***gmail.com)
Xiaoming Yuan (xmyuan***at***hkbu.edu.hk)

Abstract: We consider the linearly constrained separable convex programming whose objective function is separable into m individual convex functions without crossed variables. The alternating direction method (ADM) has been well studied in the literature for the special case m=2. But the convergence of extending ADM to the general case m>=3 is still open. In this paper, we show that the straightforward extension of ADM is valid for the general case m>=3 if a Gaussian back substitution procedure is combined. The resulting ADM with Gaussian back substitution is a novel approach towards the extension of ADM from m=2 to m>=3, and its algorithmic framework is new in the literature. For the ADM with Gaussian back substitution, we prove its convergence via the analytic framework of contractive type methods and we show its numerical efficiency by some application problems.

Keywords: Alternating direction method, convex programming, Gaussian elimination, separable structure

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 12/30/2010
Entry Accepted: 12/30/2010
Entry Last Modified: 08/05/2011

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 Optimization Society