The manuscript addresses the problem of finding all solutions of power flow equations or other similar non-linear system of algebraic equations. This problem arises naturally in a number of power systems contexts, most importantly the direct methods for transient stability analysis and voltage stability assessment. Here, the authors introduce a novel form of homotopy continuation method called the numerical polynomial homotopy continuation method that is mathematically guaranteed to find all the solutions without ever encountering a bifurcation. Since finding real solutions is much more challenging, first the authors embed the real form of power flow equation in complex space, and then track the generally unphysical solutions with complex values of real and imaginary parts of the voltages. The solutions converge to physical real form in the end of the homotopy. The so-called gamma-trick mathematically rigorously ensures that all the paths are well-behaved along the paths, so unlike other continuation approaches, no special handling of bifurcations is necessary. The method is embarrassingly parallelisable. The authors demonstrate the technique performance by solving several test cases up to the 14 buses. Finally, they discuss possible strategies for scaling the method to large size systems, and propose several applications for security assessments.

References

1. 1)
  - 30. Molzahn, D.K., Mehta, D., Niemerg, M.: ‘Toward topologically based upper bounds on the number of power flow solutions’, 2015, arXiv preprint arXiv:1509.09227.
2. 2)
  - 16. Hughes, C., Mehta, D., Skullerud, J.-I.: ‘Enumerating Gribov copies on the lattice’, Ann. Phys., 2013, 331, pp. 188–215 (doi: 10.1016/j.aop.2012.12.011).
3. 3)
  - 62. Dinh, H.N., Yoon, Y.T., Nguyen, M.Y.: ‘A new approach for corrective and preventive control to unsolvable case in power networks having DERs’, J. Electr. Eng. Technol., 2013, 8, (3), pp. 411–420 (doi: 10.5370/JEET.2013.8.3.411).
4. 4)
  - 5. Chiang, H.-D., Fekih-Ahmed, L.: ‘On the direct method for transient stability analysis of power system structure preserving models’. IEEE Int. Symp. on Circuits and Systems, 1992, ISCAS ‘92. Proc., 1992, 1992, pp. 2545–2548.
5. 5)
  - 59. Overbye, T., De Marco, C.: ‘Voltage security enhancement using energy based sensitivities’, IEEE Trans. Power Syst., 1991, 6, (3), pp. 1196–1202 (doi: 10.1109/59.119266).
6. 6)
  - 5. Ajjarapu, V., Christy, C.: ‘The continuation power flow: a tool for steady state voltage stability analysis’, IEEE Trans. Power Syst., 1992, 7, (1), pp. 416–423 (doi: 10.1109/59.141737).
7. 7)
  - 4. Varaiya, P., Wu, F.F., Chen, R.L.: ‘Direct methods for transient stability analysis of power systems: recent results’. Proc. IEEE, 1985, pp. 1703–1715.
8. 8)
  - 35. Bates, D.J., Hauenstein, J.D., Sommese, A.J., et al: ‘Adaptive multiprecision path tracking’, SIAM J. Numer. Anal., 2008, 46, (2), pp. 722–746 (doi: 10.1137/060658862).
9. 9)
  - 25. Mehta, D., Stariolo, D.A., Kastner, M.: ‘Energy landscape of the finite-size spherical three-spin glass model’, Phys. Rev., 2013, E87, (5), p. 052143.
10. 10)
  - 23. Martinez-Pedrera, D., Mehta, D., Rummel, M., et al: ‘Finding all flux vacua in an explicit example’, J. High Energy Phys., 2013, 1306, p. 110 (doi: 10.1007/JHEP06(2013)110).
11. 11)
  - 13. Mori, H., Yuihara, A.: ‘Calculation of multiple power flow solutions with the krawczyk method’. Proc. 1999 IEEE Int. Symp. on Circuits and Systems, 1999, ISCAS'99, 1999, vol. 5, pp. 94–97.
12. 12)
  - 61. Nguyen, H., Turitsyn, D.K.: ‘Voltage multistability and pulse emergency control for distribution system with power flow reversal’, 2014, arXiv preprint arXiv:1407.1355.
13. 13)
  - 36. Morgan, A., Sommese, A.: ‘A homotopy for solving general polynomial systems that respects m-homogeneous structures’, Appl. Math. Comput., 1987, 24, (2), pp. 101–113.
14. 14)
  - 63. Zobian, A., Ilic, M.: ‘A steady state voltage monitoring and control algorithm using localized least square minimization of load voltage deviations’, IEEE Trans. Power Syst., 1996, 11, (2), pp. 929–938 (doi: 10.1109/59.496177).
