Quadratically Constrained Quadratic Programs on Acyclic Graphs With Application to Power Flow

This paper proves that nonconvex quadratically constrained quadratic programs can be solved in polynomial time when their underlying graph is acyclic, provided the constraints satisfy a certain technical condition. We demonstrate this theory on optimal power-flow problems over tree networks.

• Publication year

  2012

• Venue

  IEEE Transactions on Control of Network Systems

• Publication date

  2012-03-26

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1109/TCNS.2015.2401172arXiv 1203.5599
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Equivalent Relaxations of Optimal Power Flow

  2014cited by this paper
• Exactness of Semidefinite Relaxations for Nonlinear Optimization Problems with Underlying Graph Structure

  2014cited by this paper
• Convex Relaxation of Optimal Power Flow—Part II: Exactness

  2014cited by this paper
• Branch Flow Model: Relaxations and Convexification—Part II

  2013cited by this paper
• Exact Convex Relaxation of Optimal Power Flow in Radial Networks

  2013cited by this paper
• Network Topologies Guaranteeing Zero Duality Gap for Optimal Power Flow Problem

  2013influential reference
• Optimal power flow with large-scale storage integration

  2013cited by this paper
• Physics of power networks makes hard optimization problems easy to solve

  2012influential reference
• Exact convex relaxation of OPF for radial networks using branch flow model

  2012cited by this paper
• Branch flow model for radial networks: convex relaxation

  2012cited by this paper
• Geometry of Power Flows and Optimization in Distribution Networks

  2012cited by this paper
• Adaptive VAR Control for Distribution Circuits With Photovoltaic Generators

  2012cited by this paper
• Branch flow model: Relaxations and convexification

  2012cited by this paper
• Branch Flow Model: Relaxations and Convexification—Part I

  2012cited by this paper
• Zero Duality Gap in Optimal Power Flow Problem

  2012cited by this paper
• Equivalence of branch flow and bus injection models

  2012cited by this paper
• Examining the limits of the application of semidefinite programming to power flow problems

  2011cited by this paper
• Geometry of feasible injection region of power networks

  2011cited by this paper
• Optimal power flow over tree networks

  2011cited by this paper
• A New Approach to the Stable Set Problem Based on Ellipsoids

  2011cited by this paper
• Inverter VAR control for distribution systems with renewables

  2011cited by this paper
• Zero duality gap for classical opf problem convexifies fundamental nonlinear power problems

  2011cited by this paper
• Conic optimization of electric power systems

  2011cited by this paper
• Semidefinite Relaxation of Quadratic Optimization Problems

  2010cited by this paper
• Two proposals for robust PCA using semidefinite programming

  2010cited by this paper
• Options for Control of Reactive Power by Distributed Photovoltaic Generators

  2010cited by this paper
• Convex Optimization-Based Beamforming

  2010cited by this paper
• Rank-Constrained Separable Semidefinite Programming With Applications to Optimal Beamforming

  2010cited by this paper
• Semi-definite programming-based method for security-constrained unit commitment with operational and optimal power flow constraints

  2009cited by this paper
• Modern Grid Initiative Distribution Taxonomy Final Report

  2008cited by this paper
• On Convexity of Power Flow Feasibility Boundary

  2008cited by this paper
• Semidefinite programming for optimal power flow problems

  2008cited by this paper
• A Unified Theorem on SDP Rank Reduction

  2008cited by this paper
• Transmit beamforming for physical-layer multicasting

  2006cited by this paper
• Semidefinite programming based algorithms for sensor network localization

  2006cited by this paper
• Radial distribution load flow using conic programming

  2006cited by this paper
• Convexity of the set of feasible injections and revenue adequacy in FTR markets

  2005cited by this paper
• Convex Optimization

  2004influential reference
• YALMIP : a toolbox for modeling and optimization in MATLAB

  2004cited by this paper
• On the relative position of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graph

  2003influential reference
• Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

  2003influential reference
• Graphs whose positive semi-definite matrices have nullity at most two

  2003cited by this paper
• A Primal-Dual Interior-Point Method to Solve the Optimal Power Flow Dispatching Problem

  2003cited by this paper
• Exploring the Power Flow Solution Space Boundary

  2001cited by this paper
• Sensitivity analysis in linear programming and semidefinite programming using interior-point methods

  2001cited by this paper
