Graph-Theoretic Algorithm for Solving Polynomial Optimization with Applications to Energy Systems and Distributed Control Systems
Abstract
Abstract: 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 (non-convex) optimization problems has been an active area of research for many decades. The goal is to design a robust, scalable method for finding a global or near global solution in polynomial time. This still remains as an open problem for the general class of polynomial optimization including combinatorial optimization, and has a direct impact on several navy-related problems regarding au- tonomous systems, operational sustainment, dynamical systems modeling and logistics. This project aims to develop a general-purpose global computational method, which can be deployed for a wide range of applications including the above navy problems and: i) distributed (cooperative) control of communication networks, navy systems, traffic systems, aerospace systems and wireless sensor networks, for accomplishing a wide range of missions such as search & rescue operations, surveillance, reconnaissance, targeting and hazardous material handling; ii) optimal design and operation of energy systems, e.g., micro-grids. In this project, a general polynomial optimization problemis studied through a convex relaxation, namely a semidefinite program (SDP). The existence of a rank-1 matrix solu- tion for the SDP relaxation guarantees the recovery of a global solution of the original problem. This proposal is based on the observation that an arbitrary polynomial opti- mization can be equivalently converted to a sparse quadratically-constrained quadratic program (QCQP) whose SDP relaxation possesses a matrix solution with rank at most 3, implying that the challenge is only to reduce the rank from 3 to 1. Intellectual Merit: The proposed technical approach consists of four steps. First, the polynomial optimization is converted to an equivalent QCQP problem. Second, the ob- tained QCQP is sparsified by means of the graph-theoretic notions of treewidth and OS to guarantee that its SDP relaxation will have a low-rank matrix solution. Third, the ob- jective function of the sparse SDP relaxation is penalized to further reduce the rank of its solution. Last, an approximate rank-1 SDP solution is contrived, leading to a global or near-global (approximate) solution of the original problem. This project also aims to develop a theory explaining how much and what type of approximation are needed to make a polynomial optimization problem tractable. The tools and techniques developed in this project will be implemented in a solver and then applied to several case studies on distributed control systems, energy systems and some specific navy problems. Broader Impacts: This project will have a significant impact on mathematics and en- gineering by developing a rich mathematical foundation for nonlinear optimization. The outcomes of this interdisciplinary project can be exploited for a variety of real-world prob- lems such as cooperative control of multi-vehicle systems, coordination of autonomous vehicles, formation flying of unmanned aerial vehicles, distributed control and optimiza- tion for electrical power networks, optimal design of microgrids, resource allocation for communication networks, logistics, and nonlinear system identification for the oceans and atmosphere. To perform large-scale demonstrations, the PI will leverage his collabo- rations with Google, IBM, EPRI, ABB and Los Alamos National Laboratory.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512835
Entities
People
- Javad Lavaei
Organizations
- Office of Naval Research
- United States Navy
- University of California Regents