Convex Relaxation for Polynomial Optimization: Application to Power Systems and Decentralized Control
Nov 07, 2013
from 02:00 PM to 03:30 PM
|Where||Engr. IV Bldg., Tesla Room 53-125|
|Contact Name||Prof. Lieven Vandenberghe|
|Add event to calendar||
In this talk, we study polynomial optimization problems via a semidefinite programming (SDP) relaxation. This convex relaxation is exact whenever it has a rank-1 matrix solution. The first part of this talk focuses on analyzing the rank of the SDP solution for two real-world problems: (i) optimization over power networks, and (ii) optimal decentralized control. The second part of the talk proposes a general theory for arbitrary polynomial optimization problems.
Optimization over power network: The real-time operation of a power network depends heavily on several large-scale non-convex optimization problems solved from every few minutes to every year. We show that the SDP relaxation of most of these problems has a rank-1 solution due to the physics of transmission lines and transformers. In particular, we find global solutions for many instances of the 50-year-old infamous optimal power flow problem. We also propose a penalized SDP relaxation to obtain a rank-1 solution for unsuccessful cases. Based on these results, we show that power optimization problems can be solved in polynomial time for distribution networks and for transmission networks with a sufficient number of transformers.
Optimal decentralized control: The area of decentralized control is created to address the challenges arising in the control of real-world systems with many interconnected subsystems. The objective is to design a structurally constrained controller with the aim of reducing the computation or communication complexity of the overall controller. We show that the SDP relaxation of this NP-hard control problem has a solution with rank at most 3. This is due to the fact that the nonlinearity of the optimal decentralized control problem appears in a very sparse way.
SDP for general polynomial optimization: Using an algebraic graph-theoretic technique, we show that an arbitrary polynomial optimization has a SDP relaxation with a matrix solution of rank 1, 2 or 3. In particular, we prove that the NP-hardness of polynomial optimization is due to the complexity of checking the existence of a rank-1 matrix in some convex set, while we can verify the existence of a rank-3 matrix in polynomial time.
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 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 Google Faculty Research Award, 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.