Optimal Power Flow as a Polynomial Optimization Problem

1 Introduction

• Polynomial programming models network equations and operating limits, while accommodating varied objectives and added constraints without affecting convergence properties.Source: §1 · pp. 1–2
• Lasserre’s SDP hierarchy strengthens relaxations, but its dimensions grow rapidly with power-system size.Source: §1 · p. 2
• Dynamic cutting surfaces add valid polynomial inequalities while keeping certificate degree fixed, yielding tighter bounds than Lavaei-Low.Source: §1 · p. 2
• Sparse Lasserre relaxations exploit OPF sparsity; matrix completion splits the largest SDP into smaller inequalities, at the cost of added equalities, to target systems with thousands of buses.Source: §1 · p. 2
• Structured sparsity lets the sparse hierarchy solve larger instances globally than prior literature, and the paper proves convergence of its SDP relaxations.Source: §1 · p. 2
• Either proposed technique improves on the Lavaei-Low SDP relaxation whenever that relaxation misses the global optimum.Source: §1 · p. 2

2 Optimal Power Flow Problem

• The power-system topology is an undirected graph, with buses as vertices and branches as edges.Source: §2 · p. 2
• The formulation tracks bus demands and generation, complex bus voltages, and apparent branch flows, with L marking lines subject to a flow limit.Source: §2 · pp. 2–3

2.1 Formulation

• In the rectangular formulation, x contains real and imaginary bus-voltage components, and generation-cost functions provide the objective.Source: §2.1 · p. 3
• The classical OPF is a degree-four polynomial optimization problem; setting W=xxT and dropping the rank constraint yields an SDP relaxation.Source: §2.1 · pp. 3–4

3 Polynomial Programming Approach

• Lasserre’s SDP hierarchy builds progressively stronger relaxations of polynomial programs, but their size can become computationally challenging as degree and dimension grow.Under assumptions slightly stronger than compactness, the hierarchy’s optimal values converge to the global optimum.Source: §3 · p. 4

3.1 Relationship with Lavaei-Low Formulation

• The degree-two OPF formulation has a first-level relaxation equivalent to the dual of the Lavaei–Low SDP formulation.Its first-level bound matches the Lavaei–Low bound, while the degree-four formulation’s first-level bound is at least as good.Source: §3.1 · p. 5

3.2 Inequality Generation Approach

• Dynamic inequality generation adds valid, violated polynomial inequalities while keeping certificate degree fixed, improving approximations without growing the SDP problem’s degree.A master problem supplies lower bounds, and a subproblem generates valid inequalities from its dual information.Source: §3.2 · pp. 5–6
• Adding valid inequalities to the degree-two relaxation can improve the Lavaei–Low bound and, in some cases, yield the global optimum.Unlike increasing hierarchy order, this approach increases the feasible-region inequalities while keeping polynomial degree fixed.Source: §3.2 · p. 6

3.3 Exploiting OPF Structure

• The sparse hierarchy exploits correlative sparsity by assigning constraints to maximal-clique variable sets and using clique-supported sum-of-squares polynomials.The chosen chordal extension affects clique sizes, which determine the sizes of the hierarchy’s matrix inequalities.Source: §3.3 · pp. 6–7
• For fixed order, the sparse hierarchy can be weaker than the dense hierarchy, but under Assumption 1 its primal and dual optimal values converge to the OPF optimum as order increases.The paper states that Assumption 1 is satisfied for both degree-two and degree-four formulations.Source: §3.3 · p. 7
• For the degree-four sparse hierarchy, nonempty feasible-set interior ensures no duality gap; a unique global minimizer also yields convergence of solution components as order grows.The stated no-duality-gap result also applies to the first-order degree-two sparse relaxation.Source: §3.3 · pp. 7–8
• At order one, the degree-two sparse relaxation is equivalent to the dense first-order relaxation and the Lavaei–Low dual SDP relaxation.When the polynomial program is very sparse, the sparse hierarchy’s variable and matrix sizes can be much smaller than the dense hierarchy’s.Source: §3.3 · p. 8

4 Numerical Results

• The experiments first iteratively improve [OP2-H1]* with DIGS and then use polynomial-program sparsity for higher-order relaxations.The small test cases were chosen because the Lavaei-Low relaxation is not optimal.Source: §4 · p. 8, §4.1 · p. 8

4.1 Small-scale Instances

• On the two-bus WB2 cases, DIGS improves the Lavaei-Low bound after one inequality and reaches the optimum in 8 iterations.MATPOWER converged on none of the 9 instances; for V max 2 =1.022, the reported value is 713.27.Source: §4.1 · p. 8, Figure 2 · p. 9
• For LMBM3, both approaches find optimal solutions where Lavaei-Low is not exact, while MATPOWER reports optimal solutions on all 10 instances..Source: §4.1 · p. 10, Table 2 · p. 10
• For the 5-bus cases, DIGS and sparsity-based methods solve all test cases to optimality, and MATPOWER reports optimal solutions on all 8 instances.Source: §4.1 · p. 10, Table 3 · p. 11

4.2 Large-scale Instances

• For instances up to 2736 buses, [OP2-H1]* can be solved within an hour, while generating cutting surfaces becomes too time-consuming.For instances larger than 39 buses, [OP2-H1]* can be solved, whereas [OP4-SH1] becomes computationally expensive for SparsePoP.Source: §4.2 · p. 11
• For case9mod, DIGS proves optimality in 3 hours and 7 iterations; for case14mod, it improves the Lavaei-Low bound after 2 iterations within 5 hours.The large-instance comparison also reports [OP2-H1]* with SparseColO and [OP4-SH1] with SparsePoP.Source: §4.2 · pp. 10–11, Table 4 · p. 11

• For several instances up to 39 buses where Lavaei-Low is not exact, the approaches provide globally optimal solutions for the first time.Source: §5 · p. 11
• The paper reports that its strong relaxations are tractable for medium- and large-scale instances.Source: §5 · p. 11
• The approaches allow arbitrary multivariate polynomial objectives and constraints, and can include binary variables for discrete decisions such as transmission switching.Source: §5 · p. 11