A rank minimization algorithm to enhance semidefinite relaxations of Optimal Power Flow

The Optimal Power Flow (OPF) problem is non-convex and, for generic network structures, is NP-hard. A recent flurry of work has explored the use of semidefinite relaxations to solve the OPF problem. For general network structures, however, this approach may fail to yield solutions that are physically meaningful, in the sense that they are high rank - precluding their efficient mapping back to the original feasible set. In certain cases, however, there may exist a hidden rank-one optimal solution. In this paper an iterative linearization-minimization algorithm is proposed to uncover rank-one solutions for the relaxation. The iterates are shown to converge to a stationary point. A simple bisection method is also proposed to address problems for which the linearization-minimization procedure fails to yield a rank-one optimal solution. The algorithms are tested on representative power system examples. In many cases, the linearization-minimization procedure obtains a rank-one optimal solution where the naive semidefinite relaxation fails. Furthermore, a 14-bus example is provided for which the linearization-minimization algorithm achieves a rank-one solution with a cost strictly lower than that obtained by a conventional solver. We close by discussing some rank monotonicity properties of the proposed methodology.