The algebraic degree of semidefinite programming
Tóm tắt
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.
Tài liệu tham khảo
Alizadeh F., Haeberly J., Overton M.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77, 111–128 (1997)
Bajaj C.: The algebraic degree of geometric optimization problems. Discret. Comput. Geom. 3, 177–191 (1988)
Catanese F., Hoşten S., Khetan A., Sturmfels B.: The maximum likelihood degree. Am. J. Math. 128, 671–697 (2006)
Datta R.: Universality of Nash equilibria. Math. Oper. Res. 28, 424–432 (2003)
De Loera, J., Rambau, J., Santos, F.: Triangulations: applications, structures, and algorithms. Algorithms and Computation in Mathematics. Springer, Heidelberg (to appear)
Fulton, W., Pragacz, P.: Schubert varieties and degeneracy loci. Lecture Notes in Mathematics, vol. 1689. Springer, New York (1998)
Gelfand I., Kapranov M., Zelevinsky A.: Discriminants, Resultants and Multidimensional Determinants. Birkhäuser, Boston (1994)
Grayson, D., Stillman, M.: Macaulay 2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/
Harris, J.: Algebraic geometry: a first course. Graduate Texts in Mathematics, vol. 113. Springer, New York (1992)
Harris J., Tu L.: On symmetric and skew-symmetric determinantal varieties. Topology 23, 71–84 (1984)
Helton W., Vinnikov V.: Linear matrix inequality representation of sets. Comm. Pure Appl. Math. 60, 654–674 (2007)
Hoşten S., Khetan A., Sturmfels B.: Solving the likelihood equations. Found. Comput. Math. 5, 389–407 (2005)
Kempf G.: Images of homogeneous vector bundles and varieties of complexes. Bull. Am. Math. Soc. 81, 900–901 (1975)
Lewis A., Parrilo P., Ramana M.: The Lax conjecture is true. Proc. Am. Math. Soc. 133, 2495–2499 (2005)
Macdonald I.G.: Symmetric Functions and Hall Polynomials, 2nd edn. Clarendon Press, Oxford (1995)
Miller E., Sturmfels B.: Combinatorial Commutative Algebra. Springer Graduate Texts, New York (2005)
Pataki, G.: The geometry of cone-LP’s, in [25]
Pragacz P.: Enumerative geometry of degeneracy loci. Ann. Scient. Ec. Norm. Sup. 21(4), 413–454 (1988)
Speyer D.: Horn’s problem, Vinnikov curves, and the hive cone. Duke Math. J. 127, 395–427 (2005)
Sturm J.F.: SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11, 12, 625–653 (1999)
Tevelev E.: Projective duality and homogeneous spaces. Encyclopaedia of Mathematical Sciences. Springer, Berlin (2005)
Vandenberghe L., Boyd S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996)
Vinnikov V.: Self-adjoint determinantal representation of real plane curves. Math. Ann. 296, 453–479 (1993)
von Bothmer, H.C., Ranestad, K.: A general formula for the algebraic degree in semidefinite programming. http://arxiv.org/abs/math/0701877
Wolkowicz H., Saigal R., Vandenberghe L.: Handbook of Semidefinite Programming. Kluwer, Dordrecht (2000)