# 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.

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

Keywords: