Real Algebraic Geometry and Combinatorial Optimization Seminar
Speaker: Luca Wellmeier, UiT - The Arctic University of Norway
Host: Sudhir R. Ghorpade
Title: Hierarchies in Polynomial Optimization
Time, day and date: 5:15:00 PM - 6:15:00 PM, Wednesday, January 28
Venue: Ramanujan Hall
Abstract: Polynomial optimization provides a unifying framework for problems arising in combinatorics, quantum information, power systems, and robotics, among many more - thereof also many well-known NP-hard problems. This motivates the study of systematic relaxations rather than exact solution methods. The goal of this talk is to give a brief introduction to the Moment-SOS hierarchy, a sequence of semidefinite relaxations rooted in real algebraic geometry. From one viewpoint, polynomial nonnegativity is approximated by membership in the sum-of-squares cone, connecting the theory to classical work on Hilbert's 14th problem and Positivstellensätze. From the dual viewpoint, the same hierarchy arises from truncated moment problems and the reconstruction of measures. This duality yields a theoretically rich class of tractable algorithms for computing tight bounds on polynomial optimization problems, which have been proven useful in many domains.