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的目的是打破新的地面，并为需要正式证书的一系列非convex的非consevex非多物质优化问题提出新的原则和实用凸放松。这个雄心勃勃的项目将通过将新的理论见解与精确且可扩展的优化算法的发展结合在一起来实现。该项目的新发现将应用于量子信息科学中的高影响力问题，以及智能和自主系统领域，以提供新的有效方法来保证其稳健性。