Skip to main content.
Advanced search >
<< Back to previous page Print

<< Monday, January 28, 2013 >>

Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare

Optimization over graph with application to power systems

Seminar: Departmental | January 28 | 3-4 p.m. | 521 Cory Hall

Javad Lavaei, Columbia University


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 a 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.