Optimization Online


On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming

Bingsheng He (hebma***at***nju.edu.cn)
Liusheng Hou (houlsheng***at***gmail.com)
Xiaoming Yuan (xmyuan***at***hkbu.edu.hk)

Abstract: The augmented Lagrangian method (ALM) is a benchmark for solving the convex minimization problem with linear constraints. We consider the special case where the objective is in form of the sum of m functions without coupled variables. For solving this separable convex programming model, it is usually required to decompose the ALM subproblem at each iteration into m smaller subproblems, each of which only involves one function in the original objective. Easier subproblems taking full advantage of the functions'properties individually could thus be generated. In this paper, we focus on the case where full Jacobian decomposition is applied to ALM subproblems, i.e., all the decomposed ALM subproblems are eligible for parallel computation at each iteration. For the first time, we show by an example that ALM with full Jacobian decomposition could be divergent. Hence, to guarantee convergence, certain correction step for correcting the output of ALM with full Jacobian decomposition is a must. Then, we investigate a simple correction scheme in the literature and present a novel analysis to illustrate how to choose refined step sizes for its correction step. A new splitting version of ALM with full Jacobian decomposition is thus proposed. We derive a worst-case O(1/t) convergence rate in both ergodic and nonergodic senses for the new splitting version of ALM with full Jacobian decomposition. Finally, the assignment problem is used to illustrate the efficiency of the new splitting version of ALM with full Jacobian decomposition.

Keywords: Convex programming, augmented Lagrangian method, Jacobian decomposition, contraction methods, convergence rate, operator splitting methods, assignment problem

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 05/28/2013
Entry Accepted: 05/28/2013
Entry Last Modified: 04/05/2014

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