alternating direction method of multipliers

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

  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , ,

    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

  • Wei Deng
  • Ming-Jun Lai
  • Zhimin Peng
  • Wotao Yin
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , ,

    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

    Joint Variable Selection for Data Envelopment Analysis via Group Sparsity

  • Zhiwei (Tony) Qin
  • Irene Song
    • Categories Applications - OR and Management Sciences, Convex Optimization Tags , , ,

    This study develops a data-driven group variable selection method for data envelopment analysis (DEA), a non-parametric linear programming approach to the estimation of production frontiers. The proposed method extends the group Lasso (least absolute shrinkage and selection operator) designed for variable selection on (often predefined) groups of variables in linear regression models to DEA models. … Read more

    An Accelerated Linearized Alternating Direction Method of Multipliers

  • Yunmei Chen
  • Guanghui Lan
  • Yuyuan Ouyang
  • Eduardo Pasiliao Jr.
    • Categories Convex Optimization Tags , , , ,

    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

  • Tsung-Hui Chang
  • Zhi-Quan Luo
  • Shiqian Ma
  • Mingyi Hong
  • Meisam Razaviyayn
  • Xiangfeng Wang
    • Categories Convex Optimization, Nonsmooth Optimization Tags , ,

    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

  • Bingsheng He
  • Xiao-Ming Yuan
  • Hong-Kun Xu
    • Categories Convex Optimization Tags , , , , , ,

    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

  • Caihua Chen
  • Bingsheng He
  • Yinyu Ye
  • Xiao-Ming Yuan
    • Categories Convex Optimization, Statistics Tags , , , , , , ,

    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

  • Pedro Aguiar
  • João Mota
  • Markus Püschel
  • João Xavier
    • Categories Control Applications, Network Optimization Tags , , , , ,

    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

    The proximal-proximal gradient algorithm

  • Ting Kei Pong
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    We consider the problem of minimizing a convex objective which is the sum of a smooth part, with Lipschitz continuous gradient, and a nonsmooth part. Inspired by various applications, we focus on the case when the nonsmooth part is a composition of a proper closed convex function P and a nonzero affine map, with the … Read more

    Optimal scaling of the ADMM algorithm for distributed quadratic programming

  • Euhanna Ghadimi
  • Mikael Johansson
  • Henrik Sandberg
  • Iman Shames
  • André Teixeira
    • Categories Network Optimization, Quadratic Programming Tags ,

    This paper presents optimal scaling of the alternating directions method of multipliers (ADMM) algorithm for a class of distributed quadratic programming problems. The scaling corresponds to the ADMM step-size and relaxation parameter, as well as the edge-weights of the underlying communication graph. We optimize these parameters to yield the smallest convergence factor of the algorithm. … Read more