Abstract
The Optimal Power Flow (OPF) problem can be reformulated as a nonconvex Quadratically Constrained Quadratic Program (QCQP). There is a growing body of work on the use of semidefinite programming relaxations to solve OPF. The relaxation is exact if and only if the corresponding optimal solution set contains a rank-one matrix. In this paper, we establish sufficient conditions guaranteeing the nonexistence of a rank-one matrix in said optimal solution set. In particular, we show that under mild assumptions on problem nondegeneracy, any optimal solution to the semidefinite relaxation will have rank greater than one, if the number of equality and active inequality constraints is at least twice the number of buses in the network. The sufficient condition holds for arbitrary network topologies (including tree networks). We empirically evaluate the practical implications of these results on several test cases from the literature.
Introduction
The Optimal Power Flow (OPF) problem is a cornerstone of power systems engineering, aimed at determining the most cost-effective generation and distribution strategy while adhering to physical laws and operational constraints. Mathematically, OPF is a non-convex Quadratically Constrained Quadratic Program (QCQP), making it NP-hard to solve globally.
A prominent technique to address this non-convexity is the Semidefinite Programming (SDP) relaxation. By lifting the problem into a higher-dimensional space of positive semidefinite matrices, the non-convex constraints are replaced by a convex semidefinite constraint. However, the physical validity of the solution depends on the "exactness" of the relaxation—specifically, whether the optimal matrix solution has a rank of one. A rank-one solution can be decomposed into a vector of bus voltages, whereas a higher-rank solution lacks a direct physical interpretation. While much previous research has focused on finding cases where SDP relaxations work, this paper investigates the theoretical bounds that guarantee inexactness.
Theoretical Framework: The "2n" Rule
The core contribution of this research is the establishment of a sufficient condition for the failure of SDP relaxations. Leveraging the theory of nondegeneracy in semidefinite programs, the authors define primal and dual nondegeneracy based on the linear independence of constraint matrices and the uniqueness of optimal solutions.
The primary theoretical result, Theorem 2, connects the rank of the optimal solution to the number of active constraints. It states that for a primal nondegenerate optimal solution $X^\circ$, if the sum of equality constraints ($m$) and active inequality constraints ($a(X)$) is greater than or equal to twice the number of buses ($n$), then every optimal solution must have a rank greater than one. Specifically, if $m + a(X) \ge 2n$, a rank-one solution is mathematically impossible under mild nondegeneracy assumptions.
In the context of OPF, equality constraints typically arise from power balance equations, while active inequality constraints often stem from voltage magnitude limits or line flow limits being met exactly at the optimum.
Empirical Validation on Standard Benchmarks
The researchers evaluated several standard power system benchmarks to determine if practical operating conditions trigger these inexactness criteria. The systems analyzed ranged from small 3-bus networks to larger IEEE 118-bus systems.
As shown in Table I, several well-known cases from the literature satisfy the conditions for inexactness. For instance, in the IEEE 118-bus system, the number of constraints ($m + a(X)$) significantly exceeds the $2n$ threshold, resulting in a rank-2 solution. This confirms that inexactness is not merely a theoretical curiosity but a characteristic of many standard test cases.
Challenging the Radial Network Assumption
A common heuristic in power systems is that radial (tree-shaped) distribution networks are more likely to yield exact SDP relaxations than meshed transmission networks. This paper provides a significant "reality check" for this assumption using the IEEE 34-node radial test feeder.
Through a parametric study of the 34-node feeder, the authors found that 93.69% of tested load profiles resulted in inexact solutions. This high failure rate suggests that specific load profiles and tight voltage constraints can easily force the relaxation into a higher-rank space, even without cycles in the network topology. The study also clarifies that "load over-satisfaction" is often necessary to force exactness because strict power balance equality constraints are a primary driver of the $2n$ rule violation.
Conclusion and Future Outlook
This work establishes that SDP relaxations for OPF are highly susceptible to inexactness when the number of active constraints is high relative to the number of buses. While the results rely on the assumption of primal nondegeneracy, this is considered a generic property of most problem instances.
The findings have particular implications for distribution networks, which typically have few controllable generators ($n_G \ll n$). These systems are mathematically predisposed to satisfy the inexactness conditions identified here. However, as power systems evolve to include more distributed energy resources (DERs), the ratio of controllable nodes to total nodes will increase, potentially expanding the regime where SDP relaxations can provide exact, physically meaningful solutions.
Summary updated