26 jan 2016 -- 11:30
Aula Tricerri, DiMaI, Firenze
Abstract.
Semidefinite programming (SDP) is the natural extension of linear programming to the convex cone of symmetric positive semidefinite matrices. It consists in minimizing a linear function over the convex set, called spectrahedron, defined by a linear matrix inequality (i.e. over the set of real vectors $x$ such that a symmetric linear matrix $A(x)$ is positive semidefinite, $A(x)>=0$). SDP finds numerous applications especially in combinatorial and polynomial optimization, systems control theory, real algebra. While one can solve "numerically" a SDP problem with interior-point algorithms in polynomial time at a given accuracy, neither efficient exact algorithms for SDP are available, nor a complete understanding of its theoretical complexity has been achieved. In this talk I would like to present some new results in this direction, based on joint work with D. Henrion and M. Safey El Din.