权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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)它的核心依赖于半定规划，这类凸优化问题虽然在原则上是容易处理的，但在实践中对于大型问题的解决是具有挑战性的，特别是在要求高精度的情况下。GRAPH的目标是对一大类需要形式证书的非凸非多项式优化问题提出新的原则性和实用性的凸松弛方法。这个雄心勃勃的项目将通过将新的理论见解与开发准确和可扩展的优化算法相结合来实现。该项目的新发现将应用于量子信息科学中的高影响力问题，以及智能和自主系统领域，以提供新的有效方法来确保其健壮性。