PaperlayerView exact revision on arXiv

Source-linked AI summary

Strong SOCP Relaxations for the Optimal Power Flow Problem

Burak Kocuk, Santanu S. Dey, X. Andy Sun

arXiv:1504.06770v4math.OC

TL;DR

Large-scale AC OPF is difficult to solve with standard SDP relaxations, particularly for networks exceeding a thousand buses. The paper proposes three strong SOCP relaxations that offer computationally attractive alternatives, with faster solution times and practical solution use.

  • Problem

    Standard SDP relaxations face computational difficulty when practically solving real-world-sized power networks with more than a thousand buses.

  • Method

    The paper proposes three efficient strong SOCP relaxation approaches for the AC optimal power flow problem.

  • Results

    The proposed strong SOCP relaxations provide an attractive alternative to SDP relaxations, with solution times an order of magnitude faster than SDP.

  • Takeaways & Limitations

    The proposed SOCP solutions can be used as warm starts for local OPF solvers and provide stronger bounds than existing quadratic relaxations on most instances.

  • Takeaways & Limitations

    The computational difficulty of SDP relaxations constrains their practical use for real-world power networks with more than a thousand buses.

Abstract

from arXiv · show

This paper proposes three strong second order cone programming (SOCP) relaxations for the AC optimal power flow (OPF) problem. These three relaxations are incomparable to each other and two of them are incomparable to the standard SDP relaxation of OPF. Extensive computational experiments show that these relaxations have numerous advantages over existing convex relaxations in the literature: (i) their solution quality is extremely close to that of the SDP relaxations (the best one is within 99.96% of the SDP relaxation on average for all the IEEE test cases) and consistently outperforms previously proposed convex quadratic relaxations of the OPF problem, (ii) the solutions from the strong SOCP relaxations can be directly used as a warm start in a local solver such as IPOPT to obtain a high quality feasible OPF solution, and (iii) in terms of computation times, the strong SOCP relaxations can be solved an order of magnitude faster than standard SDP relaxations. For example, one of the proposed SOCP relaxations together with IPOPT produces a feasible solution for the largest instance in the IEEE test cases (the 3375-bus system) and also certifies that this solution is within 0.13% of global optimality, all this computed within 157.20 seconds on a modest personal computer. Overall, the proposed strong SOCP relaxations provide a practical approach to obtain feasible OPF solutions with extremely good quality within a time framework that is compatible with the real-time operation in the current industry practice.

1 Introduction

OPF combines large-scale nonconvex optimization with limited computational budgets and incomplete optimality guarantees from common approaches. The paper proposes strong SOCP relaxations intended to provide tractable, high-quality alternatives to SDP and quadratic relaxations.

  • Motivation: OPF is a large-scale nonconvex optimization problem whose operational use imposes tight computational budgets.The paper describes OPF on power networks with thousands of buses and notes that operational-level problems may be solved every few minutes.
  • Limitations of Existing Approaches: DC OPF simplifies AC OPF but ignores reactive power and voltage magnitude, and subsequent power-flow calculations cannot guarantee AC optimality.
  • Limitations of Existing Approaches: Local optimization methods can solve IEEE instances effectively but do not quantify solution quality.
  • Limitations of Existing Approaches: SDP relaxations can provide global optimal solutions when exact, but exactness is guaranteed only for restricted problem classes.When SDP relaxations are not exact, their solutions may lack a clear physical interpretation.
  • Limitations of Existing Approaches: SDP hierarchies and sparsity methods face computational or recovery challenges on large networks.The required hierarchy order can be arbitrarily large, and non-rank-one solution matrices complicate voltage recovery.
  • Paper Contribution: The paper proposes three efficient strong SOCP relaxations that strengthen the classic SOCP relaxation and may be incomparable to standard SDP relaxations.The approach analyzes relaxation strength and adds convex constraints implied by the original OPF constraints.
  • Computational Findings: Across MATPOWER cases from 6-bus to 3375-bus, the third proposed SOCP relaxation achieves lower bounds within 99.96% of SDP bounds on average.The other two proposed relaxations are within 99.7% of the SDP relaxation on average.
  • Computational Findings: The proposed SOCP relaxations are orders of magnitude faster than SDP relaxations and consistently outperform existing convex quadratic relaxations.They also perform consistently on IEEE cases with randomly perturbed load profiles.

