BADMM

Bregman Alternating Direction Method of Multipliers. The mirror descent algorithm (MDA) generalizes gradient descent by using a Bregman divergence to replace squared Euclidean distance. In this paper, we similarly generalize the alternating direction method of multipliers (ADMM) to Bregman ADMM (BADMM), which allows the choice of different Bregman divergences to exploit the structure of problems. BADMM provides a unified framework for ADMM and its variants, including generalized ADMM, inexact ADMM and Bethe ADMM. We establish the global convergence and the O(1/T) iteration complexity for BADMM. In some cases, BADMM can be faster than ADMM by a factor of O(n/log(n)). In solving the linear program of mass transportation problem, BADMM leads to massive parallelism and can easily run on GPU. BADMM is several times faster than highly optimized commercial software Gurobi.


References in zbMATH (referenced in 13 articles )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Chizat, Lénaïc; Peyré, Gabriel; Schmitzer, Bernhard; Vialard, François-Xavier: Scaling algorithms for unbalanced optimal transport problems (2018)
  2. Diamond, S.; Takapoui, R.; Boyd, S.: A general system for heuristic minimization of convex functions over non-convex sets (2018)
  3. Hajinezhad, Davood; Shi, Qingjiang: Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications (2018)
  4. Pang, Jong-Shi; Tao, Min: Decomposition methods for computing directional stationary solutions of a class of nonsmooth nonconvex optimization problems (2018)
  5. Sun, Tao; Yin, Penghang; Cheng, Lizhi; Jiang, Hao: Alternating direction method of multipliers with difference of convex functions (2018)
  6. Li, Guoyin; Liu, Tianxiang; Pong, Ting Kei: Peaceman-Rachford splitting for a class of nonconvex optimization problems (2017)
  7. Wu, Zhongming; Li, Min; Wang, David Z. W.; Han, Deren: A symmetric alternating direction method of multipliers for separable nonconvex minimization problems (2017)
  8. Yang, Lei; Pong, Ting Kei; Chen, Xiaojun: Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction (2017)
  9. Levine, Sergey; Finn, Chelsea; Darrell, Trevor; Abbeel, Pieter: End-to-end training of deep visuomotor policies (2016)
  10. Li, Min; Sun, Defeng; Toh, Kim-Chuan: A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization (2016)
  11. Li, Guoyin; Pong, Ting Kei: Global convergence of splitting methods for nonconvex composite optimization (2015)
  12. Peyré, Gabriel: Entropic approximation of Wasserstein gradient flows (2015)
  13. Huahua Wang, Arindam Banerjee: Bregman Alternating Direction Method of Multipliers (2013) arXiv