15. 15)
  - 34. Bates, D.J., Hauenstein, J.D., Sommese, A.J.: ‘Efficient path tracking methods’, Numer. Algorithms, 2011, 58, (4), pp. 451–459 (doi: 10.1007/s11075-011-9463-8).
16. 16)
  - 55. Lee, J.: ‘Dynamic gradient approaches to compute the closest unstable equilibrium point for stability region estimate and their computational limitations’, IEEE Trans. Autom. Control, 2003, 48, (2), pp. 321–324 (doi: 10.1109/TAC.2002.808492).
17. 17)
  - 9. Mehta, D., Molzahn, D.K., Turitsyn, K.: ‘Recent advances in computational methods for the power flow equations’, 2015, arXiv preprint arXiv:1510.00073.
18. 18)
  - 26. Greene, B., Kagan, D., Masoumi, A., et al: ‘Tumbling through a landscape: evidence of instabilities in high-dimensional moduli spaces’, Phys. Rev., 2013, D88, (2), p. 026005.
19. 19)
  - 1. Kundur, P.: ‘Power system stability and control’ (New York, 1994).
20. 20)
  - 21. Hauenstein, J., He, Y.H., Mehta, D.: ‘Numerical elimination and moduli space of vacua’, J. High Energy Phys., 2013, 1309, p. 083 (doi: 10.1007/JHEP09(2013)083).
21. 21)
  - 53. Lee, J.: ‘A novel homotopy-based algorithm for the closest unstable equilibrium point method in nonlinear stability analysis’. Proc. 2003 Int. Symp. on Circuits and Systems, 2003, ISCAS ‘03, 2003, pp. III–8.
22. 22)
  - 32. Sommese, A., Wampler, C.: ‘The numerical solution of systems of polynomials arising in engineering and science’ (World Scientific Publishing Company, 2005).
23. 23)
  - 40. Bates, D., Hauenstein, J., Sommese, A., et al: ‘Bertini: software for numerical algebraic geometry’.
24. 24)
  - 65. Sun, H., Guo, Q., Zhang, B., et al: ‘Master–slave-splitting based distributed global power flow method for integrated transmission and distribution analysis’, IEEE Trans. Smart Grid, 2015, 6, (3), pp. 1484–1492 (doi: 10.1109/TSG.2014.2336810).
25. 25)
  - 44. Gao, T., Li, T.Y., Wu, M.: ‘Algorithm 846: Mixedvol: a software package for mixed-volume computation’, ACM Trans. Math. Softw., 2005, 31, (4), pp. 555–560 (doi: 10.1145/1114268.1114274).
26. 26)
  - 7. Van Cutsem, T., Vournas, C.: ‘Voltage stability of electric power systems’ (Springer, 1998), vol. 441.
27. 27)
  - 19. Maniatis, M., Mehta, D.: ‘Minimizing Higgs potentials via numerical polynomial homotopy continuation’, Eur. Phys. J. Plus, 2012, 127, p. 91 (doi: 10.1140/epjp/i2012-12091-1).
28. 28)
  - 66. Li, T.Y., Wang, X.: ‘The BKK root count in Cn’, Math. Comput., 1996, 65, pp. 1477–1484 (doi: 10.1090/S0025-5718-96-00778-8).
29. 29)
  - 52. Liu, C.-W., Thorp, J.S.: ‘A novel method to compute the closest unstable equilibrium point for transient stability region estimate in power systems’, IEEE Trans. Circuits Syst. I, Fundam. Theory Appl., 1997, 44, (7), pp. 630–635 (doi: 10.1109/81.596944).
30. 30)
  - 3. Kakimoto, N., Ohnogi, Y., Matsuda, H., et al: ‘Transient stability analysis of large-scale power system by Lyapunov's direct method’, IEEE Trans. Power Appar. Syst., 1984, (1), pp. 160–167 (doi: 10.1109/TPAS.1984.318594).
31. 31)
  - 67. Rojas, J.M.: ‘A convex geometric approach to counting the roots of a polynomial system’, Theor. Comput. Sci., 1994, 133, (1), pp. 105–140 (doi: 10.1016/0304-3975(93)00062-A).
32. 32)
  - 27. Liu, C.-W., Chang, C.-S., Jiang, J.-A., et al: ‘Toward a cpflow-based algorithm to compute all the type-1 load-flow solutions in electric power systems’, IEEE Trans. Circuits Syst. I, Regul. Pap., 2005, 52, (3), pp. 625–630 (doi: 10.1109/TCSI.2004.842883).
