Communication and Power Networks: Flow Optimization (Part II)

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:

  1. 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.
  2. 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.
  3. 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.

For details of the first two questions, see a 2-part tutorial on convex relaxation of OPF, or their extended version with proofs: Part I  and  Part II.

 

Advertisements

4 thoughts on “Communication and Power Networks: Flow Optimization (Part II)

  1. Thanks Steven for these great posts on optimal power flow (a problem new to me), and for the links to the tutorials. As a thought, the one (and only?) trick I’ve had repeated success applying to nonconvex optimization problems is to establish uniqueness of the local optima by the mountain pass theorem. Succinctly phrased (technical details omitted), if all stationary points are local minima, then there can be only one local minima, and it is the only global minima. If a problem has this structure (all stationary points are minima) then hill-climbing algorithms are again admissible. So: might there be some conditions on the OPF problem where the local optima are unique in this way? I have no idea, but thought I’d suggest the approach.

    As a second point, you say “it is NP-hard to minimize it over a nonconvex feasible set” — it would be more accurate to say “over a general nonconvex feasible set”, and the complexity challenge can be thought of as determining if there’s some polynomial-time/tractable subset of nonconvexity that OPF falls within.

    Lastly, You might be interested in this recent paper by Chandrasekaran and Jordan that formulates a statistical risk-based approach to convex relaxations: V Chandrasekaran, MI Jordan. “Computational and statistical tradeoffs via convex relaxation.” PNAS 2013.

    • Thanks, Johan, for your comments. The idea of mountain pass theorem is interesting; it’d need some thought to see how it can be applied to OPF. Examples are known where OPF has local optima that are not globally optimal (Waqquas A. Bukhsh, Andreas Grothey, Ken McKinnon, and Paul Trodden. Local solutions of optimal power flow. IEEE Trans. Power Systems, 28(4):4780–4788, November 2013.), so the challenge, as you pointed out, is to figure out sufficient conditions that eliminate this.

      Another point though is that, even if the local optimal of the semidefinite relaxation is unique, we need conditions to make sure that it is feasible (and hence optimal) for the original (nonconvex) OPF problem. The sufficient conditions discussed in Part II of my tutorial guarantee that every (global) optimum of the convex relaxation is “feasible” for the original OPF problem. It turns out that this (plus some reasonable conditions) guarantees the optimal is actually unique, for tree networks.

      Your comment on “NP hardness” is excellent. I can’t change the journal version, but I have updated the “extended versions with proofs”, changing from:
      “It is generally nonconvex and hence NP-hard.” to:
      “It is nonconvex and hence NP-hard in general.”
      They will be reflected when I update the version on the web (I try not to do frequent external updates).

      Thanks for the pointer to Venkat and Michael’s very nice paper. I heard Venkat’s talk on an early version. Their focus is on the optimal tradeoff of accuracy and computation, as available data increase. A related (but different) idea on OPF is, when the first-order (SDP) relaxation is not exact, whether/how one can go up the hierarchy of polynomial optimization for more and more accurate relaxations at the expense of (significant) computational effort. There is some very nice initial work on this by Molzahn and Hiskens (PSCC 2014), Josz et al (arXiv 2013) at INRIA and French operator RTE, and Ghaddar, Marecek, and Mevissen (arXiv 2014) at IBM Research, Dublin.

      In short, OPF is an important problem with a rich structure that is waiting to be explored more thoroughly!

      • Thanks for your thoughtful response and interesting references, agreed that OPF is important and has subtle structure ripe for exploration!

  2. Pingback: Rigor + Relevance | Communication and Power Networks: Flow Optimization (Part I)

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s