GRASP Conic relaxations: scalable and accurate global optimization beyond polynomials

掌握圆锥松弛：超越多项式的可扩展且准确的全局优化

基本信息

批准号：
EP/X032051/1
负责人：
Hamza Fawzi
金额：
$ 164.4万
依托单位：
University of Cambridge
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2023
资助国家：
英国
起止时间：
2023 至无数据
项目状态：
未结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FX032051%2F1
关键词：
GRASP Conic relaxations scalable accurate

项目摘要

Most optimization problems that occur in science and engineering are nonconvex and computationally hard. Yet, for many important applications such as the design of safety-critical systems, it is essential that one finds global guarantees about the solution. One of the most powerful techniques for global optimization of nonconvex problems is the so-called ''sum-of-squares method'' which had a tremendous impact in various scientific disciplines such as control theory, theoretical physics, discrete geometry, and computer science. Despite its elegant theoretical properties, the sum-of-squares method suffers from a number of shortcomings that limits its practical applicability: (a) it assumes that the problem is described using polynomials, which in many practical cases is an assumption that is not satisfied; (b) the convex relaxation it produces has a size that is much larger than the original nonconvex optimization problem; and (c) it relies at its core on semidefinite programming, a certain type of convex optimization problem, which though tractable in principle, are challenging to solve in practice for large problems, especially when high accuracy is required. The goal of GRASP is to break new ground and propose new principled and practical convex relaxations for a wide class of nonconvex nonpolynomial optimization problems where formal certificates are required. This ambitious project will be achieved by combining new theoretical insights together with the development of optimization algorithms that are accurate and scalable. The new findings of this project will be applied to high-impact problems in quantum information sciences, as well as in the area of intelligent and autonomous systems to provide new efficient ways to guarantee their robustness.

科学和工程中发生的大多数优化问题都是非凸的并且计算困难。然而，对于许多重要的应用（例如安全关键系统的设计）来说，找到解决方案的全球保证至关重要。非凸问题全局优化最强大的技术之一是所谓的“平方和方法”，它对控制理论、理论物理、离散几何和计算机科学等各个科学学科产生了巨大影响。尽管平方和方法具有优美的理论特性，但它也存在一些限制其实际适用性的缺点：(a)它假设问题是用多项式描述的，而在许多实际情况下，这是一个不满足的假设; (b) 它产生的凸松弛的大小比原始非凸优化问题大得多； (c)它的核心依赖于半定规划，这是一种凸优化问题，虽然原则上易于处理，但在实践中解决大型问题具有挑战性，特别是在需要高精度时。 GRASP 的目标是为需要正式证书的各种非凸非多项式优化问题开辟新天地并提出新的原则性和实用的凸松弛。这个雄心勃勃的项目将通过将新的理论见解与准确且可扩展的优化算法的开发相结合来实现。该项目的新发现将应用于量子信息科学以及智能和自主系统领域的高影响力问题，以提供新的有效方法来保证其鲁棒性。