Optimization Online


Optimal Linearized Alternating Direction Method of Multipliers for Convex Programming

Bingsheng He (hebma***at***nju.edu.cn)
Feng Ma (mafengnju***at***gmail.com)
Xiaoming Yuan (xmyuan***at***hkbu.edu.hk)

Abstract: The alternating direction method of multipliers (ADMM) is being widely used in a variety of areas; its different variants tailored for different application scenarios have also been deeply researched in the literature. Among them, the linearized ADMM has received particularly wide attention from many areas because of its efficiency and easy implementation. To theoretically guarantee the convergence of the linearized ADMM, the step size for the linearized subproblems, or the reciprocal of the linearization parameter, should be sufficiently small. On the other hand, small step sizes decelerate the convergence numerically. Hence, it is crucial to determine an optimal (largest) value of the step size while the convergence of the linearized ADMM can be still ensured. Such an analysis seems to be lacked in the literature. In this paper, we show how to find this optimal step size for the linearized ADMM and hence propose the optimal linearized ADMM in the convex programming context. Its global convergence and worst-case convergence rate measured by the iteration complexity are proved as well.

Keywords: Convex programming, alternating direction method of multipliers, linearized, optimal step size, proximal regularization, convergence rate

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 09/27/2017
Entry Accepted: 09/27/2017
Entry Last Modified: 10/15/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