Polynomial optimization is a high-impact area for engineering and computational mathematics, which holds the key to some fundamental problems of discrete optimization, power engineering, theoretical computer science, and of particular interest to this proposal, dynamics and control. One of the most powerful approaches for handling polynomial optimization problems with rigorous and global guarantees is via algebraic techniques. These techniques form an exciting area of optimization that combines classical concepts of algebraic geometry with modern tools of numerical optimization. Despite their enormous potential, the applicability of algebraic techniques has always been limited by a fundamental challenge, which is scalability. In the first half of this proposal, the PI puts forward a new set of research directions that if successful can lead to major advancements in our ability to solve large-scale polynomial optimization problems. In the second half of the proposal, the PI brings ideas from dynamics and control into polynomial optimization. He investigates the potential of dynamical systems for solving polynomial optimization problems and introduces a new class of optimization problems where explicit polynomial constraints are coupled with dynamical systems constraints such as stability, safety, and collision avoidance. Efficient algorithms for these problems can have a sensible societal impact by broadening the class of applications in engineering and operations research that we can solve to global or near global optimality. These include design of complex robotic systems, verification of safety-critical software embedded in airplanes or medical devices, optimization of the power grid, control of systemic risk in our financial networks, and a more effective preparation against the spread of epidemic diseases. In addition to the research component, the PI's proposal has a strong educational component, which similarly encourages synergistic activities between optimization and control. Examples include the initiation of a Princeton Day of Optimization and Control, and a revamping of the early undergraduate curriculum in optimization to highlight the modern connections of the field with control and computer science.
A slightly more technical description of the project is as follows. The majority of algebraic techniques in polynomial optimization use the so-called sum of squares relaxation, which relies on expensive-to-solve semidefinite programs. By contrast, the new algorithms that the PI proposes dispense with semidefinite programming altogether. They instead work with linear programs and second order cone programs, which are intrinsically more scalable types of convex optimization problems. These algorithms inner approximate the sum of squares cone in a hierarchical format and with increasing accuracy. The PI proposes a number of applications of his optimization algorithms in dynamics and control, such as an automated construction of Lyapunov functions for verification of large-scale nonlinear and hybrid control systems. Conversely, the PI will investigate the potential of dynamical systems and Lyapunov theory for providing better local search and lower bounding techniques for polynomial optimization problems. Finally, the PI proposes an algorithmic study of a class of optimization problems whose constraints come from requirements on the trajectories of a dynamical system that initiate from a basic semialgebraic set. These requirements could include convergence to desired equilibrium points, boundedness, collision avoidance, invariance, reachability, etc. These novel optimization problems have an array of applications in uncertain and dynamic environments and their study leads to new interactions between dynamical systems, conic optimization, computational complexity theory, and convex geometry.