2 Optimal Power Flow Problem

The OPF problem minimizes generator production costs while satisfying electrical demand, physical laws, operational restrictions, and voltage and generator limits. Its rectangular formulation is nonconvex, while an alternative formulation is exact on radial networks but may require cycle constraints on meshed networks.

  • Problem definition: OPF minimizes total generator production costs while satisfying demand at every bus and respecting physical and operational restrictions.These restrictions include physical laws such as Ohm’s and Kirchhoff’s laws, transmission-line flow limits, and generator capability limits.
  • Voltage representation: Voltage phasors can be represented in rectangular form as Vi = ei + ifi or in polar form using voltage magnitudes and phase angles.Voltage magnitudes are commonly expressed in per unit and kept close to the unit voltage level in transmission systems.
  • Rectangular formulation: The rectangular OPF formulation is a nonconvex quadratic optimization problem whose nonlinearities arise from quadratic and bilinear voltage terms.The formulation introduces cij and sij variables to represent selected products of rectangular voltage components.
  • Alternative formulation: The alternative formulation uses cij and sij variables and is exact on radial networks, allowing recovery of optimal voltage phase angles from its solution.Phase angles are recovered by solving a linear system based on the optimal cij and sij values.
  • Meshed networks: For meshed networks, the alternative formulation can be a strict relaxation because atan2(sij, cij) need not sum to zero around every cycle.Adding the cycle angle constraint produces a valid formulation for meshed-network OPF.

3 Comparison of Convex Relaxations

The paper constructs McCormick, SOCP, and SDP relaxations for both OPF formulations and compares their feasible regions. The SOCP relaxations replace selected semidefinite constraints with tractable second-order cone constraints, while strengthened SDP modeling uses additional matrix variables and bounds.

  • Relaxation framework: The paper compares McCormick, SOCP, and SDP relaxations applied to both the rectangular and alternative OPF formulations.Their relative strength is analyzed by comparing feasible regions in a common variable space.
  • McCormick relaxations: McCormick relaxations replace bilinear and quadratic products with auxiliary variables constrained by convex envelopes, producing polyhedral feasible regions.For the rectangular formulation, auxiliary variables represent products such as eiej, fifj, and eifj.
  • SDP relaxations: The standard SDP relaxation lifts voltage variables into a Hermitian or real matrix and drops rank constraints while retaining semidefinite constraints.The lifted matrix exactly recovers the original constraints when the corresponding rank condition holds.
  • SOCP relaxations: The rectangular SOCP relaxation imposes second-order cone constraints on 2 × 2 line submatrices instead of requiring the full matrix to be positive semidefinite.This is a relaxation because full semidefiniteness requires all principal submatrices to be semidefinite.
  • SOCP relaxations: The alternative SOCP relaxation relaxes the nonconvex coupling constraints with a rotated SOCP cone that is the convex hull of those constraints.This formulation is identified as the classic SOCP relaxation first proposed by Jabr.
  • Alternative-formulation SDP: The paper also develops an SDP relaxation for the alternative formulation using a vector of c, s, and diagonal c variables and a matrix approximating zzT.Additional constraints upper-bound diagonal matrix elements using McCormick envelopes.

3.2 Comparison of Relaxations

