CAREER: Linear Matrix Inequality Representations in Optimization

University Of California-San Diego, La Jolla CA

Investigators

Abstract

This proposal investigates the linear matrix inequality representations of convex sets and their applications in optimization problems. The work involves different kinds of mathematical tools like algebraic geometry, convex analysis, differential geometry, numerical analysis, optimization theory, and real algebra. The investigator not only studies the fundamental mathematics on the scope and depth of linear matrix inequality representability, but also work on designing new algorithms and software solving hard optimization problems. The following five main topics will be focused in this project: linear matrix inequality representations of rigid convex sets, semidefinite programming representations of convex semialgebraic sets, second order cone programming representations of convex semialgebraic sets, semidefinite programming representations of nonnegative multivariate polynomials, and linear matrix inequality methods for solving nonconvex optimization problems and polynomial systems. A basic problem of science and engineering is finding a global minimum of a function of many variables. As a metaphor one might think of a complicated terrain of mountains and valleys which stretches for hundreds of miles and one must find the lowest point in the lowest valley. The difficulty is that one can not see the map and one only knows a mathematical formula for the terrain and in most applications (like electronics, networks, biochemistry) there are many variables instead of three. Many algorithms will find the lowest point of a particular valley but none are known which effectively find the lowest valley itself. This NSF research is to develop global optimization algorithms for various situations. One is the class of problems where the data is given by polynomials. Another is to determine and parameterize convex problems very efficiently; in convex situations one has only one valley. These pursuits require integration of techniques from numerical mathematics, real and complex algebraic geometry, convex analysis, differential geometry, numerical analysis, and optimization theory, a wide range of mathematics. Jiawang Nie has personal experience with several areas of applications including sensor networks and systems control and this informs his mathematics and techniques. Other important features of this proposal are integrating research and education, developing new mathematical courses, training undergraduate and graduate students on using the latest mathematical tools, advising postdoctoral scholars on how to create novel research results.