• Quadratic maximization and semidefinite relaxation

  2000cited by this paper
• Handbook of semidefinite programming : theory, algorithms, and applications

  2000influential reference
• Electric Power System Applications of Optimization

  2000cited by this paper
• An efficient interior point method for sequential quadratic programming based optimal power flow

  2000cited by this paper
• Handbook of Semidefinite Programming

  2000cited by this paper
• Approximating quadratic programming with bound and quadratic constraints

  1999cited by this paper
• A review of selected optimal power flow literature to 1993. II. Newton, linear programming and interior point methods

  1999cited by this paper
• A review of selected optimal power flow literature to 1993. I. Nonlinear and quadratic programming approaches

  1999cited by this paper
• Semidefinite Relaxations, Multivariate Normal Distributions, and Order Statistics

  1998cited by this paper
• An interior-point method for nonlinear optimal power flow using voltage rectangular coordinates

  1998cited by this paper
• Semidefinite relaxation and nonconvex quadratic optimization

  1998cited by this paper
• Linear Matrix Inequalities In System And Control Theory

  1998cited by this paper
• Optimization Problems with Perturbations: A Guided Tour

  1998cited by this paper
• Multiplicities of Eigenvalues and Tree-Width of Graphs

  1998cited by this paper
• Semidefinite Programming Relaxations of Non-Convex Problems in Control and Combinatorial Optimization

  1997cited by this paper
• Quality of semidefinite relaxation for nonconvex quadratic optimization

  1997cited by this paper
• SDPT3 -- A Matlab Software Package for Semidefinite Programming

  1996cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• Improved approximation algorithms for MAXk-CUT and MAX BISECTION

  1995cited by this paper
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization

  1995influential reference
• Approximate graph coloring by semidefinite programming

  1994cited by this paper
• Interior-point polynomial algorithms in convex programming

  1994cited by this paper
• Approximate Graph Coloring by Semideenite Programming

  1994cited by this paper
• A survey of the optimal power flow literature

  1991cited by this paper
• Optimal capacitor placement on radial distribution systems

  1989cited by this paper
• Optimal sizing of capacitors placed on a radial distribution system

  1989cited by this paper
• Lectures on modern convex optimization

  1987cited by this paper
• Matrix analysis

  1985cited by this paper
• Maxima for Graphs and a New Proof of a Theorem of Turán

  1965cited by this paper
• Notes on Linear Programming: Part 1. The Generalized Simplex Method for Minimizing a Linear Form under Linear Inequality Restraints

  1954cited by this paper
• Problème général de la stabilité du mouvement

  year unknowncited by this paper
• Journal of Theoretical and Applied Information Technology a Survey of Optimal Power Flow Methods

  year unknowncited by this paper

• Approximating Dispatchable Regions in Three-Phase Radial Networks with Conditions for Exact SDP Relaxation

  2025cites this paper
• FRMNet: A Feasibility Restoration Mapping Deep Neural Network for AC Optimal Power Flow

  2024cites this paper
• Convex relaxation of two-stage network-constrained stochastic programming for CHP microgrid optimal scheduling

  2024cites this paper
• Time-Dependent Unavailability Exploration of Interconnected Urban Power Grid and Communication Network

  2023cites this paper
• Distributionally Robust Optimization for Nonconvex QCQPs with Stochastic Constraints

  2023cites this paper
• A Second-order Cone Relaxation-Based Branch-and-Bound Algorithm for Complex Quadratic Programs on Acyclic Graphs

  2023influential citation
• Reinforcement Learning-Guided Quadratically Constrained Quadratic Programming for Enhanced Convergence and Optimality

  2023cites this paper
• Optimal Power Flow Solutions for Power System Considering Electric Market and Renewable Energy

  2023cites this paper
• An Analysis on Semidefinite Relaxation of Classical Optimal Power Flow Problem

  2022cites this paper
• Robust Co-Optimization of Droop and Affine Policy Parameters in Active Distribution Systems With High Penetration of Photovoltaic Generation

  2022cites this paper
• Learning to Solve the AC-OPF using Sensitivity-Informed Deep Neural Networks

  2022cites this paper
• Learning to Solve the AC-OPF Using Sensitivity-Informed Deep Neural Networks

  2021influential citation
• Conditions for Exact Convex Relaxation and No Spurious Local Optima

  2021cites this paper