Relaxation strength is compared through projections of feasible regions onto real and reactive powers. Theorem 3.1 establishes a partial ordering, and examples show that every stated inclusion can be strict.

  • Theorem 3.1: Theorem 3.1 compares the projected feasible regions of McCormick, SOCP, and SDP relaxations for the rectangular and alternative formulations.The theorem identifies relationships among ˆRM, ˆAM, ˆRSDP, ˆRSOCP, ˆA∗SOCP, and ˆASDP.
  • Comparison basis: The comparison projects each relaxation’s feasible region onto the common (p, q) space because the objective depends only on real power.A hat denotes this projection, such as ˆRM for the projection of RM.
  • Strictness: All inclusions in the theorem can be strict, so the compared relaxations are not equivalent in general.The paper provides examples to verify the strictness claims.
  • McCormick comparisons: The projected McCormick relaxation of the alternative formulation is contained in the projected McCormick relaxation of the rectangular formulation.This relationship is stated as ˆRM ⊇ ˆAM.
  • SDP versus SOCP: The SDP relaxation of the alternative formulation can be weaker than the strong SOCP relaxation of that formulation.A two-bus example demonstrates that ˆASDP can be weaker than the corresponding SOCP relaxation.
  • Rectangular relaxations: The rectangular SDP relaxation is contained in the rectangular SOCP relaxation, with equality for radial networks but potentially strict inclusion for meshed networks.The case6ww instance illustrates strictness for a meshed network.

3.3 Our choice of convex relaxation

The paper favors strong SOCP relaxations as computationally attractive alternatives to SDP relaxations. The discussion also identifies opportunities to strengthen SOCP models with convex approximations of cycle-angle constraints.

  • Strengthening SOCP: The classic SOCP relaxation can be strengthened by adding LP- or SOCP-based convex outer approximations of the nonconvex arctangent cycle constraints.The paper indicates that such strengthening may produce relaxations incomparable to the rectangular SDP relaxation.
  • SOCP versus LP: Both McCormick relaxations are weaker than the SOCP relaxations, and preliminary meshed-system experiments report a significant bound-quality difference.The theoretical comparison supports selecting SOCP rather than linear programming relaxations when stronger bounds are desired.
  • Practical motivation: The proposed strong SOCP relaxations offer a computationally attractive alternative to SDP relaxations for large-scale OPF problems.The paper’s stated goal is to avoid using SDP relaxations while retaining strong bounds.
  • Choice of relaxation: The standard SDP relaxation is strongest among the relaxations considered in Theorem 3.1, but the alternative-formulation SDP can be weaker than the strong SOCP relaxation.The paper therefore states that the alternative-formulation SDP is not a good choice when using SDPs.

4 Strong SOCP Relaxation for Meshed Networks

The paper strengthens the classic SOCP relaxation through three approaches for meshed networks: cycle-based constraints, arctangent envelopes, and dynamically generated valid inequalities. These formulations preserve SOCP efficiency while producing solutions close to SDP accuracy.

  • Overview: Three strengthening methods augment the classic SOCP relaxation for meshed OPF networks.They use cycle constraints, arctangent envelopes, and dynamically generated valid inequalities.
  • Cycle-based strengthening: Cycle constraints reformulate angle consistency over network cycles as polynomial constraints, then use cycle decomposition and McCormick relaxation to obtain bilinear systems.The resulting approach handles polynomial constraints whose degrees depend on cycle length.
  • Cycle-based strengthening: The cycle-based convex relaxation is incomparable to the standard SDP relaxation.Neither relaxation dominates the other.
  • Arctangent strengthening: A polyhedral envelope for three-dimensional arctangent functions is incorporated into the classic SOCP relaxation, producing another convex relaxation incomparable to SDP.This approach directly approximates the arctangent constraint rather than reformulating polynomial cycle constraints.
  • Separation strengthening: Dynamically generated valid linear inequalities separate SOCP solutions from SDP cones.This method combines SOCP efficiency with SDP-like accuracy and rapidly produces solutions extremely close to the SDP relaxation.
  • Variable bounds: Variable-bounding techniques provide tight bounds for the first two strengthening approaches.The bounds are proposed as an additional way to strengthen the classic SOCP relaxation.

4.1 A New Cycle-based Relaxation of OPF

The cycle-based relaxation enforces angle consistency around cycles while replacing high-degree polynomial constraints with bilinear systems. Cycle decomposition yields valid extended relaxations that preserve the cycle condition and remain incomparable to SDP.

  • Cycle constraints: Angle differences are required to sum to 0 modulo 2π over every cycle, and it suffices to enforce this on a cycle basis.The cycle condition is expressed using cosine and sine variables associated with network lines.
  • Polynomial formulation: Cycle conditions can be expressed as homogeneous polynomial constraints in cosine and sine variables.For a cycle C, the resulting polynomial has degree proportional to |C|.
  • Polynomial formulation: Directly solving the polynomial relaxation can be intractable for large cycles because it may contain exponentially many high-degree monomials.The polynomial p|C| can have up to 2^|C|−1 + 1 monomials, with each monomial of degree |C|.
  • Bilinear reformulation: Cycle decomposition replaces large-cycle polynomial constraints with O(|C|)-sized bilinear systems, followed by McCormick relaxation.Artificial edges decompose cycles into smaller 3- and 4-cycles for applying the reformulation.
  • 3-cycle formulation: For a 3-cycle, the polynomial cycle constraint is equivalent to two bilinear constraints together with the line consistency equations.Proposition 4.1 establishes equality between the polynomial and bilinear formulations.
  • Validity: For a given cycle basis, the proposed bilinear extended relaxation is valid and implies that angle differences sum to 2πk on each cycle.The construction applies constraints (28) to 3-cycles and constraints (34) to cycles of length n ≥4.
  • Comparison with SDP: The cycle-based SOCP strengthening is incomparable to standard SDP relaxations, including RSDP.It is neither dominated by nor dominant over the corresponding SDP relaxation.

4.2 Arctangent Envelopes

The arctangent-envelope approach strengthens classic SOCP by approximating the angle constraint with linear inequalities over a box. Its resulting relaxation is also incomparable to the SDP relaxation.

  • Construction: The method incorporates a convex approximation of each arctangent angle constraint into the classic SOCP relaxation.The approximation is built over a box in the (c, s, θ) space.
  • Construction: Four linear inequalities approximate the convex envelope of the arctangent function over the box.Two inequalities approximate the upper envelope and two approximate the lower envelope.
  • Envelope geometry: The envelope planes are constructed from box-corner points in the (c, s, θ) space.The upper and lower inequalities use planes passing through selected triples of the four corner points.
  • Comparison with SDP: The SOCP relaxation strengthened by arctangent envelopes is neither dominated by nor dominant over the SDP relaxation RSDP.Figure 1 illustrates the red envelope planes from different viewpoints.

4.3 SDP Separation

The SDP-separation approach strengthens SOCP by checking whether its cosine and sine variables admit a compatible positive semidefinite matrix, then adding separating inequalities when they do not. Cycle-restricted separation reduces the computational burden and yields tight SDP approximations after few iterations.

  • SDP embedding: The method uses the linear relationship between cosine-sine variables and a matrix W satisfying W = xxT in the exact formulation.A classic SOCP solution can be embedded in the SDP relaxation when a compatible W ⪰ 0 exists.
  • Separation procedure: If a positive semidefinite matrix W exists, the SOCP solution satisfies the standard SDP relaxation; otherwise, a valid separating inequality can be added.The separation procedure iteratively excludes SOCP points outside the SDP-compatible set.
  • Computational scope: Full-network separation requires solving an SDP with a matrix as large as the original relaxation, which can be time consuming.This motivates restricting separation to cycle submatrices.
  • Cycle-restricted separation: Cycle-restricted separation uses a positive semidefinite submatrix for each cycle in a cycle basis to approximate the angle condition.The resulting inequalities are generated by solving a separation problem over each cycle.
  • Computational result: A few algorithm iterations produce very tight approximations to the SDP relaxation of the rectangular formulation.The procedure repeatedly resolves SOCP after adding valid inequalities from cycle separation.

