Electrical and Electronic Engineering - Research Publications
Permanent URI for this collection
Search Results
1 - 6 of 6
-
ItemAn Information Analysis of Iterative Algorithms for Network Utility Maximization and Strategic Games(IEEE, 2019)A variety of resource allocation problems on networked systems, for example, those in cyber-physical systems or Internet-of-things applications, require distributed solution methods. Modern distributed algorithms usually require bandwidth-limited digital communication between the system and its users, who are often modeled as independent decision makers with individual preferences. This paper presents a quantitative information flow and knowledge gain analysis of decentralized iterative algorithms with bounded trajectories in the context of convex network utility maximization problems and strategic games with a unique Nash equilibrium solution. First, a novel generic framework is introduced to quantify knowledge gain in network resource allocation problems using entropy by taking into account priors in the solution space. Second, a general result is presented on the interplay between quantization of information and distributed algorithm performance both for linear and sublinear convergence. Third, information flow in distributed algorithms is studied and a lower bound is derived on the total amount of information exchanged for convergence under uniform quantization. The well-known primal-dual decomposition algorithm is used as an example to illustrate the results. Finally, convergence guarantees for distributed algorithms with estimation are investigated. This paper establishes specific links between information concepts and iterative algorithms in addition to building a foundation for integrating learning schemes into distributed optimization.
-
ItemImpact of quantized inter-agent communications on game-theoretic and distributed optimization algorithms(Springer, 2018-01-01)Quantized inter-agent communications in game-theoretic and distributed optimization algorithms generate uncertainty that affects the asymptotic and transient behavior of such algorithms. This chapter uses the information-theoretic notion of differential entropy power to establish universal bounds on the maximum exponential convergence rates of primal-dual and gradient-based Nash seeking algorithms under quantized communications. These bounds depend on the inter-agent data rate and the local behavior of the agents’ objective functions, and are independent of the quantizer structure. The presented results provide trade-offs between the speed of exponential convergence, the agents’ objective functions, the communication bit rates, and the number of agents and constraints. For the proposed Nash seeking algorithm, the transient performance is studied and an upper bound on the average time required to settle inside a specified ball around the Nash equilibrium is derived under uniform quantization. Furthermore, an upper bound on the probability that the agents’ actions lie outside this ball is established. This bound decays double exponentially with time.
-
ItemLong-Term Stochastic Planning in Electricity Markets Under Carbon Cap Constraint: A Bayesian Game Approach(IEEE, 2016-01-01)Carbon price in an electricity market provides incentives for carbon emission abatement and renewable generation technologies. Policies constraining or penalizing carbon emissions can significantly impact the capacity planning decisions of both fossil-fueled and renewable generators. Uncertainties due to intermittency of various renewable generators can also affect the carbon emission policies. This paper proposes a Cournot-based long-term capacity expansion model taking into account carbon cap constraint for a partly concentrated electricity market dealing with stochastic renewables using a Bayesian game. The stochastic game is formulated as a centralized convex optimization problem and solved to obtain a Bayes-Nash Equilibrium (Bayes-NE) point. The stochastic nature of a generic electricity market is illustrated with a set of scenarios for wind availability, in which three generation firms (coal, gas, and wind) decide on their generation and long-term capacity investment strategies. Carbon price is derived as the dual variable of the carbon cap constraint. Embedding the carbon cap constraint in the game indicates more investment on renewable generators and less on fossil-fueled power plants. However, the higher level of intermittency from renewable generation leads to a higher carbon price to meet the cap constraint. This paves the way towards storage technologies and diversification of distributed generation as means to encounter intermittency in renewable generation.
-
ItemConvergence Analysis of Quantized Primal-dual Algorithm in Quadratic Network Utility Maximization Problems(IEEE, 2015)This paper examines the effect of quantized communications on the convergence behavior of the primal-dual algorithm in quadratic network utility maximization problems with linear equality constraints. In our set-up, it is assumed that the primal variables are updated by individual agents, whereas the dual variables are updated by a central entity, called system, which has access to the parameters quantifying the system-wide constraints. The notion of differential entropy power is used to establish a universal lower bound on the rate of exponential mean square convergence of the primal-dual algorithm under quantized message passing between agents and the system. The lower bound is controlled by the average aggregate data rate under the quantization, the curvature of the utility functions of agents, the number of agents and the number of constraints. An adaptive quantization scheme is proposed under which the primal-dual algorithm converges to the optimal solution despite quantized communications between agents and the system. Finally, the rate of exponential convergence of the primal-dual algorithm under the proposed quantization scheme is numerically studied.
-
ItemLower Bounds on the Best-Case Complexity of Solving a Class of Non-cooperative Games(Elsevier, 2016)This paper studies the complexity of solving the class G of all N-player non-cooperative games with continuous action spaces that admit at least one Nash equilibrium (NE). We consider a distributed Nash seeking setting where agents communicate with a set of system nodes (SNs), over noisy communication channels, to obtain the required information for updating their actions. The complexity of solving games in the class G is defined as the minimum number of iterations required to find a NE of any game in G with ε accuracy. Using information-theoretic inequalities, we derive a lower bound on the complexity of solving the game class G that depends on the Kolmogorov 2ε-capacity of the constraint set and the total capacity of the communication channels. We also derive a lower bound on the complexity of solving games in G which depends on the volume and surface area of the constraint set.
-
ItemPerformance Analysis of Gradient-Based Nash Seeking Algorithms Under Quantization(IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 2016-12-01)This paper investigates the impact of quantized inter-agent communications on the asymptotic and transient behavior of gradient-based Nash-seeking algorithms in non-cooperative games. Using the information-theoretic notion of entropy power, we establish a universal lower bound on the asymptotic rate of exponential mean-square convergence to the Nash equilibrium (NE). This bound depends on the inter-agent data rate and the local behavior of the agents' utility functions, and is independent of the quantizer structure. Next, we study transient performance and derive an upper bound on the average time required to settle inside a specified ball around the NE, under uniform quantization. Furthermore, we establish an upper bound on the probability that agents' actions lie outside this ball, and show that this bound decays double-exponentially with time. Finally, we propose an adaptive quantization scheme that allows the gradient algorithm to converge to the NE despite quantized inter-agent communications.