A flexible ADMM algorithm for big data applications

DOI10.1007/S10915-016-0306-6zbMATH Open1385.49020arXiv1502.04391OpenAlexW2963403579MaRDI QIDQ1704789FDOQ1704789

Authors: Daniel P. Robinson, Rachael Tappenden 

Publication date: 13 March 2018

Published in: Journal of Scientific Computing (Search for Journal in Brave)

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 $ngeq2$ blocks, subject to (non-separable) linear equality constraints. The F-ADMM algorithm uses a 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 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.

Full work available at URL: https://arxiv.org/abs/1502.04391

Recommendations

• Parallel multi-block ADMM with \(o(1/k)\) convergence
• Generalized symmetric ADMM for separable convex optimization
• An inexact accelerated stochastic ADMM for separable convex optimization
• Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives
• Implementing the alternating direction method of multipliers for big datasets: a case study of least absolute shrinkage and selection operator

zbMATH Keywords

regularizationADMMconvex optimizationJacobiGauss-Seidelseparable function

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37) Abstract computational complexity for mathematical programming problems (90C60) Newton-type methods (49M15) Implicit function theorems; global Newton methods on manifolds (58C15)

Cites Work

• Distributed optimization and statistical learning via the alternating direction method of multipliers
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Title not available (Why is that?)
• Variational Analysis
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the global and linear convergence of the generalized alternating direction method of multipliers
• Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
• Convex Analysis
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
• Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs
• Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives
• A note on the alternating direction method of multipliers
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• Block-wise ADMM with a relaxation factor for multiple-block convex programming
• Title not available (Why is that?)
• Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond
• On the Global Linear Convergence of the ADMM with MultiBlock Variables
• Extended monotropic programming and duality
• Augmented \(\ell_1\) and nuclear-norm models with a globally linearly convergent algorithm
• A parallel line search subspace correction method for composite convex optimization

Cited In (8)

• Hybrid MPI/OpenMP parallel asynchronous distributed alternating direction method of multipliers
• First-order algorithms for convex optimization with nonseparable objective and coupled constraints
• Generalized symmetric ADMM for separable convex optimization
• An inexact accelerated stochastic ADMM for separable convex optimization
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• An ADMM algorithm for two-stage stochastic programming problems
• Poisson noise removal based on non-convex hybrid regularizers
• Implementing the alternating direction method of multipliers for big datasets: a case study of least absolute shrinkage and selection operator

This page was built for publication: A flexible ADMM algorithm for big data applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704789)