Distributed optimization over directed graphs with row stochasticity and constraint regularity
From MaRDI portal
Abstract: This paper deals with an optimization problem over a network of agents, where the cost function is the sum of the individual objectives of the agents and the constraint set is the intersection of local constraints. Most existing methods employing subgradient and consensus steps for solving this problem require the weight matrix associated with the network to be column stochastic or even doubly stochastic, conditions that can be hard to arrange in directed networks. Moreover, known convergence analyses for distributed subgradient methods vary depending on whether the problem is unconstrained or constrained, and whether the local constraint sets are identical or nonidentical and compact. The main goals of this paper are: (i) removing the common column stochasticity requirement; (ii) relaxing the compactness assumption, and (iii) providing a unified convergence analysis. Specifically, assuming the communication graph to be fixed and strongly connected and the weight matrix to (only) be row stochastic, a distributed projected subgradient algorithm and its variation are presented to solve the problem for cost functions that are convex and Lipschitz continuous. Based on a regularity assumption on the local constraint sets, a unified convergence analysis is given that can be applied to both unconstrained and constrained problems and without assuming compactness of the constraint sets or an interior point in their intersection. Further, we also establish an upper bound on the absolute objective error evaluated at each agent's available local estimate under a nonincreasing step size sequence. This bound allows us to analyze the convergence rate of both algorithms.
Recommendations
- Distributed stochastic subgradient projection algorithms based on weight-balancing over time-varying directed graphs
- Distributed stochastic subgradient projection algorithms for convex optimization
- Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs
- Distributed constrained optimization for multi-agent systems over a directed graph with piecewise stepsize
- Distributed quasi-monotone subgradient algorithm for nonsmooth convex optimization over directed graphs
Cites work
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- scientific article; zbMATH DE number 3449561 (Why is no real title available?)
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Asynchronous Gossip-Based Random Projection Algorithms Over Networks
- Constrained Consensus and Optimization in Multi-Agent Networks
- Convergence Rate of Distributed ADMM Over Networks
- DEXTRA: A Fast Algorithm for Optimization Over Directed Graphs
- Distributed Finite-Time Computation of Digraph Parameters: Left-Eigenvector, Out-Degree and Spectrum
- Distributed Online Convex Optimization on Time-Varying Directed Graphs
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed Subgradient Methods for Convex Optimization Over Random Networks
- Distributed Subgradient Methods for Multi-Agent Optimization
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- Distributed multi-agent optimization subject to nonidentical constraints and communication delays
- Distributed multi-agent optimization with state-dependent communication
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Distributed stochastic subgradient projection algorithms for convex optimization
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- ExtraPush for convex smooth decentralized optimization over directed networks
- Introductory lectures on convex optimization. A basic course.
- Laplacians and the Cheeger inequality for directed graphs
- Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms
- Linear Convergence in Optimization Over Directed Graphs With Row-Stochastic Matrices
- Matrix Analysis
- Newton-like method with diagonal correction for distributed optimization
- On Projection Algorithms for Solving Convex Feasibility Problems
- The Distance to the Intersection of Two Convex Sets Expressed by the Distances to Each of Them
Cited in
(20)- Distributed optimization without boundedness of gradients for second-order multi-agent systems over unbalanced network
- Distributed quasi-monotone subgradient algorithm for nonsmooth convex optimization over directed graphs
- Distributed primal-dual method on unbalanced digraphs with row stochasticity
- Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs
- Distributed object pose estimation over strongly connected networks
- Distributed constrained optimization for multi-agent systems over a directed graph with piecewise stepsize
- Privacy-preserving distributed projected one-point bandit online optimization over directed graphs
- Adaptive backstepping for distributed optimization
- Distributed stochastic optimization algorithm with non-consistent constraints in time-varying unbalanced networks
- Online distributed dual averaging algorithm for multi-agent bandit optimization over time-varying general directed networks
- Distributed multi-UAV trajectory optimization over directed networks
- A causal filter of gradient information for enhanced robustness and resilience in distributed convex optimization
- Subgradient averaging for multi-agent optimisation with different constraint sets
- A privacy-masking learning algorithm for online distributed optimization over time-varying unbalanced digraphs
- Differentially private distributed online learning over time‐varying digraphs via dual averaging
- Distributed optimization of multi-integrator agent systems with mixed neighbor interactions
- A Distributed SDP Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation
- Distributed optimal resource allocation over strongly connected digraphs: a surplus-based approach
- 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
This page was built for publication: Distributed optimization over directed graphs with row stochasticity and constraint regularity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1737783)
