In Part I of this post, we have seen that the optimal power flow (OPF) problem in electricity networks is much more difficult than congestion control on the Internet, because OPF is nonconvex. In Part II, I will explain where the nonconvexity comes from, and how to deal with it.
Source of nonconvexity
Let’s again start with congestion control, which is a convex problem.
As mentioned in Part I, corresponding to each congestion control protocol is an optimization problem, called network utility maximization. It takes the form of maximizing a utility function over sending rates subject to network capacity constraints. The utility function is determined by the congestion control protocol: a different design to adapt the sending rate of a computer to congestion implies a different utility function that the protocol implicitly maximizes. The utility function is always increasing in the sending rates, and therefore, a congestion control protocol tends to push the sending rates up in order to maximize utility, but not to exceed network capacity. The key feature that makes congestion control simple is that the utility functions underlying all of the congestion control protocols that people have proposed are concave functions. More importantly, and in contrast to OPF, the network capacity constraint is linear in the sending rates. This means that network utility maximization is a convex problem.
OPF minimizes a convex cost function subject to Kirchhoff’s laws that govern how electric power flows through a network. Kirchhoff’s laws are quadratic, making OPF a nonconvex optimization problem. Indeed, even though the relation (Ohm’s law) between voltages and currents is linear, and power balance is also linear, power flows are quadratic functions of voltages and currents. Therefore, the constraints in OPF involve quadratic equalities, leading to nonconvexity (as opposed to linear constraints in congestion control). There are other forms of nonconvexity in different OPF problems, but the nonconvexity due to Kirchhoff’s laws is the most fundamental and present in all OPF variants, because it is part of our physical world.
An exciting new approach to solving OPF has been developed in the last few years, and remains an active research topic. This approach is based on the idea of convex relaxation, and offers several advantages. Let me first summarize the advantages, and then outline the basic idea of convex relaxation of OPF.
Advantages of convex relaxation
OPF was first formulated in 1962 by French researcher J. Carpentier. Since then, a large number of solution methods have been proposed. The most widely used method is to approximate OPF by a linear program through linearization of the Kirchhoff’s laws, and then solve the resulting linear program instead of the original OPF. This works well for some problems in (long-distance high-voltage) transmission networks, but is inappropriate for many problems in (short-distance lower-voltage) distribution networks. Various nonlinear and heuristic algorithms have also been applied to OPF. Some of them work very well when the algorithms can be initialized to run from a point that is close to an optimal point (“warm start”). Otherwise, such an algorithm may not converge. Moreover, even when it does, there is no guarantee on the quality of the solution; it can be very close to the global optimal or very far away, and there is no way to tell.
In contrast, the convex relaxation approach does not need the assumptions required by the linearization approach, and is thus more widely applicable. It provides for the first time the ability to check whether a solution is globally optimal. If it is not, the solution provides a lower bound on the minimum cost, and hence, a bound on how far any feasible solution is from optimality. Unlike approximations, if a relaxed problem is infeasible, it is a certificate that the original OPF is infeasible.
Basic idea of convex relaxation
The basic idea is simple. OPF minimizes a cost function over the set of power flows that satisfy the nonconvex Kirchhoff’s laws. Let’s call this set of power flows the feasible set of OPF. The crust of the difficulty is that the feasible set is a nonconvex set: while it is easy (polynomial-time computable) to minimize the cost function over a convex feasible set, it is NP-hard to minimize it over a nonconvex feasible set. The idea is then to design a convex superset that contains the nonconvex feasible set, and minimize the cost function over this convex superset instead, which is easy.
This new problem is called a relaxation, because the original feasible set is enlarged to a bigger set. Even though solving this new problem is easy, an optimal solution of the convex relaxation may or may not be feasible for the original OPF. If the optimal solution computed from the relaxation happens to lie in the original (nonconvex) feasible set, then we are in luck – we have found a globally optimal solution of the original OPF! Otherwise, the optimal solution of the relaxation is infeasible for the original OPF; nonetheless, it provides a lower bound on the optimal cost of the original OPF.
The main questions of this approach are therefore:
- How do we design convex supersets of the feasible set of OPF? Different designs lead to different relaxations that have different degrees of tightness and computational complexity.
- Under what condition will a convex relaxation be exact, i.e., every optimal solution of the relaxation is feasible and therefore optimal for the original OPF? Such a condition will guarantee that we can always obtain a global optimal of OPF by solving its convex relaxation.
- How do we solve a convex relaxation of OPF efficiently at scale? Even though a convex relaxation is polynomial-time solvable, it may still be impractical to solve for large networks. Distributed algorithms will be needed for scalability.