CoChat
Sign Up
PreprintCited by 131Advanced Optimization Algorithms ResearchOptimal Power Flow DistributionElectric Power System Optimization

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

Open access
Bose, Subhonmesh, Gayme, Dennice F., Chandy, K. Mani, Low, Steven H.·2012·arXiv
DOI 10.48550/arxiv.1203.5599arXiv 1203.5599
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1203.5599

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Prior sufficient conditions for exactness of the SOCP relaxation require load over-satisfaction on some or all buses and do not hold in practice.

    “these conditions require some bus to be able to draw infinite power, which is referred to as load over-satisfaction in the literature. For example, the conditions given in [9], [13], [14] require load over-satisfaction on some/all of the buses.”

    From Optimal power flow in distribution networks (2018) · cites this paper as [14]

    Section III-C (p. 18) describes exact-relaxation conditions that remove load bounds and calls this “load oversatisfaction”; its examples remove bounds at some or all buses. The paper’s own result concerns a semidefinite relaxation, while Prior work (p. 13) reports SOCP exactness under either no upper bounds on loads or no upper bounds on voltage magnitudes. Our copy does not say these conditions do not hold in practice. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 60

  1. [1][1] F. Alizadeh, 'Interior point methods in semidefinite programming with applications to combinatorial optimization,' SIAM J. on Optimization , vol. 5, no. 1, pp. 13-51, 1995. -
  2. [2][2] Y. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex programming . Society for Industrial Mathematics, 1987, vol. 13. -
  3. [3][3] --, 'Polynomial barrier methods in convex programming,' Ekonom. i Mat. Metody , vol. 24, no. 6, pp. 1084-1091, 1988. -
  4. [4][4] Z. Luo, W. Ma, A. So, Y. Ye, and S. Zhang, 'Semidefinite relaxation of quadratic optimization problems,' Signal Processing Magazine, IEEE , vol. 27, no. 3, pp. 20 -34, May 2010. -
  5. [5][5] H. Wolkowicz, R. Saigal, and L. Vandenberghe, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications . Springer Netherlands, 2000, vol. 27. -
  6. [6][6] A. Gershman, N. Sidiropoulos, S. Shahbazpanahi, M. Bengtsson, and B. Ottersten, 'Convex optimization-based beamforming,' Signal Processing Magazine, IEEE , vol. 27, no. 3, pp. 62-75, 2010. -
  7. [7][7] N. Sidiropoulos, T. Davidson, and Z. Luo, 'Transmit beamforming for physical-layer multicasting,' IEEE Trans.on Signal Processing , vol. 54, no. 6, pp. 2239-2251, 2006. -
  8. [8][8] A. So, Y. Ye, and J. Zhang, 'A unified theorem on SDP rank reduction,' Mathematics of Operations Research , vol. 33, no. 4, pp. 910-920, 2008. -
  9. [9][9] Y. Huang and D. Palomar, 'Rank-constrained separable semidefinite programming with applications to optimal beamforming,' IEEE Trans. on Signal Processing , vol. 58, no. 2, pp. 664-678, 2010. -
  10. [10][10] P. Biswas, T. Lian, T. Wang, and Y. Ye, 'Semidefinite programming based algorithms for sensor network localization,' ACM Trans. on Sensor Networks (TOSN) , vol. 2, no. 2, pp. 188-220, 2006. -
  11. [11][11] M. McCoy and J. Tropp, 'Two proposals for robust PCA using semidefinite programming,' Electronic J. of Statistics , vol. 5, pp. 1123-1160, 2011. -
  12. [12][12] A. Ljapunov and ´ E. Davaux, Probl` eme g´ en´ eral de la stabilit´ e du mouvement . Princeton Univ. Press, 1949. -
  13. [13][13] S. Boyd, L. El-Ghaoui, E. Feron, V. Balakrishnan, and E. Yaz, 'Linear matrix inequalities in system and control theory,' Proce. of the IEEE , vol. 85, no. 4, pp. 698-699, 1997. -
  14. [14][14] S. Boyd, L. Vandenberghe et al. , 'Semidefinite programming relaxations of non-convex problems in control and combinatorial optimization,' Comm., Computation, Ctrl. and Signal Processing: A Tribute to Thomas Kailath , pp. 279-288, 1997. -
  15. [15][15] S. Kim and M. Kojima, 'Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations,' Computational Optimization and Applications , vol. 26, no. 2, pp. 143-154, 2003. -
  16. [16][16] S. Zhang, 'Quadratic maximization and semidefinite relaxation,' Mathematical Programming , vol. 87, no. 3, pp. 453-465, 2000. -
  17. [17][17] M. Goemans and D. Williamson, 'Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,' J. of the ACM (JACM) , vol. 42, no. 6, pp. 1115-1145, 1995. -
  18. [18][18] A. Frieze and M. Jerrum, 'Improved approximation algorithms for max-cut and max bisection,' Algorithmica , vol. 18, no. 1, pp. 67-81, 1997. -
  19. [19][19] D. Karger, R. Motwani, and M. Sudan, 'Approximate graph coloring by semidefinite programming,' J. of the ACM (JACM) , vol. 45, no. 2, pp. 246-265, 1998. -
  20. [20][20] Y. Ye, 'Approximating quadratic programming with bound and quadratic constraints,' Mathematical Programming , vol. 84, no. 2, pp. 219-226, 1999. -
  21. [22][22] Y. Nesterov, 'Semidefinite relaxation and nonconvex quadratic optimization,' Optimization methods and software , vol. 9, no. 1-3, pp. 141-160, 1998. -
  22. [23][23] J. Carpentier, 'Contribution to the economic dispatch problem,' Bulletin de la Societe Francoise des Electriciens , vol. 3, no. 8, pp. 431-447, 1962, in French. -
  23. [25][25] M. Huneault and F. D. Galiana, 'A survey of the optimal power flow literature,' IEEE Trans. on Power Systems , vol. 6, no. 2, pp. 762-770, 1991. -
  24. [26][26] J. A. Momoh, M. E. El-Hawary, and R. Adapa, 'A review of selected optimal power flow literature to 1993. Part I: Nonlinear and quadratic programming approaches,' IEEE Trans. on Power Systems , vol. 14, no. 1, pp. 96-104, 1999. -
  25. [27][27] --, 'A review of selected optimal power flow literature to 1993. Part II: Newton, linear programming and interior point methods,' IEEE Trans. on Power Systems , vol. 14, no. 1, pp. 105 - 111, 1999. -
  26. [28][28] K. S. Pandya and S. K. Joshi, 'A survey of optimal power flow methods,' J. of Theo. and Applied Info. Tech. , vol. 4, no. 5, pp. 450-458, 2008. -
  27. [29][29] X. Bai, H. Wei, K. Fujisawa, and Y. Wang, 'Semidefinite programming for optimal power flow problems,' Int'l J. of Electrical Power & Energy Systems , vol. 30, no. 6-7, pp. 383-392, 2008. -
  28. [30][30] X. Bai and H. Wei, 'Semi-definite programming-based method for security-constrained unit commitment with operational and optimal power flow constraints,' IET Generation, Transmission & Distribution , vol. 3, no. 2, pp. 182-197, 2009. -
  29. [31][31] J. Lavaei and S. Low, 'Zero duality gap in optimal power flow problem,' IEEE Trans. on Power Systems, To Appear , vol. 27, no. 1, pp. 92-107, 2012. -
  30. [32][32] S. Bose, D. F. Gayme, S. H. Low, and K. M. Chandy, 'Optimal power flow over tree networks,' in Proc. of the Allerton Conf. on Comm., Ctrl. and Computing , 2011. -
  31. [33][33] B. Zhang and D. Tse, 'Geometry of feasible injection region of power networks,' in Proc. of the Allerton Conf. on Comm., Ctrl. and Computing , 2011. -
  32. [34][34] S. Sojoudi and J. Lavaei, 'Physics of power networks makes hard optimization problems easy to solve,' in IEEE Power & Energy Society (PES) General Meeting , July 2012. -
  33. [36][36] S. Boyd and L. Vandenberghe, Convex Optimization . Cambridge Univ. Press, 2004. -
  34. [37][37] Y. C. de Verdi'ere, 'Multiplicities of eigenvalues and tree-width graphs,' J. of Combinatorial Theory , vol. 74, p. 121146, 1998, series B. -
  35. [38][38] H. van der Holst, 'Graphs whose positive semidefinite matrices have nullity at most two,' Linear Algebra and its Applications , vol. 375, pp. 1-11, 2003. -
  36. [39][39] C. Johnson, A. Leal Duarte, C. Saiago, B. Sutton, and A. Witt, 'On the relative position of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graph,' Linear Algebra and its Applications , vol. 363, pp. 147-159, 2003. -
  37. [40][40] J. Bonnans and A. Shapiro, 'Optimization problems with perturbations: A guided tour,' SIAM review , vol. 40, no. 2, pp. 228-264, 1998. -
  38. [41][41] E. Yıldırım and M. Todd, 'Sensitivity analysis in linear programming and semidefinite programming using interior-point methods,' Mathematical Programming , vol. 90, no. 2, pp. 229-261, 2001. -
  39. [42][42] R. Horn and C. Johnson, Matrix Analysis . Cambridge Univ. Press, 2005. -
  40. [43][43] G. Dantzig, A. Orden, and P. Wolfe, 'The generalized simplex method for minimizing a linear form under linear inequality restraints,' Pacific Journal of Mathematics , vol. 5, no. 2, pp. 183-195, 1955. -
  41. [44][44] G. Torres and V. Quintana, 'An interior-point method for nonlinear optimal power flow using voltage rectangular coordinates,' Power Systems, IEEE Transactions on , vol. 13, no. 4, pp. 1211-1218, 1998. -
  42. [45][45] I. Nejdawi, K. Clements, and P. Davis, 'An efficient interior point method for sequential quadratic programming based optimal power flow,' Power Systems, IEEE Transactions on , vol. 15, no. 4, pp. 1179-1183, 2000. -
  43. [46][46] R. Jabr, 'A primal-dual interior-point method to solve the optimal power flow dispatching problem,' Optimization and Engineering , vol. 4, no. 4, pp. 309-336, 2003. -
  44. [48][48] J. Lavaei, 'Zero duality gap for classical opf problem convexifies fundamental nonlinear power problems,' in Proc. of the American Ctrl. Conf. , 2011. -
  45. [49][49] B. Lesieutre, D. Molzahn, A. Borden, and C. L. DeMarco, 'Examining the limits of the application of semidefinite programming to power flow problems,' in Proc. of the Allerton Conf. on Comm., Ctrl. and Computing , 2011. -
  46. [50][50] I. A. Hiskens and R. Davy, 'Exploring the power flow solution space boundary,' IEEE Trans. on Power Systems , vol. 16, no. 3, pp. 389-395, 2001. -
  47. [51][51] B. C. Lesieutre and I. A. Hiskens, 'Convexity of the set of feasible injections and revenue adequacy in FTR markets,' IEEE Trans. on Power Systems , vol. 20, no. 4, pp. 1790-1798, 2005. -
  48. [52][52] Y. V. Makarov, Z. Y. Dong, and D. J. Hill, 'On convexity of power flow feasibility boundary,' IEEE Trans. on Power Systems , vol. 23, no. 2, pp. 811-813, May 2008. -
  49. [53][53] M. E. Baran and F. F. Wu, 'Optimal capacitor placement on radial distribution systems,' IEEE Trans. on Power Delivery , vol. 4, no. 1, pp. 725-734, 1989. -
  50. [54][54] --, 'Optimal sizing of capacitors placed on a radial distribution system,' IEEE Trans. on Power Delivery , vol. 4, no. 1, pp. 735-743, 1989. -
  51. [55][55] J. A. Taylor, 'Conic optimization of electric power systems,' Ph.D. dissertation, MIT, June 2011. -
  52. [56][56] R. Jabr, 'Radial distribution load flow using conic programming,' IEEE Trans. on Power Systems , vol. 21, no. 3, pp. 1458-1459, Aug. 2006. -
  53. [57][57] M. Farivar, C. R. Clarke, S. H. Low, and K. M. Chandy, 'Inverter VAR control for distribution systems with renewables,' in Int'l Conf. on Smart Grid Comm. (SmartGridComm) , 2011. -
  54. [58][58] L. Gan, N. Li, U. Topcu, and S. H. Low, 'Branch flow model for radial networks: convex relaxation,' in 51st IEEE Conference on Decision and Control , December 2012. -
  55. [59][59] N. Li, L. Chen, and S. H. Low, 'Exact convex relaxation of OPF for radial networks using branch flow model,' in IEEE International Conference on Smart Grid Communications , November 2012. -
  56. [60][60] M. Farivar and S. H. Low, 'Branch flow model: relaxations and convexification,' in 51st IEEE Conference on Decision and Control , December 2012. -
  57. [61][61] S. Bose, S. H. Low, and K. M. Chandy, 'Equivalence of branch flow and bus injection models,' in Proc. of the Allerton Conf. on Comm., Ctrl. and Computing , October 2012. -
  58. [62][62] J. Lofberg, 'YALMIP: A toolbox for modeling and optimization in MATLAB,' in IEEE Int'l Symposium on Computer Aided Ctrl. Systems Design . IEEE, 2004, pp. 284-289. -
  59. [64][64] K. Turitsyn, P. S˘ ulc, S. Backhaus, and M. Chertkov, 'Options for control of reactive power by distributed photovoltaic generators,' Proc. of the IEEE , vol. 99, no. 6, pp. 1063 -1073, June 2011. -
  60. [65][65] D. F. Yeh, H.-G.and Gayme and S. H. Low, 'Adaptive VAR control for distribution circuits with photovoltaic generator,' IEEE Trans. on Power Systems, to appear , 2012.

Cited by

Sorted by citations

Authors
Bose, S., Gayme, D. F., Chandy, K. M., & Low, S. H.
Affiliations
  • Cornell University (US)
  • Johns Hopkins University (US)
  • California Institute of Technology (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2012
Volume
2
Issue
3
Pages
278-287
ISSN
2325-5870 (ISSN-L)
DOI
10.48550/arxiv.1203.5599
arXiv
1203.5599
OpenAlex
W2159935945
Cited by
131
References
0
Citations by year
2026: 2 · 2024: 3 · 2023: 5 · 2022: 6 · 2021: 8 · 2020: 3 · 2019: 14 · 2018: 11 · 2017: 10 · 2016: 10 · 2015: 14 · 2014: 22 · 2013: 17 · 2012: 6
FWCI
16.92
Type
journal article
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • IEEE Transactions on Control of Network Systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • CaltechAUTHORS (California Institute of Technology) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (0911041)
  • Cisco Systems
  • National Science Council (103-3113-P-008-001)
Topics
  • Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
  • Physical Sciences › Engineering › Electrical and Electronic Engineering › Optimal Power Flow Distribution
  • Physical Sciences › Engineering › Electrical and Electronic Engineering › Electric Power System Optimization
Keywords
quadratically constrained quadratic programming, acyclic graphs, polynomial-time solvability, non-convex optimization, optimal power flow, tree networks, power systems

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review