New Applications of Semidefinite Programming
Palestrante(s) : Victor Magron (Imperial College) Semidefinite programming (SDP) is relevant to a wide range of
mathematical fields, including combinatorial optimization, control
theory, matrix completion. In 2001, Lasserre introduced a hierarchy of
SDP relaxations for approximating polynomial infima.
My talk emphasizes new applications of this SDP hierarchy in either
computer science or mathematics, investigated during my PhD and
In real algebraic geometry, I describe how to use SDP hierarchies to
approximate as closely as desired exact projections of semialgebraic
sets. In nonlinear optimization, SDP hierarchies allow to compute
Pareto curves (associated with multicriteria problems) as well as
solutions of transcendental problems.
These hierarchies can also be easily interleaved with computer
assisted proofs. An appealing motivation is to solve efficiently
thousands of nonlinear inequalities occurring in the formal proof of
Kepler Conjecture by Hales. Finally, SDP can provide precise
information to automatically tune reconfigurable hardware (e.g. FPGA)
to algorithm specifications.
marc (at) nullmezzarobba.net