The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent

Chen Caihua Nanjing University He Bingsheng Nanjing University Ye Yinyu Stanford University Yuan Xiaoming Hong Kong Baptist University

Optimization and Control mathscidoc:1803.27001

Distinguished Paper Award in 2018

Mathematical Programming, 155, 55-79, 2016.1
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 the 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 an affirmative convergence proof nor an example showing its divergence is known in the literature. In this paper we give a negative answer to this long-standing open question: The direct extension of ADMM is not necessarily convergent. We present a sufficient condition to ensure the convergence of the direct extension of ADMM, and give an example to show its divergence.
Alternating direction method of multipliers,Convergence analysis,Convex programming,Splitting methods
[ Download ] [ 2018-03-04 17:02:55 uploaded by chchen ] [ 789 downloads ] [ 0 comments ]
@inproceedings{chen2016the,
  title={The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent},
  author={Chen Caihua, He Bingsheng, Ye Yinyu, and Yuan Xiaoming},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20180304170255143926964},
  booktitle={Mathematical Programming},
  volume={155},
  pages={55-79},
  year={2016},
}
Chen Caihua, He Bingsheng, Ye Yinyu, and Yuan Xiaoming. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. 2016. Vol. 155. In Mathematical Programming. pp.55-79. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20180304170255143926964.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved