PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparsity-Exploiting Moment-Based Relaxations of the Optimal Power Flow Problem

Daniel K. Molzahn, Ian A. Hiskens

arXiv:1404.5071v2math.OC

TL;DR

Non-convex OPF problems can defeat local methods and existing convex relaxations that fail to produce physically meaningful global solutions. This paper develops Lasserre-based moment relaxations and a sparsity-exploiting iterative algorithm that applies higher-order constraints selectively. The approach globally solves many such test systems, including systems up to 300 buses, while retaining a computational cost that grows with relaxation order.

  • Problem

    Non-convex OPF problems can cause local methods to fail or return local optima, while semidefinite relaxations may fail to provide physically meaningful solutions when their rank condition is not satisfied.

  • Method

    The paper develops Lasserre-hierarchy moment relaxations and an iterative sparse algorithm that applies computationally intensive higher-order constraints only to selected buses.

  • Results

    The algorithm globally solves many test systems with up to 300 buses for which existing convex relaxations fail to yield globally optimal solutions.

  • Takeaways & Limitations

    Low-order moment relaxations solve many small difficult OPF problems, while selective higher-order enforcement makes global solution of larger problems computationally tractable.

  • Takeaways & Limitations

    Realistic test cases where low-order relaxations fail remain an important direction for future research, and sufficient tightness conditions would be valuable.

Abstract

from arXiv · show

Convex relaxations of non-convex optimal power flow (OPF) problems have recently attracted significant interest. While existing relaxations globally solve many OPF problems, there are practical problems for which existing relaxations fail to yield physically meaningful solutions. This paper applies moment relaxations to solve many of these OPF problems. The moment relaxations are developed from the Lasserre hierarchy for solving generalized moment problems. Increasing the relaxation order in this hierarchy results in "tighter" relaxations at the computational cost of larger semidefinite programs. Low-order moment relaxations are capable of globally solving many small OPF problems for which existing relaxations fail. By exploiting sparsity and only applying the higher-order relaxation to specific buses, global solutions to larger problems are computationally tractable through the use of an iterative algorithm informed by a heuristic for choosing where to apply the higher-order constraints. With standard semidefinite programming solvers, the algorithm globally solves many test systems with up to 300 buses for which the existing semidefinite relaxation fails to yield globally optimal solutions.

I. INTRODUCTION

OPF is non-convex, so local methods may fail to converge or return local optima, while existing semidefinite relaxations can lack physically meaningful solutions. The paper introduces moment relaxations and sparse higher-order methods to recover global solutions while managing computational cost.

  • OPF combines nonlinear power-flow equalities with engineering limits, making the problem generally non-convex and potentially locally solvable.
  • Local OPF methods can fail to converge or converge to local optima, including on large systems where they remain computationally tractable.
  • Exact semidefinite relaxations can provide polynomial-time global solutions, but failed rank conditions leave only lower bounds without physically meaningful voltage phasors.
  • Moment relaxations globally solve a broader class of OPF problems by exploiting their polynomial structure, including cases where existing relaxations are not exact.
  • Higher-order moment relaxations substantially increase matrix size; for a 10-bus system, second- and third-order matrices are 231×231 and 1771×1771 versus 20×20 for the semidefinite relaxation.
  • A second-order relaxation finds the global solution for a 9-bus problem where local optima are 10.0%, 37.5%, and 38.1% above global optimum and the semidefinite lower bound is 11% below it.

A. Overview

The paper converts polynomial OPF constraints into semidefinite moment and localizing matrix constraints. Increasing relaxation order strengthens the approximation but expands the monomial basis and semidefinite programs.

  • A. Overview: OPF can be treated as polynomial optimization because its formulation consists of polynomial functions of rectangular voltage components.
  • A. Overview: For bounded OPF variables, increasing relaxation order approaches the global solutions of the underlying polynomial optimization problem.
  • A. Overview: Moment relaxations replace polynomial monomials with scalar moment variables through a linear functional applied term by term.
  • A. Overview: The order-γ relaxation includes all voltage-component monomials through degree γ, while its moment matrix contains entries through degree 2γ.
  • A. Overview: Localizing matrices encode polynomial inequality constraints as positive-semidefinite conditions built from moment variables.
  • A. Overview: The moment relaxation is a semidefinite program with normalization, angle-reference, and positive-semidefinite moment-matrix constraints.

B. Two-Bus Example

The two-bus example illustrates a case where the first-order relaxation is not exact but the second-order moment relaxation recovers the global solution. The example also exposes the practical role of voltage-magnitude constraints in the relaxation.

  • B. Two-Bus Example: The example is a two-bus system with bus-voltage magnitude limits of [0.95, 1.05] and [0.95, 1.02] per unit.
  • B. Two-Bus Example: The system has three degrees of freedom, allowing its feasible space to be visualized in three dimensions.
  • B. Two-Bus Example: The first-order moment relaxation is not exact despite the system’s radial network topology and therefore does not satisfy the cited sufficient exactness conditions.
  • B. Two-Bus Example: The second-order relaxation yields the global voltage solution for the two-bus OPF problem.
  • B. Two-Bus Example: The reported global operating point has generation of 456.6 MW and 162.3 MVAr at bus 1, with an operating cost of 456.55 $/MWh.

C. Implementation Details

Implementation details reduce redundancy in moment relaxations and recover OPF solutions from their semidefinite representations. Equality-constrained polynomials can be imposed through linear moment constraints instead of positive-semidefinite matrix constraints.

  • C. Implementation Details: The implementation addresses solution recovery, linear dependencies, unnecessary matrix portions, and reformulations of cost and line-flow constraints.
  • C. Implementation Details: Equality-constrained polynomials produce linear constraints in moment variables because their localizing matrices are forced to zero.

1) Equality-Constrained Polynomials:

Equality-constrained polynomials are handled through vector constraints that remove redundant localizing-matrix equalities. The resulting moment relaxation recovers a global solution when its rank condition holds; otherwise it yields a lower bound or may require a higher order.

  • Equality-constrained polynomials: Equality-constrained polynomial localizing matrices are replaced by the equivalent vector constraints Ly {g (x̂) xγ−1} = 0.This eliminates linearly dependent equality constraints caused by repeated symmetric matrix entries.
  • Solution extraction: A rank-one moment matrix permits extraction of a single globally optimal solution by spectral decomposition of its second-order block.The extracted voltage phasor vector is the globally optimal decision vector.
  • Exactness and bounds: If the relaxation is not exact, it provides only a lower bound, while increasing the order may improve the bound and produce a global solution.Multiple global solutions instead require a separate solution-extraction procedure.
  • Computational reduction: Positive semidefinite constraints are reduced to diagonal blocks associated with even-order monomials, decreasing the semidefinite program’s computational burden.Odd-order off-diagonal blocks and duplicated even-order terms are omitted.
  • First-order relaxation: After first-order monomials are eliminated, the first-order relaxation contains only second-order monomials and scalar positivity constraints.This makes the first-order moment relaxation equivalent to the existing semidefinite relaxation.

4) Quadratic Cost Function and Apparent-Power Line-FLow Limits:

The relaxation order must accommodate the polynomial degrees in OPF constraints, while reformulations can reduce the required order and improve computational behavior. Higher-order moment relaxations offer broader exactness but become rapidly more expensive, motivating sparse and selective formulations.

  • Relaxation order: The relaxation order γ must be at least half the degree of every OPF polynomial, although reformulations can lower the required order.For example, a reformulated OPF with linear cost and without apparent-power limits requires γ ≥1.
  • Global solution: The moment approach preserves global optimality when exact while addressing OPF cases where existing relaxations are not exact.This contrasts with heuristics that can lose a global-optimality guarantee.
  • Sparsity: Second-order relaxations are computationally tractable for systems with approximately forty buses after matrix completion decomposition.Direct implementation is tractable only for second-order problems with up to ten buses.
  • Selective higher-order constraints: For larger systems, selective second- and third-order relaxations applied to specific buses make OPF problems of up to 300 buses solvable with standard semidefinite programming solvers.The approach exploits regions where the first-order relaxation is sufficient.

A. Matrix Completion Decomposition

Matrix completion decomposition exploits graph sparsity by replacing one large moment constraint with smaller clique-based constraints. Shared clique entries must agree, and rank conditions determine whether the decomposed solution yields recoverable global voltages.

  • Graph construction: The power-system graph is chordally extended so maximal cliques can be identified and used for decomposition.A Cholesky factorization of D + I produces the extension, with approximate minimum-degree ordering limiting added edges.
  • Matrix completion: The matrix completion theorem replaces one large positive semidefinite moment constraint with constraints on smaller matrices associated with maximal cliques.Localizing matrices are similarly reduced using each bus’s smallest covering maximal clique.
  • Clique coverage: The decomposition graph includes each bus and its neighbors within a maximal clique, ensuring higher-order moment variables are well-defined.This graph differs subtly from decompositions that directly use the original network topology.
  • Consistency: Shared entries among overlapping decomposed moment matrices are constrained to be equal.This consistency condition is required because maximal cliques intersect.
  • Solution recovery: A globally optimal voltage vector can be recovered when every decomposed moment matrix satisfies the required rank-one condition.Failure may indicate non-exactness or multiple global solutions; the objective then remains a lower bound.

B. Selective Application of Higher-Order Constraints

Selective higher-order constraints exploit the fact that first-order relaxations are usually adequate at most buses, while a few problematic buses receive higher orders. This preserves tractability for substantially larger OPF systems.

  • Matrix completion baseline: Second-order relaxations of OPF problems with up to approximately forty buses become tractable after matrix completion decomposition.This provides the sparse baseline for extending the method to larger systems.
  • Heuristic evaluation: A closest rank-one matrix is used to obtain a voltage vector from the moment-relaxation solution before evaluating bus mismatches.The matrix minimizes Frobenius-norm distance to the higher-rank moment matrix.
  • Motivation: First-order relaxations usually produce small injection mismatches at most buses and large mismatches at only a few buses.The mismatch pattern motivates assigning higher orders selectively rather than uniformly.
  • Order assignment: Each bus receives its own relaxation order γk, and each clique uses the highest order assigned to its covered buses.Power-injection and voltage constraints use bus-specific orders, while line-flow constraints use the higher terminal-bus order.
  • Selective application: Selective higher-order constraints make large OPF problems tractable by applying computationally intensive orders only where necessary.The majority of buses can remain at a computationally tractable relaxation order.

C. Iterative Solution Algorithm with a Heuristic for Determining the Relaxation Order

The algorithm iteratively solves a moment relaxation, checks power-injection mismatches and feasibility criteria, and selectively raises relaxation orders at buses with the largest mismatches. Its heuristic balances iteration count against per-iteration matrix size, while global optimality is accepted only when specified tolerances are satisfied.

  • Algorithm 1: The algorithm initializes every bus at relaxation order one, solves the moment relaxation, and computes power-injection mismatches.If tolerances are met, it recovers the optimal voltage profile using an eigen decomposition of the second-order monomial block.
  • Algorithm 1: Relaxation orders are increased at a subset of buses with the greatest power-injection mismatches when the current solution fails tolerance criteria.The buses with the greatest mismatches can change as the relaxation order increases, requiring multiple iterations.
  • Convergence criteria: A voltage vector is accepted only when injection mismatches, inequality constraints, and the objective value satisfy specified tolerances.The objective evaluated at the voltage vector must match the moment-relaxation optimum within tolerance.
  • Heuristic for determining the relaxation order: The heuristic increments orders at up to h buses with the largest mismatches, prioritizing buses below the current maximum order before increasing that maximum.This avoids unnecessarily enlarging moment matrices while targeting buses whose mismatches exceed tolerance.
  • Heuristic for determining the relaxation order: Choosing h trades off faster iterations against fewer iterations, and experience indicates that h = 2 provides a good balance.Larger h can reduce iteration count but make each iteration slower; smaller h has the opposite trade-off.
  • Heuristic for determining the relaxation order: The proposed mismatch-based heuristic is one possible strategy, and the paper identifies comparison with alternative approaches as future work.The authors also note that further analysis is needed for varying h.

V. NUMERICAL RESULTS

The numerical results show that selective higher-order moment constraints can globally solve many OPF test problems where the first-order relaxation fails, while computational cost varies substantially across cases. The experiments also identify cases where the heuristic requires many higher-order buses or iterations, limiting tractability.

  • Second- and third-order moment relaxations are exact for the tested problems, recovering globally minimal objectives and globally optimal decision variables.
  • The first-order relaxation often produces objective values close to the global optimum despite large power-injection mismatches, indicating hidden or nearly hidden rank-one solutions.
  • Selective higher-order constraints recover global solutions for many problems, with Algorithm 1 typically requiring only a small number of iterations and higher-order buses.
  • 3.54% and 0.75% are the first-order objective-value gaps below the global optimum for case39Q and case118L, respectively, showing that not all problems have hidden rank-one solutions.
  • Case39Q requires many iterations and higher-order constraints at most network buses, demonstrating that selective higher-order relaxations are not computationally tractable for every problem.
  • Algorithm 1 identifies an at-least-locally minimal higher-order bus set for case118Q, case118L, and case300, and uses only one additional bus for case14Q, case39L, case57Q, and case57L.

VI. CONCLUSION

The paper combines moment relaxations with sparsity exploitation and selective higher-order constraints to globally solve OPF instances that defeat existing convex relaxations. Its remaining challenges include computational performance, realistic hard test cases, tightness conditions, and broader OPF formulations.

  • Moment relaxations: Moment relaxations form a hierarchy of semidefinite programs developed from the Lasserre hierarchy, with higher orders producing tighter but larger relaxations.Increasing relaxation order improves tightness at increased computational cost.
  • Scalability: A matrix completion decomposition exploits power-system sparsity to make larger moment-relaxation problems tractable.The decomposition is paired with selective enforcement of higher-order constraints.
  • Scalability: An iterative algorithm applies higher-order constraints selectively, using a heuristic to identify where they are needed while relying on first-order relaxations elsewhere.The approach leverages the observation that first-order relaxations suffice for large regions of typical OPF problems.
  • Results: The algorithm globally solved several test cases for which existing convex relaxations failed.This demonstrates effectiveness on instances lacking physically meaningful solutions from existing relaxations.
  • Future work: Future work targets improved computational performance, more realistic cases where low-order relaxations fail, sufficient tightness conditions, and more general OPF formulations.Proposed extensions include alternative heuristics, distributed algorithms, discrete devices, security constraints, and transient stability constraints.
Loading 1404.5071v2…