Near-Global Solutions of Nonlinear Mixed-Integer Power Optimization Problems: Theory, Numerical Algorithm, and Case Studies

Javad Lavaei
University of California, Berkeley (UC Berkeley)

In this talk, we study the potentials of semidefinite programming (SDP) relaxations for nonlinear mixed-integer power optimization problems such as the power flow problem, security-constrained optimal power flow, and unit commitment. The existence of a rank-1 matrix solution to the SDP relaxation enables the recovery of a global solution of the original problem. We show that real-world power networks have low treewidth, and as a result the SDP relaxation always has a low-rank solution. By leveraging this property, we design a penalized SDP relaxation to reduce the rank to 1, leading to a near-global solution. As a case study, we demonstrate that the proposed relaxation is able to find feasible solutions for the optimal power flow problem for various IEEE and Polish test systems with a global optimality guarantee of at least 99%. Moreover, we propose a low-computation distributed algorithm to solve the penalized SDP relaxation. Unlike the existing second-order methods that cannot handle large SDP problems, our approach leverages the low treewidth of power grids and develops a very efficient numerical algorithm. For example, solving an SDP relaxation over the NY Grid using the proposed algorithm requires only a series of eigenvalue decompositions over small matrices of size at most 40, which runs very fast.

The unit commitment (UC) is a mixed-integer nonlinear program and the existing algorithms mostly rely on solving a series of convex relaxations by means of branch-and-bound or cutting planning methods. We show that the classical SDP performs as poorly as the basis linear programming relaxation, and they both lead to high optimality gaps in many examples. We then develop a strengthened SDP relaxation of UC problem and test its performance on several examples. We study some hard instances of the UC problem for which the globally optimal discrete and continuous parameters of the UC problem are found by solving the proposed convex problem only once. To handle a general security-constrained unit-commitment problem, we propose a two-step procedure. First, we design a simple pre-processing algorithm to reduce the size of the problem without affecting the solution of the problem. For example, we show that the size of the problem could reduce from 96,000,000 constraints to a few thousand conditions for ERCOT. Second, we convexify the problem using the proposed strengthened SDP.

Back to Optimization and Equilibrium in Energy Economics