Campuses:

The Algebraic Degree of Semidefinite Programming

Thursday, January 18, 2007 - 9:30am - 10:30am
EE/CS 3-180
Bernd Sturmfels (University of California, Berkeley)
Given a semidefinite program, specified by matrices
with rational entries, each coordinate of its optimal solution
is
an algebraic number. We study the degree of the minimal
polynomials
of these algebraic numbers. Geometrically, this degree counts
the
critical points attained by a linear functional on a fixed rank
locus in a linear space of symmetric matrices. We determine
this degree
using methods from complex algebraic geometry, such as
projective duality,
determinantal varieties, and their Chern classes. This is a
joint paper with
Jiawang Nie and Kristian Ranestad, posted at
href=http://www.arxiv.org/abs/math.OC/0611562>rxiv.org/abs/math.OC/0611562.
MSC Code: 
90C22