CAREER: Polynomial Optimization and Dynamical Systems

多项式优化是工程和计算数学中一个影响很大的领域，它是离散优化、动力工程、理论计算机科学等一些基本问题的关键，尤其对本提案、动力学和控制感兴趣。处理具有严格和全局保证的多项式优化问题的最强大方法之一是通过代数技术。这些技术形成了一个令人兴奋的优化领域，它将代数几何的经典概念与现代数值优化工具相结合。尽管具有巨大的潜力，但代数技术的适用性一直受到一个基本挑战的限制，即可扩展性。在本提案的前半部分，PI提出了一套新的研究方向，如果成功，可以导致我们解决大规模多项式优化问题的能力取得重大进展。在提案的后半部分，PI将动力学和控制的思想带入多项式优化。他研究了动力系统解决多项式优化问题的潜力，并引入了一类新的优化问题，其中显式多项式约束与动力系统约束（如稳定性、安全性和避碰性）相结合。这些问题的有效算法可以通过扩大工程和运筹学中的应用类别来产生明显的社会影响，我们可以解决全局或接近全局最优。这包括设计复杂的机器人系统，验证嵌入飞机或医疗设备中的安全关键软件，优化电网，控制金融网络中的系统性风险，以及更有效地防范流行病的传播。除了研究部分，PI的建议有一个强大的教育部分，同样鼓励优化和控制之间的协同活动。例如，普林斯顿大学启动了“优化与控制日”，并对早期本科优化课程进行了改革，以突出该领域与控制和计算机科学的现代联系。对该项目的稍微技术性的描述如下。多项式优化中的大多数代数技术使用所谓的平方和松弛，它依赖于昂贵的求解半定规划。相比之下，PI提出的新算法完全不需要半确定规划。取而代之的是线性规划和二阶锥规划，它们本质上是可扩展的凸优化问题。这些算法以分层的形式逼近平方和，精度越来越高。PI提出了他的优化算法在动力学和控制中的许多应用，例如用于验证大型非线性和混合控制系统的Lyapunov函数的自动构造。相反，PI将研究动力系统和李亚普诺夫理论的潜力，为多项式优化问题提供更好的局部搜索和下限技术。最后，PI提出了一类优化问题的算法研究，这些优化问题的约束来自于对一个动力系统的轨迹的要求，该系统起源于一个基本的半代数集。这些要求可能包括收敛到期望的平衡点、有界性、避免碰撞、不变性、可达性等。这些新的优化问题在不确定和动态环境中有一系列应用，它们的研究导致了动力系统、二次优化、计算复杂性理论和凸几何之间的新相互作用。

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.