Linear Convergence in Optimization Over Directed Graphs With Row-Stochastic Matrices

DOI10.1109/TAC.2018.2797164MaRDI QIDQ4562301zbMATH OpenOpenAlexFDO

Authors Chenguang Xi, Van Sy Mai, Ran Xin, Eyad H. Abed, Usman A. Khan

Publication date 19 December 2018

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

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

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Programming involving graphs or networks (90C35)

Abstract: This paper considers a distributed optimization problem over a multi-agent network, in which the objective function is a sum of individual cost functions at the agents. We focus on the case when communication between the agents is described by a emph{directed} graph. Existing distributed optimization algorithms for directed graphs require at least the knowledge of the neighbors' out-degree at each agent (due to the requirement of column-stochastic matrices). In contrast, our algorithm requires no such knowledge. Moreover, the proposed algorithm achieves the best known rate of convergence for this class of problems, $O(m{u}^k)$ for $0<mu<1$, where $k$ is the number of iterations, given that the objective functions are strongly-convex and have Lipschitz-continuous gradients. Numerical experiments are also provided to illustrate the theoretical findings.

Cited in

(28)

• Distributed optimization over directed graphs with row stochasticity and constraint regularity
• Nash equilibrium seeking in N-coalition games via a gradient-free method
• An accelerated distributed gradient method with local memory
• Distributed adaptive Newton methods with global superlinear convergence
• An improved distributed gradient-push algorithm for bandwidth resource allocation over wireless local area network
• Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs
• Distributed dynamic event-triggered algorithm with minimum inter-event time for multi-agent convex optimisation
• Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
• Distributed dynamic event-triggered algorithm with positive minimum inter-event time for convex optimisation problem
• Distributed mirror descent algorithm over unbalanced digraphs based on gradient weighting technique
• An accelerated exact distributed first-order algorithm for optimization over directed networks
• A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
• Optimal output consensus of second‐order uncertain nonlinear systems on weight‐unbalanced directed networks
• Distributed optimization without boundedness of gradients for second-order multi-agent systems over unbalanced network
• Event-triggered distributed Nash equilibrium seeking over directed graphs and its application to power management
• Linear convergence of distributed estimation with constraints and communication delays
• Distributed object pose estimation over strongly connected networks
• Distributed constrained optimization algorithms with linear convergence rate over time-varying unbalanced graphs
• Momentum-based distributed gradient tracking algorithms for distributed aggregative optimization over unbalanced directed graphs
• A decentralized Nesterov gradient method for stochastic optimization over unbalanced directed networks
• A distributed consensus based algorithm for economic dispatch over time-varying digraphs
• Local consensus based multi-objective distributed optimization and its application
• Distributed MPC algorithm with row-stochastic weight matrix over non-ideal time-varying directed communication
• AB /Push-Pull method for distributed optimization in time-varying directed networks
• Gradient tracking for sum-of-nonconvex decentralized optimization
• Distributed aggregative optimization over directed networks with column-stochasticity
• Performing linear convergence for distributed constrained optimisation over time-varying directed unbalanced networks
• Privacy-preserving gradient tracking via state decomposition for directed multi-agent optimization

This page was built for publication: Linear Convergence in Optimization Over Directed Graphs With Row-Stochastic Matrices

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