PaperlayerView exact revision on arXiv

Source-linked AI summary

Quadratically constrained quadratic programs on acyclic graphs with application to power flow

Subhonmesh Bose, Dennice F. Gayme, K. Mani Chandy, Steven H. Low

arXiv:1203.5599v2math.OC

TL;DR

Non-convex QCQPs are generally NP-hard, and computationally efficient solution methods are lacking. This paper gives a polynomial-time result for a conditionally defined class of QCQPs and applies it to radial-network OPF, while offering a heuristic outside the conditions; simulations suggest that heuristic often finds near-optimal OPF solutions.

  • Problem

    QCQPs are generally non-convex and NP-hard, and they therefore lack computationally efficient solution methods.

    Source: §I · p. 1, §V · p. 22

  • Method

    The paper proves polynomial-time solvability for QCQPs meeting its sufficient conditions, applies the result to OPF, and offers a feasible-solution heuristic when the conditions fail.

    Source: §I · p. 2, §V · p. 22

  • Results

    The paper derives conditions for efficient OPF solutions, and simulations suggest its heuristic often finds near-optimal OPF solutions.

    Source: §V · p. 22

  • Takeaways & Limitations

    The polynomial-time result is conditional; for problems outside its sufficient conditions, the paper provides a heuristic to find a feasible solution.

    Source: §V · p. 22

    The polynomial-time guarantee is limited to QCQPs satisfying the sufficient conditions; the proposed alternative for other cases is a heuristic.

    Source: §I · p. 2, §V · p. 22

Abstract

from arXiv · show

This paper proves that non-convex quadratically constrained quadratic programs can be solved in polynomial time when their underlying graph is acyclic, provided the constraints satisfy a certain technical condition. When this condition is not satisfied, we propose a heuristic to obtain a feasible point. We demonstrate this approach on optimal power flow problems over radial networks.

I. INTRODUCTION

The introduction develops conditions under which non-convex QCQPs on acyclic graphs can be solved in polynomial time using exact semidefinite relaxations, and outlines rank-one recovery while noting challenges when connectivity or strict feasibility fails. It also presents a heuristic for instances that do not satisfy the conditions and applies the approach to optimal power flow on radial networks.

I. INTRODUCTION

  • The paper extends the class of efficiently solvable non-convex QCQPs and applies its sufficient condition to OPF over radial networks.The introduction describes the radial-network result as extending the previously known class of OPF problems that can be solved efficiently.Source: §I · p. 2
  • For QCQPs that fail these conditions, the paper proposes a heuristic for feasible points and reports near-optimal feasible OPF points in simulations.The introduction notes that these QCQPs cannot have their optimum directly recovered by solving the semidefinite relaxation.Source: §I · p. 3

II. QCQP’S AND SEMIDEFINITE RELAXATION

  • QCQPs satisfying Condition 1—connected acyclic graph, edgewise origin outside the relative interior of specified coefficient hulls, bounded feasibility, and strict feasibility—are solvable in polynomial time.The edgewise condition concerns the convex hull of the objective and constraint matrix entries associated with each graph edge.Source: §II · p. 4
  • Under Condition 1, the semidefinite relaxation is not only exact but can itself be solved in polynomial time.The theorem states that all QCQPs satisfying Condition 1 can be solved in polynomial time.Source: §II · pp. 4, 6
  • The relaxation and its dual have equal optimal values and a finite primal-dual optimal point.The proof invokes strict feasibility and Slater’s condition.Source: A. Proof of Theorem 1 for C ≻0 · p. 8
  • A rank-at-most-one optimal solution of the relaxation gives an exact SDR, and perturbation and a limit argument establish such a solution for the original relaxation.The perturbed optima have rank at most one for sufficiently small positive ε; a convergent subsequence yields an optimal feasible limit of rank at most one, with equal primal and relaxation optimum values.Source: A. Proof of Theorem 1 for C ≻0 · pp. 10–11
  • Because a non-unique relaxation may not return a minimum-rank optimizer, the proposed polynomial-time approach solves the relaxation and recovers x∗ when its optimizer has rank at most one.For a rank-at-most-one optimizer, x∗ is constructed from W∗; the passage notes that non-uniqueness can prevent directly using the relaxation to solve P in polynomial time.Source: A. Proof of Theorem 1 for C ≻0 · p. 11
  • The proof of Theorem 1 is completed for the case where C is positive definite.Source: A. Proof of Theorem 1 for C ≻0 · p. 11
  • Without strict feasibility, P still has an exact SDR with an optimal positive semidefinite solution of rank at most 1, but finding a low-rank optimizer efficiently is hard to guarantee.Other optimal SDR solutions may fail the rank condition needed to map them to an optimal solution of P.Source: A. Proof of Theorem 1 for C ≻0 · p. 12

