Reliable operation of a power system is contingent on balancing the demand and supply of power at all times. In its simplest abstraction, this balance is achieved by first accepting supply offers and demand bids through a wholesale market. Based on these offers/bids, an optimal dispatch is then computed, subject to the constraints of the underlying grid. The challenge in this operation is twofold: (1) Kirchhoff’s laws render such optimization problems over power networks NP-hard in general, (2) the market is susceptible to gaming, but its equilibrium outcomes are typically hard to characterize.
The hardness in optimizations over power networks stems from the nonconvexity of the feasible sets defined by Kirchhoff’s laws. Formulating them as quadratically constrained quadratic programs (QCQP), we obtain sufficient conditions under which such problems can be optimally solved in polynomial time. In the process, we identify a class of nonconvex QCQPs that are polynomial-time solvable using their semidefinite relaxations. We further explore a unifying framework for other conic programming based relaxations of such problems. Finally, we offer insights into market design in electricity markets using a networked Cournot competition model, focusing on the role of a market maker. Broadly, the aim is to demonstrate the value of optimization and game theory in the design and analysis of modern power systems.