4.4 Obtaining Variable Bounds

The section develops tighter variable bounds for SOCP relaxations, especially for c and s variables, using local network subproblems and cycle decompositions. These bounds support arctangent-based strengthening while balancing accuracy and computational speed.

  • Strengthening mechanism: The resulting bounds enable McCormick relaxations of cycle constraints and contribute to the strengthening of the proposed SOCP methods.Arctangent functions are useful only when good upper and lower variable bounds are available.
  • Motivation: Explicit bounds on phase-angle-related variables are important because implied bounds on c_ij and s_ij may be loose.Under normal operation, phase-angle differences are typically small, implying c_ij ≈ 1 and s_ij ≈ 0.
  • Local SOCP bounds: A reduced SOCP over buses within r steps of an edge provides potentially weaker but computationally efficient variable bounds.The local network is defined using B_kl(r), G_kl(r), and L_kl(r), and the resulting problems can be solved in parallel for each edge.
  • Local SOCP bounds: The experiments select r = 2 as a tradeoff between accuracy and speed, while larger r values improve bounds only marginally.
  • Cycle-based bounds: For artificial edges, bounds are obtained from original-variable bounds and tightened through 3-cycle and 4-cycle decompositions.The procedure bounds bilinear expressions to derive bounds for artificial-edge variables such as c13, s13, and c14, s14.

5 Computational Experiments

Computational experiments compare four SOCP-based methods with SDP and quadratic convex relaxations on IEEE and NESTA instances. The strong SOCP methods achieve bounds and feasible solutions close to SDP quality while requiring substantially less computation time.

  • Comparison with SDP: The proposed relaxations are not ordered by dominance: SDP does not dominate S34 or SOCPA, and the SOCP methods are not dominated by SDP.
  • Lower-bound quality: Arctangent envelopes substantially strengthen classic SOCP, whereas additional McCormick cycle inequalities provide only a small effect after arctangent strengthening.
  • Lower bounds and computation time: SSDP matches the SDP lower bound in nine instances and reaches 99.96% of it on average for the remaining comparisons.
  • Lower bounds and computation time: The proposed SOCP methods are roughly one order of magnitude faster than SDP for large problems with 2383 buses or more.The largest case3375wp requires at least 3 hours merely to construct the SDP model.
  • Feasible solutions: SSDP reduces the average optimality gap to 0.08%, compared with 0.19% for SDP, while SOCP-based methods are faster in feasible-solution computation.
  • Robustness: The methods remain provably good and tight on randomly perturbed IEEE benchmark instances.

6 Conclusions and Future Work

The paper concludes that strong SOCP relaxations offer computationally attractive alternatives to SDP for large-scale OPF. They provide near-SDP bounds, useful warm starts for local optimization, and stronger bounds than existing quadratic relaxations, while some instances remain unsolved to global optimality.

  • Main conclusions: Strong SOCP relaxations provide lower bounds close to SDP quality at computation times an order of magnitude faster.They are not always dominated by SDP, and the recommended variant depends on whether tight phase-angle bounds are available.
  • Feasible OPF solutions: SOCP solutions can serve as convenient warm starts for IPOPT, whereas recovering feasible solutions from SDP relaxations is computationally challenging.
  • Comparison with prior relaxations: The proposed SOCP relaxations provide stronger bounds than existing quadratic OPF relaxation approaches on most instances.
  • Future work: Some instances are not solved to global optimality, motivating future spatial branch-and-bound methods.

A Times for NESTA Instances

Appendix A reports computational costs for different relaxation methods on NESTA instances.

  • Computational costs: Computational costs of the different methods for NESTA instances are provided in Table 7.
Loading 1504.06770v4…