III. OPTIMAL POWER FLOW: AN APPLICATION

The section applies the paper’s QCQP results to optimal power flow (OPF), formulating OPF as a QCQP and focusing on radial networks. It uses Theorem 1 to characterize conditions for efficient solution.

III. OPTIMAL POWER FLOW: AN APPLICATION

  • The section applies the results of Section II to the optimal power flow problem.Source: §III · p. 12
  • Theorem 1 is used to characterize conditions under which OPF over radial networks can be solved efficiently.The section focuses on radial networks, commonly found in distribution circuits.Source: §III · p. 12

A. Prior work

Prior work studies convex relaxations of OPF, including semidefinite and second-order cone relaxations, and reports exactness under particular conditions. The section also notes that these methods do not recover solutions for every instance.

A. Prior work

  • Prior approaches also use convex Lagrangian duality to derive a sufficient condition for recovering an OPF optimum from a dual optimum,.Source: A. Prior work · p. 12
  • Semidefinite relaxation has recovered OPF solutions on IEEE test systems but does not work on all problem instances.Source: A. Prior work · p. 12
  • For radial networks, prior work reports exactness of the OPF semidefinite relaxation under certain power-flow constraint conditions –.Source: A. Prior work · pp. 12–13
  • SOCP relaxations proposed in – are proved exact for radial networks in – when upper bounds on loads or voltage magnitudes are absent.Source: A. Prior work · p. 13

B. Problem Formulation

The formulation represents a power system using bus voltages, currents, power injections, and branch flows, with circuit parameters tied to the network admittance. It expresses real power flows and line losses as quadratic forms.

B. Problem Formulation

  • The formulation describes an n-bus power system using complex voltage and current vectors and a complex power vector whose components are real and reactive powers.Source: B. Problem Formulation · p. 13
  • Real and reactive power demands are fixed inputs, while real and reactive generation are decision variables subject to power-injection bounds.Source: B. Problem Formulation · p. 14
  • Branch quantities include sending-end complex power flow and line loss, with real power flow bounded by the line-flow limit and thermal loss by the thermal limit.Source: B. Problem Formulation · p. 14
  • The real power flow and thermal loss are expressed as quadratic forms in the voltage vector, using Hermitian matrices.Source: B. Problem Formulation · p. 15

V HM ijV ≤F ij, i ∼j, (17d)

The formulation includes constraints on power, voltage magnitudes, line flows, and thermal losses, and varies the objective by changing its matrix. It omits apparent-power upper bounds because those constraints are not quadratic in voltages.

V HM ijV ≤F ij, i ∼j, (17d)

C. Semidefinite relaxation of OPF over radial networks

For OPF on a tree, the paper applies its QCQP result when the specified conditions hold; in general, condition 1(b) may fail. The section also describes constraint patterns and the strict-feasibility boundary for polynomial-time solvability.

C. Semidefinite relaxation of OPF over radial networks

A. Numerical techniques

When the relaxation yields a higher-rank solution, the paper constructs a feasible point for the original QCQP through an iterative heuristic. The procedure starts from the relaxation solution and may fail to find feasibility within its iteration limit.

