Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms

DOI10.1109/TAC.2014.2363299MaRDI QIDQ2982765zbMATH OpenFDO

Authors Dušan Jakovetić, José M. F. Moura, João Xavier

Publication date 16 May 2017

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2482

Mathematics Subject Classification ID

Distributed algorithms (68W15) Convex programming (90C25)

Abstract: We study distributed optimization where nodes cooperatively minimize the sum of their individual, locally known, convex costs $f_i(x)$'s, $xin{mathbbR}^d$ 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 $f_i$'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.

Cited in

(18)

• Distributed optimization over directed graphs with row stochasticity and constraint regularity
• Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method
• Distributed decision-coupled constrained optimization via proximal-tracking
• Tracking-ADMM for distributed constraint-coupled optimization
• Cluster-based distributed augmented Lagrangian algorithm for a class of constrained convex optimization problems
• A distributed methodology for approximate uniform global minimum sharing
• Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization
• Ontology sparse vector learning algorithm for ontology similarity measuring and ontology mapping via ADAL technology
• Distributed subgradient method for multi-agent optimization with quantized communication
• Decentralized consensus algorithm with delayed and stochastic gradients
• A randomized incremental primal-dual method for decentralized consensus optimization
• Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
• Optimal convergence rates for convex distributed optimization in networks
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Primal-dual -subgradient method for distributed optimization
• Distributed convex optimization based on ADMM and belief propagation methods
• Balancing communication and computation in gradient tracking algorithms for decentralized optimization
• Achieving optimal output consensus for discrete-time linear multi-agent systems with disturbance rejection

This page was built for publication: Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2982765)