Graph-Theoretic Algorithm for Arbitrary Polynomial Optimization Problems with Applications to Distributed Control, Power Systems, and Matrix Completion

ECE Seminar: Graph-Theoretic Algorithm for Arbitrary Polynomial Optimization Problems with Applications to Distributed Control, Power Systems, and Matrix Completion

Starts at: November 20, 2014 4:30 PM

Location: Scaife Hall - Room 125

Speaker: Javad Lavaei

Affiliation: Columbia University

Refreshments provided: Yes



Optimization theory plays a crucial role in the design, analysis, control, and operation of real-world systems. The development of efficient optimization techniques and numerical algorithms for nonlinear optimization problems has been an active area of research for many years. The goal is to design an efficient, robust and scalable method for finding a global or near-global solution. This still remains as an open problem for the general class of polynomial optimization, including combinatorial optimization. In this talk, we study a general polynomial optimization using a semidefinite programming (SDP) relaxation. The existence of a rank-1 matrix solution to the SDP relaxation enables the recovery of a global solution of the original problem. We propose a graph-theoretic technique to sparsify the optimization problem of interest such that its SDP relaxation will have a guaranteed low-rank solution. As a by-product, we show that every arbitrary polynomial optimization admits a sparse quadratic representation whose SDP relaxation has a matrix solution with rank at most 3. This result provides a basis for finding a near-global solution by approximating the rank-3 SDP solution with a rank-1 matrix. In this talk, we apply our technique to three long-standing problems: optimal distributed control, power optimization problem, and low-rank matrix completion. We also offer more than 100K simulations for control and optimization over real-world power systems (such as Polish and New England systems). We verify that our algorithm usually finds solutions with global optimality degrees close to 99.9%. Since general-purpose SDP solvers can hardly accommodate sparse SDP problems with millions of parameters, we also propose a distributed algorithm whose iterations consist of only simple multiplication and eigenvalue decomposition over small-sized matrices.


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 in 2011 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, control theory, distributed computation, and nonlinear optimization. Javad Lavaei is a senior member of IEEE and has won several awards, including NSF CAREER Award, Office of Naval Research YIP, 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. For his computation work on energy systems, he was chosen by Resnick Institute and Fortune Magazine as one of 5 innovators in the area of sustainability worldwide in 2014.