The Algebraic Degree of Semidefinite Programming

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Given a generic 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.
23 pages, 3 figures

Keywords

Optimization and Control, Algebraic Geometry

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/168526

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0611562
 http://arxiv.org/abs/math/0611562

Collections

arXiv