Distributed optimization increasingly plays a central role in economical and sustainable operation of cyber-physical systems. Nevertheless, the complete potential of the technology has not yet been fully exploited in practice due to communication limitations posed by the real-world infrastructures. This work investigates fundamental properties of distributed optimization based on gradient methods, where gradient information is communicated using a limited number of bits. In particular, a general class of quantized gradient methods are studied, where the gradient direction is approximated by a finite quantization set. Sufficient and necessary conditions are provided on such a quantization set to guarantee that the methods minimize any convex objective function with Lipschitz continuous gradient and a nonempty and bounded set of optimizers. A lower bound on the cardinality of the quantization set is provided, along with specific examples of minimal quantizations. Convergence rate results are established that connect the fineness of the quantization and the number of iterations needed to reach a predefined solution accuracy. Generalizations of the results to a relevant class of constrained problems using projections are considered. Finally, the results are illustrated by simulations of practical systems.
18 June 2018 in IEEE Journal of Selected Topics in Signal Processing
Dual decomposition methods are among the most prominent approaches for finding primal/dual saddle point solutions of resource allocation optimization problems. To deploy these methods in the emerging Internet of Things (IoT) networks, which will often have limited data-rates, it is important to understand the level of communication they require. Motivated by this, we introduce and explore two measures of communication complexity of dual decomposition methods to identify the most efficient communication among these algorithms. The first measure is $\epsilon$-complexity, which quantifies the minimal number of bits needed to find an $\epsilon$-accurate solution. The second measure is b-complexity, which quantifies the best possible solution accuracy that can be achieved from communicating b bits. We find the exact $\epsilon$- and b-complexity of a class of resource allocation problems where a single supplier allocates resources to multiple users. For both the primal and dual problems, the $\epsilon$-complexity grows proportionally to log(1/$\epsilon$) and the b-complexity proportionally to $1/2^b$. We also introduce a variant of the $\epsilon$- and b-complexity measures where only algorithms that ensure primal feasibility of the iterates are allowed. Such algorithms are often desirable because overuse of the resources can overload the respective systems, e.g., by causing blackouts in power systems. We provide upper and lower bounds on the convergence rate of these primal feasible complexity measures. In particular, we show that the b-complexity cannot converge at a faster rate than O(1/b). Therefore, the results demonstrate a trade-off between fast convergence and primal feasibility. We illustrate the result by numerical studies.
As electric power system operators shift from conventional energy to renewable energy sources, power distribution systems will experience increasing fluctuations in supply. These fluctuations present the need to not only design online decentralized power allocation algorithms, but also characterize how effective they are given fast-changing consumer demand and generation. In this paper, we present an online decentralized dual descent (OD3) power allocation algorithm and determine (in the worst case) how much of observed social welfare can be explained by fluctuations in generation capacity and consumer demand. Convergence properties and performance guarantees of the OD3 algorithm are analyzed by characterizing the difference between the online decision and the optimal decision. We demonstrate validity and accuracy of the theoretical results in the paper through numerical experiments using real power generation data.
Typical coordination schemes for future power grids require two-way communications. Since the number of end power-consuming devices is large, the bandwidth requirements for such two-way communication schemes may be prohibitive. Motivated by this observation, we study distributed coordination schemes that require only one-way limited communications. In particular, we investigate how dual descent distributed optimization algorithm can be employed in power networks using one-way communication. In this iterative algorithm, system coordinators broadcast coordinating (or pricing) signals to the users/devices who update power consumption based on the received signal. Then system coordinators update the coordinating signals based on the physical measurement of the aggregate power usage. We provide conditions to guarantee the feasibility of the aggregated power usage at each iteration so as to avoid blackout. Furthermore, we prove the convergence of algorithms under these conditions, and establish its rate of convergence. We illustrate the performance of our algorithms using numerical simulations. These results show that one-way limited communication may be viable for coordinating/operating the future smart grids.
This paper considers a distributed optimization problem in a multi-agent system where a fraction of the agents act in an adversarial manner. Specifically, the malicious agents steer the network of agents away from the optimal solution by sending false information to their neighbors and consume significant bandwidth in the communication process. We propose a distributed gradient-based optimization algorithm in which the non-malicious agents exchange quantized information with one another. We prove convergence of the solution to a neighborhood of the optimal solution, and characterize the solutions obtained in the communication-constrained environment and presence of malicious agents. Numerical simulations to illustrate the results are also presented.