The Direct Extension of ADMM for Multi-block Convex Minimization Problems is Not Necessarily Convergent

Caihua Chen (chchennju.edu.cn)
Bingsheng He (hebmanju.edu.cn)
Yinyu Ye (yyyestanford.edu)
Xiaoming Yuan (xmyuanhkbu.edu.hk)

Abstract: The alternating direction method of multipliers (ADMM) is now widely used in many fields, and its convergence was proved when two blocks of variables are alternatively updated. It is strongly desirable and practically valuable to extend ADMM directly to the case of a multi-block convex minimization problem where its objective function is the sum of more than two separable convex functions. However, the convergence of this extension has been missing for a long time --- neither affirmatively proved convergence nor counter example showing its failure of convergence is known in the literature. In this paper we answer this long-standing open question: the direct extension of ADMM is not necessarily convergent. We present an example showing its failure of convergence, and a sufficient condition ensuring its convergence.

Keywords: Alternating direction method of multipliers, Convergence analysis, Convex programming, Sparse optimization, Low-rank Optimization, Image processing, Statistical learning, Computer vision

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Applications -- Science and Engineering (Statistics )

Citation:

Download: [PDF]

Entry Submitted: 09/30/2013
Entry Accepted: 09/30/2013
Entry Last Modified: 12/01/2013

Modify/Update this entry