Distributed nonconvex constrained optimization over time-varying digraphs
From MaRDI portal
Publication:2425183
Decomposition methods (49M27) Numerical optimization and variational techniques (65K10) Numerical methods for variational inequalities and related problems (65K15) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Applications of mathematical programming (90C90) Noncooperative games (91A10)
Abstract: This paper considers nonconvex distributed constrained optimization over networks, modeled as directed (possibly time-varying) graphs. We introduce the first algorithmic framework for the minimization of the sum of a smooth nonconvex (nonseparable) function--the agent's sum-utility--plus a Difference-of-Convex (DC) function (with nonsmooth convex part). This general formulation arises in many applications, from statistical machine learning to engineering. The proposed distributed method combines successive convex approximation techniques with a judiciously designed perturbed push-sum consensus mechanism that aims to track locally the gradient of the (smooth part of the) sum-utility. Sublinear convergence rate is proved when a fixed step-size (possibly different among the agents) is employed whereas asymptotic convergence to stationary solutions is proved using a diminishing step-size. Numerical results show that our algorithms compare favorably with current schemes on both convex and nonconvex problems.
Recommendations
- Distributed convex optimization with coupling constraints over time-varying directed graphs
- Distributed Convex Optimization with Inequality Constraints over Time-Varying Unbalanced Digraphs
- Distributed optimization methods for nonconvex problems with inequality constraints over time-varying networks
- Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs
- Optimal Distributed Convex Optimization on Slowly Time-Varying Graphs
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed Online Convex Optimization on Time-Varying Directed Graphs
- Distributed Continuous-Time Algorithms for Time-Varying Constrained Convex Optimization
- Distributed Continuous-Time Convex Optimization With Time-Varying Cost Functions
- Distributed continuous‐time constrained convex optimization with general time‐varying cost functions
Cites work
- 10.1162/153244303322753751
- A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
- A Proximal Gradient Algorithm for Decentralized Composite Optimization
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Adaptation, learning, and optimization over networks
- ADD-OPT: Accelerated Distributed Directed Optimization
- Alternative Distributed Algorithms for Network Utility Maximization: Framework and Applications
- An affine scaling methodology for best basis selection
- An Approximate Dual Subgradient Algorithm for Multi-Agent Non-Convex Optimization
- Constrained Consensus and Optimization in Multi-Agent Networks
- Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization
- Cooperative Convex Optimization in Networked Systems: Augmented Lagrangian Algorithms With Directed Gossip Communication
- Coordinate descent algorithms
- DC approximation approaches for sparse optimization
- Decentralized Frank–Wolfe Algorithm for Convex and Nonconvex Problems
- Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
- Difference-of-convex learning: directional stationarity, optimality, and sparsity
- Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
- Diffusion LMS Strategies for Distributed Estimation
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed Subgradient Methods for Multi-Agent Optimization
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Fast Distributed Gradient Methods
- Feasible methods for nonconvex nonsmooth problems with applications in green communications
- Gradient Convergence in Gradient methods with Errors
- Harnessing Smoothness to Accelerate Distributed Optimization
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- Minimization of transformed L₁ penalty: theory, difference of convex function algorithm, and robust application in compressed sensing
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- Non-Convex Distributed Optimization
- On Distributed Averaging Algorithms and Quantization Effects
- Optimization methods for large-scale machine learning
- Parallel and Distributed Methods for Constrained Nonconvex Optimization—Part I: Theory
- Parallel Selective Algorithms for Nonconvex Big Data Optimization
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
Cited in
(43)- Distributed optimization methods for nonconvex problems with inequality constraints over time-varying networks
- A distributed continuous-time method for non-convex QCQPs
- A distributed asynchronous method of multipliers for constrained nonconvex optimization
- Distributed convex optimization with coupling constraints over time-varying directed graphs
- Decentralized optimization over tree graphs
- Proximal ADMM for nonconvex and nonsmooth optimization
- Triggered gradient tracking for asynchronous distributed optimization
- Mass-spring-damper networks for distributed optimization in non-Euclidean spaces
- Parallel and distributed successive convex approximation methods for big-data optimization
- 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
- Penalty-based method for decentralized optimization over time-varying graphs
- EFIX: exact fixed point methods for distributed optimization
- Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization
- A two-level distributed algorithm for nonconvex constrained optimization
- Proximal nested primal-dual gradient algorithms for distributed constraint-coupled composite optimization
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- ExtraPush for convex smooth decentralized optimization over directed networks
- Fast decentralized nonconvex finite-sum optimization with recursive variance reduction
- 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
- scientific article; zbMATH DE number 7307473 (Why is no real title available?)
- Decentralized dictionary learning over time-varying digraphs
- Distributed Continuous-Time Convex Optimization With Time-Varying Cost Functions
- An event-triggering algorithm for decentralized stochastic optimization over networks
- Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs
- 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 Fenchel dual gradient method enabling regularization for nonsmooth distributed optimization over time-varying networks
- Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
- Linear convergence rate analysis of a class of exact first-order distributed methods for weight-balanced time-varying networks and uncoordinated step sizes
- Decentralized Gradient Descent Maximization Method for Composite Nonconvex Strongly-Concave Minimax Problems
- Decentralized optimization with affine constraints over time-varying networks
- DIMIX: Diminishing Mixing for Sloppy Agents
- Localization and approximations for distributed non-convex optimization
- Iterative distributed model predictive control for heterogeneous systems with non-convex coupled constraints
- Distributed optimization for economic dispatch with acceleration and privacy preservation over unbalanced directed networks
- A decentralized proximal gradient tracking algorithm for composite optimization on Riemannian manifolds
- Decentralized projected Riemannian gradient method for smooth optimization on compact submanifolds embedded in the Euclidean space
- On graphs with finite-time consensus and their use in gradient tracking
- An improved convergence guarantee for the gradient-push algorithm with a constant stepsize
- Zeroth-order feedback-based optimization for distributed energy management
This page was built for publication: Distributed nonconvex constrained optimization over time-varying digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2425183)
