We study distributed optimization where nodes cooperatively minimize the sum of their individual, locally known, convex costs @math 's, @math is global. Distributed augmented Lagrangian (AL) methods have good empirical performance on several signal processing and learning applications, but there is limited understanding of their convergence rates and how it depends on the underlying network. This paper establishes globally linear (geometric) convergence rates of a class of deterministic and randomized distributed AL methods, when the @math 's are twice continuously differentiable and have a bounded Hessian. We give explicit dependence of the convergence rates on the underlying network parameters. Simulations illustrate our analytical findings.
@cite_28: We study the computational complexity certification of inexact gradient augmented Lagrangian methods for solving convex optimization problems with complicated constraints. We solve the augmented Lagrangian dual problem that arises from the relaxation of complicating constraints with gradient and fast gradient methods based on inexact first order information. Moreover, since the exact solution of the augmented Lagrangian primal problem is hard to compute in practice, we solve this problem up to some given inner accuracy. We derive relations between the inner and the outer accuracy of the primal and dual problems and we give a full convergence rate analysis for both gradient and fast gradient algorithms. We provide estimates on the primal and dual suboptimality and on primal feasibility violation of the generated approximate primal and dual solutions. Our analysis relies on the Lipschitz property of the dual function and on inexact dual gradients. We also discuss implementation aspects of the proposed algor...
@cite_12: This paper shows, by means of an operator called asplitting operator, that the Douglas--Rachford splitting method for finding a zero of the sum of two monotone operators is a special case of the proximal point algorithm. Therefore, applications of Douglas--Rachford splitting, such as the alternating direction method of multipliers for convex programming decomposition, are also special cases of the proximal point algorithm. This observation allows the unification and generalization of a variety of convex programming algorithms. By introducing a modified version of the proximal point algorithm, we derive a new,generalized alternating direction method of multipliers for convex programming. Advances of this sort illustrate the power and generality gained by adopting monotone operator theory as a conceptual framework.
@cite_23: 
. Our work is also related to studies of the AL and related algorithms in conventional, centralized optimization. There is a vast literature on the subject, and many authors considered inexact primal minimizations (see @cite_23 @cite_28 @cite_12 and the references listed in the following paragraphs.) Before detailing the existing work, we point to main differences of this paper with respect to usual studies in the literature. First, when analyzing inexact AL methods, the literature usually assumes that the primal problems use arbitrary initialization. In contrast, we initialize the inner primal algorithm with the previous primal variable. Consequently, our results and the results in the literature are different, the algorithms in the literature typically be convergent only to a solution neighborhood, e.g. @cite_23 @cite_28 . Second, except for recent papers, e.g., @cite_23 @cite_28 , the analysis of inexact AL is usually done with respect to dual sub-optimality. In contrast, we are interested in the primal sub-optimality measures. Third, convergence rates are usually established at the outer iteration level, while we--besides the outer iterations level--establish the rates in the number of iterations.