Optimization over graph with application to power systems

Professor Javad Lavaei
Assistant Professor, Columbia University
Given on: January 31, 2013


In this talk, we consider an arbitrary real or complex-valued optimization problem whose variable is a positive semi-definite (PSD) matrix. The objective is to investigate under what conditions this optimization has a low-rank (e.g., rank 1 or 2) solution. The motivation is that a broad class of optimization problems, including polynomial optimization, can be cast as a rank-constrained matrix optimization. To solve the problem, the structure of the optimization is mapped into a generalized weighted graph, where each edge is associated with a real/complex weight set. We first show that the problem is NP-hard even in the case when the underlying graph is a tree and each weight set has only two elements. We then introduce the notion of “sign definite real/complex set”, based on which we prove that the existence of a low-rank solution can be related to the topology of the graph characterizing the optimization as well as the sign definiteness of its weight sets. As a by-product of this result, several classes of optimizations are shown to be polynomial-time solvable. To demonstrate the application of this result in power systems, we illustrate that optimization over a power circuit can be mapped into a generalized weighted graph, where each weight set is naturally sign definite due to the physics of power systems. This result improves upon our previous result on zero duality gap for the optimal power flow problem, and can be readily applied to abstract optimization problems (e.g. max cut) as well as optimization over other physical systems.

As another problem related to the topic of this talk, we finally discuss “generalized network flow (GNF)”. This is a well-studied problem in the special case where the loss of the network is a linear function. Under the reasonable assumption that the loss of each line is an increasing and convex function, we show that GNF is polynomial-time solvable.


Javad Lavaei is an Assistant Professor in the Department of Electrical Engineering at Columbia University. He obtained his Ph.D. degree in Control & Dynamical Systems from California Institute of Technology and held a one-year postdoc position jointly with Electrical Engineering and Precourt Institute for Energy at Stanford University. He is the recipient of the Milton and Francis Clauser Doctoral Prize for the best university-wide Ph.D. thesis. His research interests include power systems, networking, distributed computation, optimization, and control theory. Javad Lavaei is a senior member of IEEE and has won several awards, including the Canadian Governor General’s Gold Medal, Northeastern Association of Graduate Schools Master’s Thesis Award, New Face of Engineering in 2011, and Silver Medal in the 1999 International Mathematical Olympiad.