Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems

Abstract

We propose a novel decomposition framework for the distributed optimization of general nonconvex sum-utility functions arising naturally in the system design of wireless multiuser interfering systems. Our main contributions are: i) the development of the first class of (inexact) Jacobi best-response algorithms with provable convergence, where all the users simultaneously and iteratively solve a suitably convexified version of the original sum-utility optimization problem; ii) the derivation of a general dynamic pricing mechanism that provides a unified view of existing pricing schemes that are based, instead, on heuristics; and iii) a framework that can be easily particularized to well-known applications, giving rise to very efficient practical (Jacobi or Gauss-Seidel) algorithms that outperform existing adhoc methods proposed for very specific problems. Interestingly, our framework contains as special cases well-known gradient algorithms for nonconvex sum-utility problems, and many blockcoordinate descent schemes for convex functions.

submitted to IEEE Transactions on Signal Processing

References in corpus (3)

• Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems based on Game Theory-Part I: Nash Equilibria
• Signal Processing and Optimal Resource Allocation for the Interference Channel
• Decomposition by Successive Convex Approximation: A Unifying Approach for Linear Transceiver Design in Heterogeneous Networks

Cited by in corpus (62)

• Joint Optimization of Radio and Computational Resources for Multicell Mobile-Edge Computing
• Group Sparse Regularization for Deep Neural Networks
• Optimization Methods for Designing Sequences with Low Autocorrelation Sidelobes
• Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications
• Sequence Design to Minimize the Weighted Integrated and Peak Sidelobe Levels
• Joint Precoding and Multivariate Backhaul Compression for the Downlink of Cloud Radio Access Networks
• Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
• Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization
• Parallel Selective Algorithms for Big Data Optimization
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Decentralized Quasi-Newton Methods
• A Parallel Stochastic Approximation Method for Nonconvex Multi-Agent Optimization Problems
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
• A Unified Successive Pseudo-Convex Approximation Framework
• Robust Matrix Completion via Maximum Correntropy Criterion and Half Quadratic Optimization
• Inexact Block Coordinate Descent Algorithms for Nonsmooth Nonconvex Optimization
• Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization
• Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance
• Sparse Generalized Eigenvalue Problem via Smooth Optimization
• Blockage-aware Reliable mmWave Access via Coordinated Multi-point Connectivity
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• CellOS: Zero-touch Softwarized Open Cellular Networks
• Parallel and Distributed Methods for Nonconvex Optimization-Part I: Theory
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
• Iteration Complexity Analysis of Block Coordinate Descent Methods
• Local Stackelberg equilibrium seeking in generalized aggregative games
• Low-Complexity Robust MISO Downlink Precoder Design With Per-Antenna Power Constraints
• Energy efficiency optimization in MIMO interference channels: A successive pseudoconvex approximation approach
• WNOS: An Optimization-based Wireless Network Operating System
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• Distributed Nonconvex Multiagent Optimization Over Time-Varying Networks
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling
• An Online Parallel and Distributed Algorithm for Recursive Estimation of Sparse Signals
• On Nonconvex Decentralized Gradient Descent
• Decomposition by Successive Convex Approximation: A Unifying Approach for Linear Transceiver Design in Heterogeneous Networks
• Reconfigurable Intelligent Surface Enabled Federated Learning: A Unified Communication-Learning Design Approach
• Latency-Constrained Highly-Reliable mmWave Communication via Multi-point Connectivity
• Uncrewed Vehicles in 6G Networks: A Unifying Treatment of Problems, Formulations, and Tools
• NEXT: In-Network Nonconvex Optimization
• Joint Transmission with Limited Backhaul Connectivity
• Solving High-Order Portfolios via Successive Convex Approximation Algorithms
• Cooperative Network Node Positioning Techniques Using Underwater Radio Communications
• Stochastic Difference-of-Convex Algorithms for Solving nonconvex optimization problems
• Cross Layer Provision of Future Cellular Networks
• Distributed Stochastic Nonconvex Optimization and Learning based on Successive Convex Approximation
• Escaping Saddle Points with the Successive Convex Approximation Algorithm
• Computing B-Stationary Points of Nonsmooth DC Programs
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• On the Pervasiveness of Difference-Convexity in Optimization and Statistics
• Decentralized Dictionary Learning Over Time-Varying Digraphs
• Content-Aware User Association and Multi-User MIMO Beamforming over Mobile Edge Caching
• A New Distributed DC-Programming Method and its Applications
• Transforming physics-informed machine learning to convex optimization
• WNOS: Enabling Principled Software-Defined Wireless Networking
• Strong Duality in Nonconvex Quadratic Problems with Separable Quadratic Constraints
• An Adaptive Partial Linearization Method for Optimization Problems on Product Sets
• Design of RIS-aided mMTC+ Networks for Rate Maximization under the Finite Blocklength Regime with Imperfect Channel Knowledge
• Applications of Economic and Pricing Models for Wireless Network Security: A Survey
• A Parallel Best-Response Algorithm with Exact Line Search for Nonconvex Sparsity-Regularized Rank Minimization
• New Algorithms for Maximizing Cellular Wireless Network Energy Efficiency
• Resource Management in Cloud Networking Using Economic Analysis and Pricing Models: A Survey