权益分类	功能权益	普通用户	{{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）它的核心依赖于半定规划，半定规划是某种类型的凸优化问题，尽管其在原理上易于处理，但在实践中对于大型问题的解决是具有挑战性的，特别是当需要高精度时。GRASP的目标是开辟新天地，提出新的原则和实用的凸松弛广泛的一类非凸非多项式优化问题，需要正式的证书。这个雄心勃勃的项目将通过将新的理论见解与精确和可扩展的优化算法的开发相结合来实现。该项目的新发现将应用于量子信息科学以及智能和自主系统领域的高影响力问题，以提供新的有效方法来保证其鲁棒性。