-

 

 

 




Optimization Online





 

A Flexible ADMM Algorithm for Big Data Applications

Daniel Robinson(daniel.p.robinson***at***jhu.edu)
Rachael Tappenden(rtappen1***at***jhu.edu)

Abstract: We present a flexible Alternating Direction Method of Multipliers (F-ADMM) algorithm for solving optimization problems involving a strongly convex objective function that is separable into $n \geq 2$ blocks, subject to (non-separable) linear equality constraints. The F-ADMM algorithm uses a \emph{Gauss-Seidel} scheme to update blocks of variables, and a regularization term is added to each of the subproblems arising within F-ADMM. We prove, under common assumptions, that F-ADMM is globally convergent. We also present a special case of F-ADMM that is \emph{partially parallelizable}, which makes it attractive in a big data setting. In particular, we partition the data into groups, so that each group consists of multiple blocks of variables. By applying F-ADMM to this partitioning of the data, and using a specific regularization matrix, we obtain a hybrid ADMM (H-ADMM) algorithm: the grouped data is updated in a Gauss-Seidel fashion, and the blocks within each group are updated in a Jacobi manner. Convergence of H-ADMM follows directly from the convergence properties of F-ADMM. Also, a special case of H-ADMM can be applied to functions that are convex, rather than strongly convex. We present numerical experiments to demonstrate the practical advantages of this algorithm.

Keywords: Alternating Direction Method of Multipliers; convex optimization; Gauss-Seidel; Jacobi; regularization; separable function

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation:

Download: [PDF]

Entry Submitted: 03/23/2015
Entry Accepted: 03/23/2015
Entry Last Modified: 03/23/2015

Modify/Update this entry


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

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society