GRASP Conic relaxations: scalable and accurate global optimization beyond polynomials
Lead Research Organisation:
University of Cambridge
Department Name: Applied Maths and Theoretical Physics
Abstract
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.
Organisations
People |
ORCID iD |
Hamza Fawzi (Principal Investigator) |
Publications
Faust O
(2024)
Sum-of-Squares Proofs of Logarithmic Sobolev Inequalities on Finite Markov Chains
in IEEE Transactions on Information Theory
Fawzi H
(2024)
Entropy constraints for ground energy optimization
in Journal of Mathematical Physics