Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3667
Articles: 2'599'751
Articles rated: 2609

08 February 2025
 
  » arxiv » 1508.0193

 Article overview



On the Convergence of Multi-Block Alternating Direction Method of Multipliers and Block Coordinate Descent Method
Caihua Chen ; Min Li ; Xin Liu ; Yinyu Ye ;
Date 2 Aug 2015
AbstractThe paper answers several open questions of the alternating direction method of multipliers (ADMM) and the block coordinate descent (BCD) method that are now wildly used to solve large scale convex optimization problems in many fields. For ADMM, it is still lack of theoretical understanding of the algorithm when the objective function is not separable across the variables. In this paper, we analyze the convergence of the 2-block ADMM for solving the linearly constrained convex optimization with coupled quadratic objective, and show that the classical ADMM point-wisely converges to a primal-dual solution pair of this problem. Moreover, we propose to use the randomly permuted ADMM (RPADMM) to solve the non-separable multi-block convex optimization, and prove its expected convergence while applied to solve a class of quadratic programming problems. When the linear constraint vanishes, the 2-block ADMM and the randomly permuted ADMM reduce to the 2-block cyclic BCD method (also known as the alternating minimization method) and the EPOCHS (The randomly permuted cyclic BCD method, also known as the "sampling without replacement" variant of randomized BCD. For simplicity, we call it EPOCHS as suggested in a very recent survey paper of Stephen Wright). Our study provides the first iteration convergence result of the 2-block cyclic BCD method under only the unique solutions type conditions of subproblems. More importantly, we also theoretically establish the first expected convergence result of the multi-block EPOCHS.
Source arXiv, 1508.0193
Services Forum | Review | PDF | Favorites   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.






ScienXe.org
» my Online CV
» Free

home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2025 - Scimetrica