eess.SYOct 17, 2026

Low-Bit Distributed Constrained Optimization with Application to Optimal Scheduling and Allocation

Authors: Mohammadreza Doostmohammadian, Sergio Pequito

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

This paper proposes a distributed resource allocation algorithm in which each agent communicates only the sign of its local cost gradient, a single bit per directed link per iteration. The algorithm is based on Laplacian-gradient dynamics and preserves the equality (demand) constraint at every iterate, guaranteeing anytime feasibility irrespective of termination time. First, we provide a complete Lyapunov-based convergence analysis for the fixed-step-size regime: the iterates are shown to enter, in at most O(1/\varepsilon^2) iterations, a neighborhood of the optimizer whose radius scales as O(τ) in the decision variable and O(τ^2) in the cost residual, where ττ is the step-size. Crucially, the step-size bound is a time-invariant network constant (depending only on the graph Laplacian spectrum and the cost curvature bounds), so no adaptive tuning is required. Second, we characterize the invariant set under B-connected, weight-balanced digraphs, strictly weaker than the all-time connectivity and doubly-stochastic weights assumed in most prior work, and show that any odd, sign-preserving nonlinearity yields the same invariant-set and descent structure, with the single-bit protocol being the extreme communication-minimizing instance of a broader nonlinear class. Third, we address local box constraints via smooth penalty relaxation and quantify explicitly how the penalty weight interacts with the step-size bound and the optimality gap. Simulations on economic dispatch (1000 generators) and CPU scheduling (500 servers) demonstrate that the single-bit protocol achieves 5-60 times reduction in total communication cost relative to multi-bit baselines, at the price of a tunable and explicitly bounded optimality gap. A diminishing step-size schedule is shown empirically to eliminate this gap; its formal convergence analysis is identified as an open problem.

Figures & tables

SymbolDescription
fif_{i} , FFlocal and global objective
xix_{i}state variable of agent ii
x\mathbf{x}global state variable
nnnumber of nodes/agents
bbaggregate demand
ν\nu , μ\mustrong convexity and Lipschitz constant
Table 1: Summary of the key notations in the paper.
AlgorithmRun timeOptimizationInitialization
Single-bit (Alg. 1 )0.0661 s0.0614 s0.0047 s
Log-quantized [ 40 ]0.1981 s0.1934 s0.0047 s
Linear [ 35 ]0.0640 s0.0593 s0.0047 s
Table 2: Comparison on the n=8n{=}8 time-varying network over 1000010000 iterations ( τ=0.0001\tau{=}0.0001 ).
Figure 1: (Left) Optimality residual F‾(k)\overline{F}(k) for the single-bit algorithm versus the linear method [ 35 ] and log-quantized method [ 40 ] . The single-bit residual floor is consistent with Theorem 1 (iii). (Right) Fixed step-size τ=0.01\tau=0.01 versus diminishing τ(k)=0.05/k\tau(k)=0.05/k ; the diminishing schedule drives the residual below the fixed- τ\tau floor.
AlgorithmRun timeOptimizationInitialization
Single-bit (Alg. 1 )11.26 s10.67 s0.59 s
Linear [ 36 ]11.07 s10.48 s0.59 s
Accelerated [ 50 ]11.41 s10.82 s0.59 s
Finite-time [ 26 ]24.96 s24.37 s0.59 s
Fixed-time [ 46 ]38.39 s37.80 s0.59 s
Saturated [ 43 ]11.58 s10.99 s0.59 s
Table 3: Economic dispatch ( n=1000n{=}1000 , τ=0.1\tau{=}0.1 , kmax⁡=1000k_{\max}{=}1000 iterations).
Figure 2: (Left) Optimality residual for the EDP: Algorithm 1 versus five multi-bit baselines. (Right) Power states xi(k)x_{i}(k) at all generators and their average 1n∑ixi(k)=b/n\frac{1}{n}\sum_{i}x_{i}(k)=b/n , confirming anytime feasibility (Lemma 6 ).
AlgorithmRun timeInitializationOptimization
Single-bit (Alg. 1 )5.81 s0.21 s5.60 s
Log-quant. [ 40 ]21.58 s0.21 s21.37 s
Uniform-quant. [ 1 ]8.86 s0.21 s8.65 s
Table 4: CPU scheduling ( n=500n{=}500 , τ=1\tau{=}1 , kmax⁡=10 000k_{\max}{=}10\,000 ). Comparison of the computational complexity for the cost given by ( 46 ).
Figure 3: (Left) Optimality residual for CPU scheduling: Algorithm 1 versus log-quantized [ 40 ] and uniformly-quantized [ 1 ] methods. (Right) Allocated workloads xi(k)x_{i}(k) at all servers and their average, confirming anytime feasibility (Lemma 6 ).
More in this topic

