Engineers designing a self-driving car's braking system or a quantum computer's error correction need to know, with absolute certainty, that their solution is the best possible—not just a good guess. The standard method for proving this, the sum-of-squares technique, is powerful but brittle: it only works on problems described by simple polynomials, and it often creates a new problem so large and computationally heavy that it becomes impractical to solve. This project aims to build a new, more flexible mathematical toolkit that can provide those same ironclad guarantees for a much wider range of real-world problems, including those involving exponentials or trigonometric functions. If successful, the work could allow engineers to formally certify the robustness of autonomous systems—ensuring a drone can recover from a sensor failure—or verify the security of quantum communication protocols. The research is fundamentally about expanding the reach of a core mathematical technique, with the potential to make safety-critical systems across computing and engineering provably reliable rather than just probably safe.
View original technical description
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.
Plain English summaries and category classifications on this site are generated by AI and may not perfectly reflect the original research.
Is something wrong? Let us know