Optimization Online


Convergence Study on the Proximal Alternating Direction Method with Larger Step Size

Bingsheng He(hebma***at***nju.edu.cn)
Feng Ma(mafengnju***at***gmail.com)

Abstract: The alternating direction method of multipliers (ADMM) is a popular method for the separable convex programming with linear constraints, and the proximal ADMM is its important variant. Previous studies show that the relaxation factor $\gamma\in (0, \frac{1+\sqrt{5}}{2})$ by Fortin and Glowinski for the ADMM is also valid for the proximal ADMM. In this paper, we further demonstrate that the feasible region of $\gamma$ depends on the proximal term added on the second subproblem, and can be enlarged when the proximal factor is positive. We derive the exact relationship between the relaxation factor $\gamma$ and the proximal factor. Finally, we prove the global convergence and derive a worst-case $O(1/t)$ convergence rate in the ergodic sense for this generalized scheme.

Keywords: Alternating Direction Method of Multipliers, Convex Programming, Proximal Regularization, Contraction, Convergence Analysis.

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 02/12/2017
Entry Accepted: 02/12/2017
Entry Last Modified: 02/12/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society