• T -operator limits on optical communication: Metaoptics, computation, and input-output transformations

  2021cites this paper
• Optimal power flow

  2021cites this paper
• Distributed Dual Subgradient Methods with Averaging and Applications to Grid Optimization

  2021cites this paper
• Distributed Grid Optimization via Distributed Dual Subgradient Methods with Averaging

  2021cites this paper
• Performance Analysis and Applications of Finite-Time ZNN Models With Constant/Fuzzy Parameters for TVQPEI

  2021cites this paper
• Optimal Dispatch of Battery Energy Storage System Using Convex Relaxations in Unbalanced Distribution Grids

  2020cites this paper
• Matrix-Based Generalization for Power-Mismatch Newton-Raphson Load Flow Computations With Arbitrary Number of Phases

  2020cites this paper
• Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

  2020influential citation
• A survey on conic relaxations of optimal power flow problem

  2020cites this paper
• Conic Relaxations of Power System Optimization : Theory and Algorithms

  2019cites this paper
• Electric Power System with Renewable Generation

  2019cites this paper
• An Alternating Projection Approach for Non-Convex Quadratically Constrained Quadratic Programmings

  2019cites this paper
• SDP-Based Optimal Power Flow With Steady-State Voltage Stability Constraints

  2019cites this paper
• A QCQP and SDP Formulation of the Optimal Power Flow Including Renewable Energy Resources

  2019cites this paper
• A distributed algorithm for high-dimension convex quadratically constrained quadratic programs

  2019cites this paper
• Bilateral Electricity Market in a Distribution System Environment

  2019cites this paper
• Mixed‐integer second‐order cone programming framework for optimal scheduling of microgrids considering power flow constraints

  2019cites this paper
• Architecting a fully fuzzy information model for multi-level quadratically constrained quadratic programming problem

  2019cites this paper
• Sufficient Conditions for Exact Semi-definite Relaxation of Optimal Power Flow in Unbalanced Multiphase Radial Networks

  2019influential citation
• Convex Relaxation Based Locational Marginal Prices

  2019cites this paper
• Convex Relaxation based Locational Marginal Prices for Electricity Markets

  2019cites this paper
• Computing Time-Varying Quadratic Optimization With Finite-Time Convergence and Noise Tolerance: A Unified Framework for Zeroing Neural Network

  2019cites this paper
• An efficient optimization algorithm for quadratic programming problem and its applications to mobile robot path planning

  2018cites this paper
• Profit Maximizing Storage Integration in AC Power Networks

  2018cites this paper
• The Convex Hull of a Quadratic Constraint over a Polytope

  2018cites this paper
• A Computational Model for Multi-level Quadratically Constrained Quadratic Optimization under Fully Fuzzy Environment

  2018cites this paper
• Optimal power flow in distribution networks

  2018cites this paper
• An Exact SOCP Formulation for AC Optimal Power Flow

  2018cites this paper
• Finding Sparse Solutions for Packing and Covering Semidefinite Programs

  2018cites this paper
• Convexity of Solvability Set of Power Distribution Networks

  2018cites this paper
• Penalized Parabolic Relaxation for Optimal Power Flow Problem

  2018cites this paper
• A branch-and-cut algorithm using polar cuts for solving nonconvex quadratic programming problems

  2018cites this paper
• A decomposition method for nonconvex quadratically constrained quadratic programs

  2017cites this paper
• Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem

  2017cites this paper
• Quadratic programming over ellipsoids with applications to constrained linear regression and tensor decomposition

  2017cites this paper
• Minimum Rank Positive Semidefinite Matrix Completion with Chordal Sparsity Pattern

  2017cites this paper
• Constrained Primal-Dual Dynamics for QCQP with Applications to Economic Dispatch

  2017cites this paper
• Convex Hull of the Quadratic Branch AC Power Flow Equations and Its Application in Radial Distribution Networks

  2017cites this paper
• AC OPF in radial distribution networks – Part I: On the limits of the branch flow convexification and the alternating direction method of multipliers

  2017cites this paper
• Approximations for generalized unsplittable flow on paths with application to power systems optimization

  2017cites this paper
• Reactive power fluctuations smoothing in optimal control of grid-connected PV systems

  2017cites this paper
• Non-convex Quadratically Constrained Quadratic Programming: Hidden Convexity, Scalable Approximation and Applications

  2017cites this paper
