Physics of power networks makes hard optimization problems easy to solve
Physics of power networks makes hard optimization problems easy to solve
复制标题
DOI：
10.1109/pesgm.2012.6345272
复制
发表时间：
2012-07
期刊：
影响因子：
--
通讯作者：
S. Sojoudi;J. Lavaei
中科院分区：
文献类型：
--
作者：
S. Sojoudi;J. Lavaei
我们最近观察并证明了具有二次成本函数的最优潮流（OPF）问题可以在多项式时间内解决，其中包括IEEE基准系统。在本工作中，我们将之前的结果推广到具有任意凸代价函数的OPF，从而提供了更严格的理论基础。首先，通过其拉格朗日对偶得到了OPF在多项式时间内可解的充分必要条件。由于求解OPF的对偶对于大规模网络来说是昂贵的，因此利用电网图的稀疏性，设计了一种具有更高可扩展性的算法。该算法的计算复杂度与网络的循环数有关。此外，由于电网的物理特性，本文提出的多项式时间算法总是能精确地解决所有的全交流OPF问题，或者经过两次轻微的修改。
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.