Convergence of the Augmented Decomposition Algorithm

Abstract

We study the convergence of the Augmented Decomposition Algorithm (ADA) proposed in [32] for solving multi-block separable convex minimization problems subject to linear constraints. We show that the global convergence rate of the exact ADA is o(1/k) under the assumption that there exists a saddle point. We consider the inexact Augmented Decomposition Algorithm (iADA) and establish global and local convergence results under some mild assumptions, by providing a stability result for the maximal monotone operator T associated with the perturbation from both primal and dual perspectives. This result implies the local linear convergence of the inexact ADA for many applications such as the lasso, total variation reconstruction, exchange problem and many other problems from statistics, machine learning and engineering with l1 regularization.

References in corpus (5)

• Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
• Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
• A parameterized proximal point algorithm for separable convex optimization
• Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Quadratic and Semi-Definite Programming
• On the R-superlinear convergence of the KKT residues generated by the augmented Lagrangian method for convex composite conic programming