| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
08 February 2025 |
|
| | | |
|
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 | Abstract: | The 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 |
|
|
No review found.
Did you like this article?
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.
|
| |
|
|
|