A. Numerical techniques

  • When the relaxation optimum W* has rank greater than 1, the paper proposes a heuristic to construct a feasible point for P.The relaxation solution cannot then be mapped to an optimal solution of P.Source: A. Numerical techniques · p. 19
  • The heuristic initializes x0 from the principal eigenvector of W*, scaled so its objective matches the relaxation optimum.Source: A. Numerical techniques · p. 19
  • At each iteration, it linearizes the quadratic constraints around the current point and limits the step using an ℓ1 ball of radius γ.The linearization is intended as an approximation within that ball.Source: A. Numerical techniques · p. 20
  • The heuristic either returns a feasible point or fails to produce one within a fixed number of iterations.Source: A. Numerical techniques · p. 20

B. OPF test examples

The simulations test voltage and power-loss minimization on a Southern California circuit and randomly generated radial circuits. Power-loss minimization yields rank-1 relaxation optima, while voltage minimization can require the heuristic; reported heuristic points are feasible and close to the theoretical optimum.

B. OPF test examples

  • The test set includes a modified Southern California industrial distribution circuit and randomly generated radial circuits.The Southern California circuit has approximately 11.3 MW peak load and 6.4 MW installed PV capacity; random circuits assume PV at about 15–60% of nodes.Source: B. OPF test examples · pp. 20–21
  • Both voltage minimization and power-loss minimization are tested as objective functions.Source: B. OPF test examples · p. 21
  • Power-loss minimization always yielded a rank-1 optimal W*, whereas voltage minimization produced optima violating the rank condition.The heuristic was used for the voltage-minimization cases that violated the rank condition.Source: B. OPF test examples · p. 21, Table II · p. 22
  • In the examples studied, the heuristic always found a feasible point within 5 iterations, with objective values close to the theoretical optimum.The text describes the values of η in Table II as indicating this closeness.Source: B. OPF test examples · pp. 21–22, Table II · p. 22
  • The heuristic's general performance bound remains an open question.Source: B. OPF test examples · p. 22

V. CONCLUSION

The paper proves polynomial-time solvability for a class of non-convex QCQPs and applies the result to OPF under sufficient conditions. For cases outside those conditions, it offers a feasibility heuristic that simulations suggest often finds near-optimal OPF solutions.

V. CONCLUSION

  • A certain class of non-convex QCQPs is solvable in polynomial time, and the result yields conditions for efficient solutions to OPF.Source: §V · p. 22
  • For OPF instances that do not satisfy the sufficient conditions, the paper provides a heuristic to find a feasible solution.Source: §V · p. 22
  • Simulations suggest that the heuristic often finds a near-optimal solution for OPF.Source: §V · p. 22

VI. APPENDIX

The appendix supplies perturbation arguments for exact and approximate polynomial-time solutions, then gives OPF-specific C_k entry relations.

A. Proof of lemma 2:

  • For C ⪰ 0, perturbing RP makes its objective matrix positive definite; rank-at-most-one optimizers can then construct an optimum of P in polynomial time.The proof sketch states that the perturbed problem has a finite optimizer and can be solved in polynomial time.Source: B. Proof of Theorem 1 for C ⪰0 · p. 23
  • The perturbation proof uses bounded shared feasible regions to take δ→0 subsequences, showing a feasible limit that attains P's optimum.The proof argues that a strict gap between the limit's objective and P's optimum would contradict optimality for sufficiently small δ.Source: B. Proof of Theorem 1 for C ⪰0 · p. 24
  • When an optimizer of RP fails the rank-at-most-one test, solving a perturbed RP yields a feasible P point within ζ of the theoretical optimum in polynomial time.If the optimizer meets the rank condition, the paper instead recovers x* from it and solves P in polynomial time.Source: B. Proof of Theorem 1 for C ⪰0 · pp. 24–25
  • For OPF, the appendix derives C_k entries from equations (14)–(16), listing diagonal and paired-index cases in T, plus Y_ij-based cases when k=j.The listed diagonal and paired-index cases involve g_pq; the k=j cases use Y_ij.Source: C. Matrices involved in OPF · pp. 25–26
Loading 1203.5599v2…