New Applications of Semidefinite Programming

12/02/2015
Intervenant(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 Postdoc research.
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.