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 [7] indicating that the multi-block ADMM for minimizing the sum of N (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 present convergence and convergence rate results for the multi-block ADMM applied to solve certain N -block (N ≥ 3) convex minimization problems without requiring strong convexity. Specifically, we prove the following two results: (1) the multi-block ADMM returns an ǫ-optimal solution within O(1/ǫ 2 ) iterations by solving an associated perturbation to the original problem; (2) the multi-block ADMM returns an ǫ-optimal solution within O(1/ǫ) iterations when it is applied to solve a certain sharing problem, under the condition that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz property, which essentially covers most convex optimization models except for some pathological cases.
In REF , the authors proved that multi-block ADMM can achieve -optimal solutions within O(1/ 2 ) iterations by solving a modified version of the original problem, and whitin O(1/ ) iterations when applied to certain sharing problems conditioned on properties of the augmented Lagrangian function.
Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity
arXiv: Optimization and Control
Mathematics Computer Science