Distributed Optimization Over Time-Varying Directed Graphs

DOI10.1109/TAC.2014.2364096MaRDI QIDQ2982801zbMATH OpenFDO

Authors Angelia Nedić, Alex Olshevsky

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/1303.2289

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Convex programming (90C25) Programming involving graphs or networks (90C35)

Abstract: We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a time-varying sequence of directed graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of $O(ln(t)/sqrtt)$, where the constant depends on the initial values at the nodes, the subgradient norms, and, more interestingly, on both the consensus speed and the imbalances of influence among the nodes.

Cited in

(only showing first 100 items - show all)

• Nash equilibrium seeking for N-coalition noncooperative games
• Optimal distributed stochastic mirror descent for strongly convex optimization
• Consensus for heterogeneous networked multi-agent systems with switching topology and time-varying delays
• Exponential convergence of a distributed algorithm for solving linear algebraic equations
• Convergence rate analysis of distributed optimization with projected subgradient algorithm
• Delay-induced discrete-time consensus
• A fast proximal gradient algorithm for decentralized composite optimization over directed networks
• Distributed optimization methods for nonconvex problems with inequality constraints over time-varying networks
• Stochastic learning in multi-agent optimization: communication and payoff-based approaches
• Resilient distributed optimal generation dispatch for lossy AC microgrids
• Distributed quasi-monotone subgradient algorithm for nonsmooth convex optimization over directed graphs
• Distributed optimization over directed graphs with row stochasticity and constraint regularity
• Necessary and sufficient conditions for containment control of multi-agent systems with time delay
• Distributed consensus-based multi-agent convex optimization via gradient tracking technique
• Improved mixing rates of directed cycles by added connection
• Distributed optimization of multiagent systems in directed networks with time-varying delay
• Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method
• Distributed convex optimization with coupling constraints over time-varying directed graphs
• Distributed constrained stochastic subgradient algorithms based on random projection and asynchronous broadcast over networks
• Parallel alternating direction method of multipliers
• Distributed multi-UAV trajectory optimization over directed networks
• A privacy-masking learning algorithm for online distributed optimization over time-varying unbalanced digraphs
• Distributed decision-coupled constrained optimization via proximal-tracking
• Asynchronous networked aggregative games
• Distributed resource allocation via multi-agent systems under time-varying networks
• Solving leaderless multi-cluster games over directed graphs
• Distributed gradient tracking methods with finite data rates
• A multi-scale method for distributed convex optimization with constraints
• Convergence results of a nested decentralized gradient method for non-strongly convex problems
• An accelerated distributed gradient method with local memory
• Surplus-based accelerated algorithms for distributed optimization over directed networks
• Primal-dual method for optimization problems with changing constraints
• Distributed ergodic algorithms for mixed equilibrium problems: absent of cut property
• Gradient-free distributed optimization with exact convergence
• Distributed support vector machine in master-slave mode
• Distributed constrained optimization for multi-agent systems over a directed graph with piecewise stepsize
• Regularized dual gradient distributed method for constrained convex optimization over unbalanced directed graphs
• Tracking-ADMM for distributed constraint-coupled optimization
• Network flows that solve least squares for linear equations
• Predefined-time optimization for distributed resource allocation
• Cooperative convex optimization with subgradient delays using push-sum distributed dual averaging
• An improved distributed gradient-push algorithm for bandwidth resource allocation over wireless local area network
• A distributed algorithm for solving mixed equilibrium problems
• Random asynchronous iterations in distributed coordination algorithms
• Stability analysis of distributed convex optimization under persistent attacks: a hybrid systems approach
• A Lie bracket approximation approach to distributed optimization over directed graphs
• Communication-efficient algorithms for decentralized and stochastic optimization
• Distributed learning of average belief over networks using sequential observations
• An adaptive online learning algorithm for distributed convex optimization with coupled constraints over unbalanced directed graphs
• Distributed multi-step subgradient optimization for multi-agent system
• Distributed stochastic subgradient projection algorithms based on weight-balancing over time-varying directed graphs
• Multi-cluster distributed optimization via random sleep strategy
• Spatially distributed sampling and reconstruction
• Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
• Distributed nonconvex constrained optimization over time-varying digraphs
• Distributed second-order continuous-time optimization via adaptive algorithm with nonuniform gradient gains
• Distributed economic dispatch via a predictive scheme: heterogeneous delays and privacy preservation
• Distributed optimal resource allocation over strongly connected digraphs: a surplus-based approach
• Subgradient averaging for multi-agent optimisation with different constraint sets
• Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs
• Privacy-preserving dual stochastic push-sum algorithm for distributed constrained optimization
• Noise-to-state exponentially stable distributed convex optimization on weight-balanced digraphs
• Decentralized gradient algorithm for solution of a linear equation
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• Distributed deterministic asynchronous algorithms in time-varying graphs through Dykstra splitting
• Networked parallel algorithms for robust convex optimization via the scenario approach
• Decentralized consensus algorithm with delayed and stochastic gradients
• Robust asynchronous stochastic gradient-push: asymptotically optimal and network-independent performance for strongly convex functions
• GADMM: fast and communication efficient framework for distributed machine learning
• A randomized incremental primal-dual method for decentralized consensus optimization
• Event-triggered zero-gradient-sum distributed optimisation algorithm with time-varying communication delays
• Distributed dynamic event-triggered algorithm with minimum inter-event time for multi-agent convex optimisation
• Distributed multi-step subgradient projection algorithm with adaptive event-triggering protocols: a framework of multiagent systems
• Decentralized multi-agent optimization based on a penalty method
• Distributed smooth optimisation with event-triggered proportional-integral algorithms
• Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
• Distributed variable sample-size gradient-response and best-response schemes for stochastic Nash equilibrium problems
• Second-order guarantees of distributed gradient algorithms
• Duality and Stability in Complex Multiagent State-Dependent Network Dynamics
• A distributed ADMM-like method for resource sharing over time-varying networks
• Optimal convergence rates for convex distributed optimization in networks
• A simple framework for stability analysis of state-dependent networks of heterogeneous agents
• Event-triggered zero-gradient-sum distributed convex optimisation over networks with time-varying topologies
• Asynchronous algorithms for computing equilibrium prices in a capital asset pricing model
• Generalised gossip-based subgradient method for distributed optimisation
• A dual approach for optimal algorithms in distributed optimization over networks
• Distributed dynamic event-triggered algorithm with positive minimum inter-event time for convex optimisation problem
• Variable metric primal-dual method for convex optimization problems with changing constraints
• Distributed optimization of multi-integrator agent systems with mixed neighbor interactions
• An event-triggering algorithm for decentralized stochastic optimization over networks
• Distributed mirror descent algorithm over unbalanced digraphs based on gradient weighting technique
• A distributed optimization algorithm over Markov switching topology under adversarial attack
• Semi‐global weighted output average tracking of heterogeneous multi‐agent systems in the presence of actuator saturation and external disturbances
• A gradient‐free distributed optimization method for convex sum of nonconvex cost functions
• Distributed optimization with hybrid linear constraints for multi‐agent networks
• A distributed accelerated optimization algorithm over time‐varying directed graphs with uncoordinated step‐sizes
• Distributed Optimization Over Time-Varying Graphs With Imperfect Sharing of Information
• A fixed step distributed proximal gradient push‐pull algorithm based on integral quadratic constraint
• Differentially private distributed online learning over time‐varying digraphs via dual averaging
• Optimal output consensus of second‐order uncertain nonlinear systems on weight‐unbalanced directed networks

This page was built for publication: Distributed Optimization Over Time-Varying Directed Graphs

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