CAREER: Polynomial Optimization and Dynamical Systems

职业：多项式优化和动力系统

• 批准号: 1554230
• 负责人: Amir Ali Ahmadi
• 金额: $ 50万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-02-01 至 2022-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1554230&HistoricalAwards=false
• 关键词: CAREER; Polynomial; Optimization; Dynamical; Systems

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.

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