alternating direction method of multipliers – Page 7

Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions

Published: 2014/07/19, Updated: 2015/04/30

Convex Optimization alternating direction method of multipliers, averaged operator, douglas-rachford splitting, fixed point algorithm, nonexpansive operator, peaceman-rachford splitting

Splitting schemes are a class of powerful algorithms that solve complicated monotone inclusion and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which the simple pieces of the decomposition are processed individually. This leads to easily implementable and highly parallelizable algorithms, which often obtain nearly state-of-the-art performance. … Read more

Convergence rate analysis of several splitting schemes

Published: 2014/06/18, Updated: 2014/08/20

Damek Davis

Wotao Yin

Convex and Nonsmooth Optimization alternating direction method of multipliers, averaged operator, douglas-rachford splitting, fixed point algorithm, krasnosel'skii-mann algorithm, little-o convergence, nonexpansive operator, peaceman-rachford splitting

Splitting schemes are a class of powerful algorithms that solve complicated monotone inclusions and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which the simple pieces of the decomposition are processed individually. This leads to easily implementable and highly parallelizable algorithms, which often obtain nearly state-of-the-art performance. … Read more

On the Direct Extension of ADMM for Multi-block Separable Convex Programming and Beyond: From Variational Inequality Perspective

Published: 2014/03/28, Updated: 2014/04/05

Bingsheng He

Xiao-Ming Yuan

Convex Optimization alternating direction method of multipliers, contraction, convergence rate, onvex optimization, splitting methods, variational inequality

When the alternating direction method of multipliers (ADMM) is extended directly to a multi-block separable convex minimization model whose objective function is in form of more than two functions without coupled variables, it was recently shown that the convergence is not guaranteed. This fact urges to develop efficient algorithms that can preserve completely the numerical … Read more

Parallel Multi-Block ADMM with o(1/k) Convergence

Published: 2014/03/18

Constrained Nonlinear Optimization, Convex Optimization admm, alternating direction method of multipliers, convergence rate, parallel and distributed computing

This paper introduces a parallel and distributed extension to the alternating direction method of multipliers (ADMM). The algorithm decomposes the original problem into N smaller subproblems and solves them in parallel at each iteration. This Jacobian-type algorithm is well suited for distributed computing and is particularly attractive for solving certain large-scale problems. This paper introduces … Read more

An Accelerated Linearized Alternating Direction Method of Multipliers

Published: 2014/02/12

Convex Optimization alternating direction method of multipliers, augmented lagrangian method, complexity, convex optimization, lagrange multiplier

We present a novel framework, namely AADMM, for acceleration of linearized alternating direction method of multipliers (ADMM). The basic idea of AADMM is to incorporate a multi-step acceleration scheme into linearized ADMM. We demonstrate that for solving a class of convex composite optimization with linear constraints, the rate of convergence of AADMM is better than … Read more

A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization

Published: 2014/01/27

Convex Optimization, Nonsmooth Optimization alternating direction method of multipliers, block successive upper-bound minimization, randomized block coordinate descent

Consider the problem of minimizing the sum of a smooth convex function and a separable nonsmooth convex function subject to linear coupling constraints. Problems of this form arise in many contemporary applications including signal processing, wireless networking and smart grid provisioning. Motivated by the huge size of these applications, we propose a new class of … Read more

On the Proximal Jacobian Decomposition of ALM for Multiple-block Separable Convex Minimization Problems and its Relationship to ADMM

Published: 2013/11/29, Updated: 2013/12/05

Bingsheng He

Xiao-Ming Yuan

Hong-Kun Xu

Convex Optimization alternating direction method of multipliers, augmented lagrangian method, convex optimization, jacobian decomposition, parallel computing, proximal point algorithm, variational inequality problem

The augmented Lagrangian method (ALM) is a benchmark for solving convex minimization problems with linear constraints. When the objective function of the model under consideration is representable as the sum of some functions without coupled variables, a Jacobian or Gauss-Seidel decomposition is often implemented to decompose the ALM subproblems so that the functions’ properties could … Read more

The Direct Extension of ADMM for Multi-block Convex Minimization Problems is Not Necessarily Convergent

Published: 2013/09/30, Updated: 2013/12/01

Convex Optimization, Statistics alternating direction method of multipliers, computer vision, convergence analysis, convex optimization, image processing, low-rank optimization, sparse optimization, statistical learning

The alternating direction method of multipliers (ADMM) is now widely used in many fields, and its convergence was proved when two blocks of variables are alternatively updated. It is strongly desirable and practically valuable to extend ADMM directly to the case of a multi-block convex minimization problem where its objective function is the sum of … Read more

Distributed Optimization With Local Domain: Applications in MPC and Network Flows

Published: 2013/06/05

Control Applications, Network Optimization alternating direction method of multipliers, distributed algorithms, model predictive control, multicommodity flow, network flow, sensor networks

In this paper we consider a network with P nodes, where each node has exclusive access to a local cost function. Our contribution is a communication-efficient distributed algorithm that finds a vector x* minimizing the sum of all the functions. We make the additional assumption that the functions have intersecting local domains, i.e., each function … Read more