Geometria Complessa e Geometria Differenziale
Geometria Complessa e Geometria Differenziale
home | mail | papers | authors | news | seminars | events | open positions | login

Computer algebra algorithms for semidefinite programming

Simone Naldi (Université de Limoges)

created by daniele on 15 Jan 2016

26 jan 2016 -- 11:30

Aula Tricerri, DiMaI, Firenze


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.

Credits | Cookie policy | HTML 5 | CSS 2.1