• Branch-delete-bound algorithm for globally solving quadratically constrained quadratic programs

  2017cites this paper
• From Electrical Power Flows to Unsplittabe Flows: A QPTAS for OPF with Discrete Demands in Line Distribution Networks

  2017cites this paper
• POVMs are equivalent to projections for perfect state exclusion of three pure states in three dimensions

  2017cites this paper
• General Heuristics for Nonconvex Quadratically Constrained Quadratic Programming

  2017cites this paper
• A Survey of Distributed Optimization and Control Algorithms for Electric Power Systems

  2017cites this paper
• Active network management for electrical distribution systems: problem formulation, benchmark, and approximate solution

  2016cites this paper
• Bound Tightening for the Alternating Current Optimal Power Flow Problem

  2016cites this paper
• Optimal sizing of distributed energy storage with consideration of demand response in distribution systems

  2016cites this paper
• Application of polynomial optimization to electricity transmission networks

  2016cites this paper
• A Hybrid Transmission Grid Architecture Enabling Efficient Optimal Power Flow

  2016influential citation
• A bound on the minimum rank of solutions to sparse linear matrix equations

  2016cites this paper
• Optimization and Control of Power Flow in Distribution Networks

  2016cites this paper
• Low-Rank Semidefinite Programming: Theory and Applications

  2016cites this paper
• Active Network Management for Electrical Distribution Systems

  2016cites this paper
• Graphical models for optimal power flow

  2016cites this paper
• Global Optimization Methods for Optimal Power Flow and Transmission Switching Problems in Electric Power Systems

  2016cites this paper
• Real-Time Optimal Controls for Active Distribution Networks - From Concepts to Applications

  2015cites this paper
• LP formulations for mixed-integer polynomial optimization problems

  2015cites this paper
• Hidden Convexity in QCQP with Toeplitz-Hermitian Quadratics

  2015cites this paper
• AC OPF in Radial Distribution Networks - Parts I, II

  2015cites this paper
• Acyclic semidefinite approximations of quadratically constrained quadratic programs

  2015influential citation
• Offset optimization for a network of signalized intersections via semidefinite relaxation

  2015cites this paper
• Resistive Network Optimal Power Flow: Uniqueness and Algorithms

  2015influential citation
• A Unifying Market Power Measure for Deregulated Transmission-Constrained Electricity Markets

  2015cites this paper
• Strong SOCP Relaxations for the Optimal Power Flow Problem

  2015cites this paper
• Branch-and-Cut for Nonlinear Power Systems Problems

  2015cites this paper
• Secure electric power grid operation

  2015cites this paper
• Optimal sizing of distributed energy storage in distribution systems

  2015cites this paper
• On mixed-integer optimization problems with bounded tree-width

  2015cites this paper
• Moment/Sum-of-Squares Hierarchy for Complex Polynomial Optimization

  2015cites this paper
• On optimization problems with bounded tree-width

  2015cites this paper
• LP approximations to mixed-integer polynomial optimization problems

  2015cites this paper
• Optimization Decomposition of Resistive Power Networks With Energy Storage

  2014cites this paper
• Exactness of Semidefinite Relaxations for Nonlinear Optimization Problems with Underlying Graph Structure

  2014cites this paper
• Solving quadratically constrained quadratic programs on acyclic graphs with application to optimal power flow

  2014cites this paper
• Active network management for electrical distribution systems: problem formulation and benchmark

  2014cites this paper
• Distributed State Estimation and Energy Management in Smart Grids: A Consensus${+}$ Innovations Approach

  2014cites this paper
• Nondegeneracy and Inexactness of Semidefinite Relaxations of Optimal Power Flow

  2014cites this paper
• Rank-2 Matrix Solution for Semidefinite Relaxations of Arbitrary Polynomial Optimization Problems

  2014cites this paper
• Advanced optimization methods for power systems

  2014cites this paper
• Graph-theoretic algorithms for polynomial optimization problems

  2014cites this paper
• Robust Layered Transmission and Compression for Distributed Uplink Reception in Cloud Radio Access Networks

  2014cites this paper
• A non-convex alternating direction method of multipliers heuristic for optimal power flow

  2014cites this paper
• Active network management for electrical distribution systems: problem formulation, benchmark, and approximate solution

  2014cites this paper
• Gestion active d’un réseau de distribution d’électricité : formulation du problème et benchmark

  2014cites this paper