Distributed Optimization

Distributed optimization coordinates computation across multiple agents or machines while balancing convergence, communication, privacy, and reliability.

See all 92 papers

Explore similar work

CardsList
Jul 28, 2026

Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling

Distributed constraint optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too large to solve monolithically. We address this challenge from two complementary directions. We revisit the connection between DCOPs and potential games, and adapt modern online learning algorithms for equilibrium finding to DCOPs. We show that these algorithms are competitive with representative incomplete DCOP algorithms. We then turn to decomposition frameworks for large-scale DCOPs, motivated by large-scale decentralized satellite scheduling. We propose a new framework that separates a DCOP into two interacting subproblems: a high-level meta-DCOP for task allocation, and independent local optimization problems for scheduling. To couple the two levels, we develop a novel iterative pricing method that updates the meta-level utilities using feedback from the local optimizers. Combining our online learning methods with our iterative pricing framework, we obtain near-optimal performance on real-world decentralized satellite scheduling problem instances, fulfilling over 99% of observation requests compared with 87% for state-of-the-art baselines.

Itai Zilberstein, Pranav Rajbhandari, Steve Chien +1

Department of Computer Science, Carnegie Mellon University · Jet Propulsion Laboratory, California Institute of Technology · Additional affiliations: Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc.

Distributed OptimizationPotential GamesConstrained OptimizationOnline Learning
AskPDF
Oct 17, 2026

Adding Heavy-Ball Momentum to Distributed Constrained Optimization for Energy Resource Management Subject to Time-Delays and Quantization

This paper studies a hybrid discrete-time signed gradient-consensus method with heavy-ball momentum, paired communication delays, and fixed logarithmic quantization. The method preserves the aggregate supply-demand equality at every iteration. For a static connected undirected graph and bounded delays, a Lyapunov-Krasovskii analysis establishes practical stability by isolating the discontinuous quantization error as an additive disturbance and closing a computable invariant-sublevel argument. The resulting ergodic residual bound is quadratic in the quantization resolution, and exact convergence to the smooth penalized equality-constrained optimizer is recovered in the unquantized case. For delay-free unquantized quadratic costs, an exact modal analysis identifies the heavy-ball stability region and optimal parameters, with the predicted rate validated on a fixed sparse network. A reproducible delayed experiment reports all constants and a certificate whose guaranteed steady-state level lies below the reported initialization. A separate mixed generator-battery experiment exercises the signed update directly. Finite smooth penalties approximate, but do not generally enforce, the local box constraints exactly.

Mohammadreza Doostmohammadian, Sergio Pequito

Distributed OptimizationConstrained OptimizationDecentralized OptimizationSign-Based OptimizationMomentum Methods
AskPDF
Jul 13, 2026

Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity

Decentralized gradient descent (DGD) is widely used for solving distributed optimization problems over networks of agents. While its convergence properties are well understood, less is known about the communication and computation resources required to attain a prescribed accuracy. In this paper, we study DGD from a resource-aware perspective and characterize the communication-computation budget required to attain a target error level. We develop a bottleneck-centric framework in which different factors dominate the optimization dynamics at different error scales. Specifically, we identify operating regimes governed by initialization, objective heterogeneity and network connectivity, gradient noise, and communication noise. To capture these effects, we introduce two fundamental quantities: the gradient-Diversity-to-Network-connectivity Ratio (DNR) and the Gradient-to-Communication-noise Ratio (GCR). We show that these quantities determine the sequence of bottlenecks encountered during optimization and the corresponding budget-optimal operating strategy. Using a multi-stage analysis, we derive optimal stepsize selections and explicit budget-complexity bounds that quantify the budget resources required to attain a prescribed accuracy. The resulting expressions reveal how the overall budget decomposes into contributions associated with successive bottlenecks and provide insight into the fundamental tradeoffs among objective heterogeneity, network connectivity, gradient noise, and communication noise.

Nicolò Michelusi

School of Electrical, Computer and Energy Engineering, Arizona State University.

Distributed OptimizationStochastic Optimization ConvergenceDecentralized Optimization
AskPDF