33. 33)
  - 38. Khovanski, A.G.: ‘Newton polyhedra and the genus of complete intersections’, Funkts. Anal. Pril., 1978, 12, (1), pp. 51–61.
34. 34)
  - 64. Cvijić, S., Ilić, M.: ‘Distributed multiparty dc power flow algorithm with secure exchange of information’, in (Eds.): ‘Control of cyber-physical systems’ (Springer, 2013), pp. 241–258.
35. 35)
  - 10. Salam, F.M.A., Ni, L., Guo, S., et al: ‘Parallel processing for the load flow of power systems: the approach and applications’. Proc. 28th IEEE Conf. on Decision and Control, 1989, 1989, vol. 3, pp. 2173–2178.
36. 36)
  - 33. Li, T.: ‘Solving polynomial systems by the homotopy continuation method’, in (Cucker, F., Ciarlet, P. Eds.): ‘Handbook of numerical analysis’ (North-Holland, 2003), vol. XI, pp. 209–304.
37. 37)
  - 51. Chiang, H.-D., Thorp, J.S.: ‘The closest unstable equilibrium point method for power system dynamic security assessment’, IEEE Trans. Circuits Syst., 1989, 36, (9), pp. 1187–1200 (doi: 10.1109/31.34664).
38. 38)
  - 57. Yorino, N., Popov, E., Zoka, Y., et al: ‘An application of critical trajectory method to BCU problem for transient stability studies’, IEEE Trans. Power Syst., 2013, 28, (4), pp. 4237–4244 (doi: 10.1109/TPWRS.2013.2256376).
39. 39)
  - 46. Chow, S.N., Mallet-Paret, J., Yorke, J.A.: ‘Finding zeroes of maps: homotopy methods that are constructive with probability one’, Math. Comput., 1978, 32, (143), pp. 887–899 (doi: 10.1090/S0025-5718-1978-0492046-9).
40. 40)
  - 37. Bernstein, D.N.: ‘The number of roots of a system of equations’, Funkts. Anal. Pril., 1975, 9, pp. 1–4 (doi: 10.1007/BF01078167).
41. 41)
  - 2. Ma, W., Thorp, J.: ‘An efficient algorithm to locate all the load flow solutions’, IEEE Trans. Power Syst., 1993, 8, (3), pp. 1077–1083 (doi: 10.1109/59.260891).
42. 42)
  - 17. Mehta, D., Sternbeck, A., von Smekal, L., et al: ‘Lattice landau gauge and algebraic geometry’, PoS, 2009, QCD-TNT09, p. 025.
43. 43)
  - 24. He, Y.H., Mehta, D., Niemerg, M., et al: ‘Exploring the potential energy landscape over a large parameter-space’, J. High Energy Phys., 2013, 1307, p. 050 (doi: 10.1007/JHEP07(2013)050).
44. 44)
  - 29. Chandra, S., Mehta, D., Chakrabortty, A.: ‘Exploring the impact of wind penetration on power system equilibrium using a numerical continuation approach’, 2014, arXiv preprint arXiv:1409.7844.
45. 45)
  - 39. Kushnirenko, A.G.: ‘Newton polytopes and the bezout theorem’, Funkts. Anal. Pril., 1976, 10, (3), pp. 82–83.
46. 46)
  - 6. Chiang, H.-D.: ‘Direct Methods for Stability Analysis of Electric Power Systems: Theoretical Foundation, BCU Methodologies, and Applications’, (John Wiley & Sons, Hoboken, NJ, USA, 2011).
47. 47)
  - 15. Mehta, D.: ‘Lattice vs. continuum: landau gauge fixing and ‘t Hooft-Polyakov monopoles’, PhD thesis, 2009.
48. 48)
  - 20. Mehta, D., He, Y.H., Hauenstein, J.D.: ‘Numerical algebraic geometry: a new perspective on string and gauge theories’, J. High Energy Phys., 2012, 1207, p. 018 (doi: 10.1007/JHEP07(2012)018).
49. 49)
  - 47. Chow, S.-N., Mallet-Paret, J., Yorke, J.A.: ‘A homotopy method for locating all zeros of a system of polynomials’, in (Peitgen, H.O., Walther, H.O. Eds.): ‘Functional differential equations and approximation of fixed points’ (Springer, 1979), pp. 77–88.
50. 50)
  - 42. Gunji, T., Kim, S., Kojima, M., et al: ‘Phom – a polyhedral homotopy continuation method for polynomial systems’, Computing, 2004, 73, (1), pp. 57–77 (doi: 10.1007/s00607-003-0032-4).
