admm

Understanding the Convergence of the Alternating Direction Method of Multipliers: Theoretical and Computational Perspectives

  • Jonathan Eckstein
  • Wang Yao
    • Categories Convex Optimization Tags ,

    The alternating direction of multipliers (ADMM) is a form of augmented Lagrangian algorithm that has experienced a renaissance in recent years due to its applicability to optimization problems arising from “big data” and image processing applications, and the relative ease with which it may be implemented in parallel and distributed computational environments. While it is … Read more

    Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems

  • Tianyi Lin
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    The alternating direction method of multipliers (ADMM) has been successfully applied to solve structured convex optimization problems due to its superior practical performance. The convergence properties of the 2-block ADMM have been studied extensively in the literature. Specifically, it has been proven that the 2-block ADMM globally converges for any penalty parameter $\gamma>0$. In this … Read more

    First-Order Algorithms for Convex Optimization with Nonseparate Objective and Coupled Constraints

  • Xiang Gao
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we consider a block-structured convex optimization model, where in the objective the block-variables are nonseparable and they are further linearly coupled in the constraint. For the 2-block case, we propose a number of first-order algorithms to solve this model. First, the alternating direction method of multipliers (ADMM) is extended, assuming that it … Read more

    Activity Identification and Local Linear Convergence of Douglas-Rachford/ADMM under Partial Smoothness

  • Jalal Fadili
  • Jingwei Liang
  • Russell Luke
  • Gabriel Peyré
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    Proximal splitting algorithms are becoming popular to solve convex optimization problems in variational image processing. Within this class, Douglas-Rachford (DR) and ADMM are designed to minimize the sum of two proper lower semicontinuous convex functions whose proximity operators are easy to compute. The goal of this work is to understand the local convergence behaviour of … 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

    Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems

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

    The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm … Read more

    On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers

  • Wei Deng
  • Wotao Yin
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    The formulation min f(x)+g(y) subject to Ax+By=b, where f and g are extended-value convex functions, arises in many application areas such as signal processing, imaging and image processing, statistics, and machine learning either naturally or after variable splitting. In many common problems, one of the two objective functions is strictly convex and has Lipschitz continuous … Read more