alternating direction method of multipliers

Linearized Alternating Direction Method of Multipliers via Positive-Indefinite Proximal Regularization for Convex Programming

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

    The alternating direction method of multipliers (ADMM) is being widely used for various convex minimization models with separable structures arising in a variety of areas. In the literature, the proximalversion of ADMM which allows ADMM’s subproblems to be proximally regularized has been well studied. Particularly the linearized version of ADMM can be yielded when the … Read more

    Faster Alternating Direction Method of Multipliers with a Worst-case O(1/n^2) Convergence Rate

  • Wenyi Tian
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , ,

    The alternating direction method of multipliers (ADMM) is being widely used for various convex programming models with separable structures arising in specifically many scientific computing areas. The ADMM’s worst-case O(1/n) convergence rate measured by the iteration complexity has been established in the literature when its penalty parameter is a constant, where n is the iteration … Read more

    Randomized Primal-Dual Proximal Block Coordinate Updates

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

    In this paper we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its $O(1/t)$ convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such … Read more

    Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis

  • Bo Jiang
  • Tianyi Lin
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Nonlinear Optimization Tags , , , , ,

    Nonconvex optimization problems are frequently encountered in much of statistics, business, science and engineering, but they are not yet widely recognized as a technology. A reason for this relatively low degree of popularity is the lack of a well developed system of theory and algorithms to support the applications, as is the case for its … Read more

    Improved pointwise iteration-complexity of a regularized ADMM and of a regularized non-Euclidean HPE framework

  • Max L. N. Gonçalves
  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , ,

    This paper describes a regularized variant of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex programs. It is shown that the pointwise iteration-complexity of the new method is better than the corresponding one for the standard ADMM method and that, up to a logarithmic term, is identical to the ergodic iteration-complexity … Read more

    On the Convergence of Multi-Block Alternating Direction Method of Multipliers and Block Coordinate Descent Method

  • Caihua Chen
  • Xin Liu
  • Yinyu Ye
  • Min Li
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    The paper answers several open questions of the alternating direction method of multipliers (ADMM) and the block coordinate descent (BCD) method that are now wildly used to solve large scale convex optimization problems in many fields. For ADMM, it is still lack of theoretical understanding of the algorithm when the objective function is not separable … Read more

    ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

  • Zhimin Peng
  • Yangyang Xu
  • Ming Yan
  • Wotao Yin
    • Categories Convex Optimization, Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

    We propose ARock, an asynchronous parallel algorithmic framework for finding a fixed point to a nonexpansive operator. In the framework, a set of agents (machines, processors, or cores) update a sequence of randomly selected coordinates of the unknown variable in an asynchronous parallel fashion. As special cases of ARock, novel algorithms for linear systems, convex … Read more

    Alternating Direction Method of Multipliers for Linear Programming

  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Linear Programming Tags , ,

    Recently the alternating direction method of multipliers (ADMM) has been widely used for various applications arising in scientific computing areas. Most of these application models are, or can be easily reformulated as, linearly constrained convex minimization models with separable nonlinear objective functions. In this note we show that ADMM can also be easily used for … Read more

    On the Step Size of Symmetric Alternating Directions Method of Multipliers

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

    The alternating direction method of multipliers (ADMM) is an application of the Douglas-Rachford splitting method; and the symmetric version of ADMM which updates the Lagrange multiplier twice at each iteration is an application of the Peaceman-Rachford splitting method. Sometimes the symmetric ADMM works empirically; but theoretically its convergence is not guaranteed. It was recently found … Read more

    Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity

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

    The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems due to its superior practical performance. On the theoretical side however, a counterexample was shown in [7] indicating that the multi-block ADMM for minimizing the sum of $N$ $(N\geq 3)$ convex functions with $N$ block variables linked by linear … Read more