Multiple Local Optima of Nonconvex Optimal Power Flow Problem

Introduction to the Optimal Power Flow Problem

The optimal power flow (OPF) problem can be regarded as a relaxed version of the associated power flow problem. Instead of fixing the active power generation and voltage magnitude at each PV node, the OPF problem allows flexbile ranges for these variables. Therefore, an optimal solution may be achieved for a given objective function. Additional constraints beside power balance equations are usually included, for example, the line flow limit, the generator relative angle limit, etc. Many variations of the OPF problem are formulated, such as DCOPF, unit commitment OPF, chance-constrained OPF, security-constrained OPF, etc. 

Nonconvexity of the Optimal Power Flow Problem

The standard OPF problem with AC power balance equations is generically nonconvex. Thus, it can admit multiple local optima. Furthermore, the voltage constraints, line flow limts, and generation limits can cut the feasible space of an OPF problem into several disconnected pieces. 

For example, the above animations illustrate 3-D projections of disconnected feasible spaces for two small OPF examples. Interested readers can find more examples in Empirical Investigation of Non-Convexities in Optimal Power Flow Problems. The method that generates feasible regions of OPF problems can be found in Computing the Feasible Spaces of Optimal Power Flow Problems. Although these examples are just small power grids with 3, 4, and 5 buses, they already exhibit rather complicated geometric structures of their feasible spaces. One can imagine that for a system with thousands of nodes, the situation can be much much more complex.

A Deterministic Method to Systematically Enumerate Alternative OPF Local Optima

One may notice that once a feasible space is separated into several disconnected pieces there must exist at least one optimum on each piece. Hence, the problem admits multiple local optima. Recently convex relaxation techniques, such as semi-definite programming, second order cone programming, moment-based relaxation, are used in the OPF problem to achieve the global optimum. These are very powerful approaches that can ensure to achieve the global solution under certain conditions. However, these conditions are usually very restricted to a certain class of OPF problems. 

To search for a better optimum, one can enumerate multiple OPF optima and select the best from them. A straightforward way uses different random initializations with some local solver to find multiple local optima. However, as the problem size increases, the number of random seeds may increase exponentially to reach a relatively thorough search. To avoid random initializations, a new idea is introduced to deterministically locate multiple local optima. The principle is to make connections between different local optima (first order solutions). Once a local optimum is found, the interlinked solutions are also revealed. Specifically, the connections between different solutions are provided by some 1-D curves. We require these curves to satisfy certain generic properties such as smoothness, boundedness, and closedness. The construction of such curves and the method to visit interlinked solutions are fully discussed in A Deterministic Method to Identify Multiple Local Extrema for the AC Optimal Power Flow Problem. Besides enumerating multiple local solutions which have never been reported before, and finding the global optimum, an interesting property (necessary for highly nonconvex problems) of this approach is that the linking curves can bridge disconnected pieces of the feasible space to do a relative thorough search. The following animation and pictures show particular hard examples which fail the SDP relaxation. Other examples can also be found in the above mentioned paper. Note that this approach can be naturally extended to any bounded quadratic constrained quadratic programming problems. For example, this method has been used to successfully locate the minimum of long-term voltage stability margin, discussions and comparisons can be found in Improving Power System Voltage Stability by Using Demand Response to Maximize the Distance to the Closest Saddle-Node Bifurcation

The left example has four disconnected pieces of the feasible space. Starting from one local solution on one piece, the blue curve leads the searching algorithm to another piece. By following a new green curve, the global solution is reached. 

The middle example has two disconnected pieces of the feasible space. The global optimum resides on the tiny piece of the feasible space which is achieved by following the green curve from the large feasible piece. 

The right example has three disconnected pieces of the feasible space. The global optimum resides on the left hand side piece of the feasible space. We start from the right hand side piece, follow the light blue curve to reach the upper middle feasible piece. Then, we switch the tracing curve to the green one, which leads us to the left hand side feasible piece and locates the global optimum.