Name
Title | ||
|---|---|---|
Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity |
Abstract | ||
|---|---|---|
The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems due to its superior practical performance. On the theoretical side however, a counterexample was shown in Chen et al. (Math Program 155(1):57---79, 2016.) indicating that the multi-block ADMM for minimizing the sum of N$$(N\\ge 3)$$(Nź3) convex functions with N block variables linked by linear constraints may diverge. It is therefore of great interest to investigate further sufficient conditions on the input side which can guarantee convergence for the multi-block ADMM. The existing results typically require the strong convexity on parts of the objective. In this paper, we provide two different ways related to multi-block ADMM that can find an $$\\epsilon $$∈-optimal solution and do not require strong convexity of the objective function. Specifically, we prove the following two results: (1) the multi-block ADMM returns an $$\\epsilon $$∈-optimal solution within $$O(1/\\epsilon ^2)$$O(1/∈2) iterations by solving an associated perturbation to the original problem; this case can be seen as using multi-block ADMM to solve a modified problem; (2) the multi-block ADMM returns an $$\\epsilon $$∈-optimal solution within $$O(1/\\epsilon )$$O(1/∈) iterations when it is applied to solve a certain sharing problem, under the condition that the augmented Lagrangian function satisfies the Kurdyka---źojasiewicz property, which essentially covers most convex optimization models except for some pathological cases; this case can be seen as applying multi-block ADMM to solving a special class of problems. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10915-016-0182-0 | J. Sci. Comput. |
Keywords | Field | DocType |
Alternating direction method of multipliers (ADMM), Convergence rate, Regularization, Kurdyka–Łojasiewicz property, Convex optimization, 90C25, 90C30 | Convergence (routing),Mathematical optimization,Convexity,Mathematical analysis,Augmented Lagrangian method,Convex function,Regularization (mathematics),Rate of convergence,Counterexample,Convex optimization,Mathematics | Journal |
Volume | Issue | ISSN |
69 | 1 | 1573-7691 |
Citations | PageRank | References |
12 | 0.54 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tianyi Lin | 1 | 147 | 11.79 |
| Shiqian Ma | 2 | 1068 | 63.48 |
| Shuzhong Zhang | 3 | 2808 | 181.66 |