Physics of power networks makes hard optimization problems easy to solve
- Creators
- Sojoudi, Somayeh
- Lavaei, Javad
Abstract
We have recently observed and justified that the optimal power flow (OPF) problem with a quadratic cost function may be solved in polynomial time for a large class of power networks, including IEEE benchmark systems. In this work, our previous result is extended to OPF with arbitrary convex cost functions and then a more rigorous theoretical foundation is provided accordingly. First, a necessary and sufficient condition is derived to guarantee the solvability of OPF in polynomial time through its Lagrangian dual. Since solving the dual of OPF is expensive for a large-scale network, a far more scalable algorithm is designed by utilizing the sparsity in the graph of a power network. The computational complexity of this algorithm is related to the number of cycles of the network. Furthermore, it is proved that due to the physics of a power network, the polynomial-time algorithm proposed here always solves every full AC OPF problem precisely or after two mild modifications.
Additional Information
© 2012 IEEE. Date of Current Version: 10 November 2012; Issue Date: 22-26 July 2012. We would like to gratefully acknowledge Masoud Farivar, Steven H. Low and Rabih Jabr for discussions and suggestions.Additional details
- Eprint ID
- 35569
- Resolver ID
- CaltechAUTHORS:20121120-114854050
- Created
-
2012-11-20Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field