51. 51)
  - 45. Lee, L.T.Y., Tsai, T.L.C.H.: ‘Hom4ps-2.0, a software package for solving polynomial systems by the polyhedral homotopy continuation method, preprint’, 2008.
52. 52)
  - 41. Verschelde, J.: ‘Algorithm 795: Phcpack: a general-purpose solver for polynomial systems by homotopy continuation’, ACM Trans. Math. Softw., 1999, 25, (2), pp. 251–276 (doi: 10.1145/317275.317286).
53. 53)
  - 54. Lee, J., Chiang, H.-D.: ‘A singular fixed-point homotopy method to locate the closest unstable equilibrium point for transient stability region estimate’, IEEE Trans. Circuits Syst. II, Express Briefs, 2004, 51, (4), pp. 185–189 (doi: 10.1109/TCSII.2004.824058).
54. 54)
  - 49. Prasad, G.D., Jana, A., Tripathy, S.: ‘Modifications to Newton–Raphson load flow for ill-conditioned power systems’, Int. J. Electr. Power Energy Syst., 1990, 12, (3), pp. 192–196 (doi: 10.1016/0142-0615(90)90032-7).
55. 55)
  - 43. Morgan, S.A.J., Watson, A.P.L.T.: ‘Finding all isolated solutions to polynomial systems using hompack’, ACM Trans. Math. Softw., 1989, 15, (2), pp. 93–122 (doi: 10.1145/63522.64124).
56. 56)
  - 8. Nguyen, H., Turitsyn, K.: ‘Voltage multistability and pulse emergency control for distribution system with power flow reversal’, IEEE Trans. Smart Grid, 2015, 6, (6), pp. 2985–2996 (doi: 10.1109/TSG.2015.2419880).
57. 57)
  - 50. ‘Power systems test case archive’. Available at http://www.ee.washington.edu/research/pstca/.
58. 58)
  - 14. Molzahn, D.K., Lesieutre, B.C., Chen, H.: ‘Counterexample to a continuation-based algorithm for finding all power flow solutions’, IEEE Trans. Power Syst., 2013, 28, (1), pp. 564–565 (doi: 10.1109/TPWRS.2012.2202205).
59. 59)
  - 48. Taylor, C., Balu, N., Maratukulam, D.: ‘Power system voltage stability’, The EPRI power system engineering series.
60. 60)
  - 18. Mehta, D.: ‘Numerical polynomial homotopy continuation method and string vacua’, Adv. High Energy Phys., 2011, 2011, p. 263937 (doi: 10.1155/2011/263937).
61. 61)
  - 22. Mehta, D., Hauenstein, J.D., Kastner, M.: ‘Energy landscape analysis of the two-dimensional nearest-neighbor phi4 model’, Phys. Rev., 2012, E85, p. 061103.
62. 62)
  - 58. Hristov, P.E., Yorino, N., Zoka, Y., et al: ‘Robust method for detection of CUEP for power system transient stability screening’. Fourth IEEE/PES Innovative Smart Grid Technologies Europe (ISGT EUROPE), 2013, 2013, pp. 1–5.
63. 63)
  - 28. Chandra, S., Mehta, D., Chakrabortty, A.: ‘Equilibria analysis of power systems using a numerical homotopy method’. IEEE Power & Energy Society General Meeting, 2015, 2015, pp. 1–5.
64. 64)
  - 11. Castro, J., Montes, A.: ‘Solving the load flow problem using gröbner basis’.
65. 65)
  - 68. Rojas, J.M., Wang, X.: ‘Counting affine roots of polynomial systems via pointed Newton polytopes’, J. Complexity, 1996, 12, (2), pp. 116–133 (doi: 10.1006/jcom.1996.0009).
66. 66)
  - 56. Chen, L., Min, Y., Xu, F., et al: ‘A continuation-based method to compute the relevant unstable equilibrium points for power system transient stability analysis’, IEEE Trans. Power Syst., 2009, 24, (1), pp. 165–172 (doi: 10.1109/TPWRS.2008.2009395).
67. 67)
  - 12. Nguyen, H.D., Turitsyn, K.S.: ‘Appearance of multiple stable load flow solutions under power flow reversal conditions’. Power and Energy Society General Meeting, 2014.
68. 68)
  - 60. Overbye, T., Demarco, C.: ‘Improved techniques for power system voltage stability assessment using energy methods’, IEEE Trans. Power Syst., 1991, 6, (4), pp. 1446–1452 (doi: 10.1109/59.116988).

Numerical polynomial homotopy continuation method to locate all the power flow solutions

References

Related content