TITLE:  “Graph-theoretic Convexification of Polynomial Optimization Problems: Theory, Numerical Algorithm, and Case Studies”

ABSTRACT:

The area of polynomial optimization has been actively studied for years, where the goal is to find a high-quality solution using an efficient computational method. Some of the important research problems in this area are: i) how does the underlying structure of an optimization problem affect its complexity? Ii) how does sparsity help? iii) how to find a near globally optimal solution whenever it is hard to find a global minimum? iv) how to design an efficient numerical algorithm for large-scale non-convex optimization problems? v) how to deal with problems with a mix of continuous and discrete variables? In this talk, we will develop a new mathematical framework to study the above problems. Our framework rests on recent advances in graph theory and optimization, including the notions of OS-vertex sequence and treewidth, matrix completion, semidefinite programming (SDP), and low-rank optimization.

As an application, we will study four fundamental mixed-integer power optimization problems, named power flow, security-constrained optimal power flow, state estimation and unit commitment. Power optimization problems are at the heart of the multi-billion electricity market and 1-5% improvements in their solutions lead to saving billions of dollars annually. The design of better optimization techniques for power systems has been an active area of research since 1962. In this talk, we will show that real-world power networks have low treewidth, and as a result their SDP relaxation always has a low-rank solution. By leveraging this property, we will design a penalized SDP relaxation to find a near-global solution. We will illustrate our results on real-world power grids with over 13,000 nodes described by nonlinear equations subject to noise and corrupted data.

Bio

Javad Lavaei is an Assistant Professor in the Department of Industrial Engineering and Operations Research at University of California, Berkeley. He was an Assistant Professor at Columbia University from 2012 to 2015. He received the Ph.D. degree in Control and Dynamical Systems from the California Institute of Technology in 2011, and was a postdoctoral scholar in Precourt Institute for Energy and Electrical Engineering at Stanford University in 2011-2012. He is the recipient of the Milton and Francis Clauser Doctoral Prize for the best university-wide Ph.D. thesis, entitled "Large-Scale Complex Systems: From Antenna Circuits to Power Grids".  He researches on optimization theory, control theory and power systems. He has won several awards, including DARPA Young Faculty Award, Office of Naval Research Young Investigator Award, Office of Naval Research's Director of Research Early Career Award, Air Force Office of Scientific Research Young Investigator Award, National Science Foundation CAREER Award, Resonate Award, Google Faculty Research Award, Governor General of Canada Academic Gold Medal, Northeastern Association of Graduate Schools Master's Thesis Award, and Silver Medal in the 1999 International Mathematical Olympiad. Javad Lavaei is an associate editor of the IEEE Transactions on Smart Grid as well as the guest editor-in-chief of the IEEE Transactions on Smart Grid for a special issue on distributed computation, and serves on the conference editorial board of both IEEE Control Systems Society and European Control Association. He was a finalist (as an advisor) for the Best Student Paper Award at the 53rd IEEE Conference on Decision and Control 2014. His journal paper entitled "Zero Duality Gap in Optimal Power Flow Problem" has received a prize paper award given by the IEEE PES Power System Analysis Computing and Economics Committee in 2015. Javad Lavaei is a recipient of the 2015 INFORMS Optimization Society Prize for Young Researchers, the 2016 Donald P. Eckman Award given by the American Automatic Control Council, and the 2016 INFORMS ENRE Energy Best Publication Award.