Bad projections of the PSD cone

• Jiang, Yuhan ^[1] ; Sturmfels, Bernd ^[2]
  1. [1] Harvard University

     Harvard University

     City of Cambridge, Estados Unidos

     
  2. [2] Max Planck Institute for Mathematics in the Sciences

     Max Planck Institute for Mathematics in the Sciences

     Kreisfreie Stadt Leipzig, Alemania

     
• Localización: Collectanea mathematica, ISSN 0010-0757, Vol. 72, Fasc. 2, 2021, págs. 261-280
• Idioma: inglés
• DOI: 10.1007/s13348-021-00319-4
• Enlaces
  • Texto completo
• Resumen

  • The image of the cone of positive semidefinite matrices under a linear map is a convex cone. Pataki characterized the set of linear maps for which that image is not closed. The Zariski closure of this set is a hypersurface in the Grassmannian. Its components are the coisotropic hypersurfaces of symmetric determinantal varieties. We develop the convex algebraic geometry of such bad projections, with focus on explicit computations.

• Referencias bibliográficas
  • Blekherman, G., Parrilo, P., Thomas, R.: Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Series on Optimization 13. SIAM,...
  • Cifuentes, D., Harris, C., Sturmfels, B.: The geometry of SDP-exactness in quadratic optimization. Math. Program. Ser. A 182, 399–428 (2020)
  • Cifuentes, D., Kahle, T., Parrilo, P.: Sums of squares in Macaulay2. J. Softw. Algebra Geometry 10, 17–24 (2020)
  • Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decompostion. Springer Lecture Notes Comput. Sci. 33,...
  • Fawzi, H., Safey El Din, M.: A lower bound on the positive semidefinite rank of convex bodies. SIAM Journal on Applied Algebra and Geometry...
  • Fløystad, G., Kileel, J., Ottaviani, G.: The Chow form of the essential variety in computer vision. J. Symbolic Comput. 86, 97–119 (2018)
  • Gel’fand, I.M., Kapranov, M.M., Zelevinsky, A.V.: Discriminants. Resultants and Multidimensional Determinants, Birkhäuser, Boston (1994)
  • Grayson, D., Stillman, M.: Macaulay2, a software system for research in algebraic geometry, available at http://www.math.uiuc.edu/Macaulay2/
  • Harris, C., Michałek, M., Sertöz, E.: Computing images of polynomial maps. Adv. Comput. Math. 45, 2845–2865 (2019)
  • Klep, I., Schweighofer, M.: An exact duality theory for semidefinite programming based on sums of squares. Math. Oper. Res. 38, 569–590 (2013)
  • Kohn, K.: Coisotropic hypersurfaces in Grassmannians. J. Symbolic Comput. 103, 157–177 (2021)
  • Liu, M., Pataki, G.: Exact duality in semidefinite programming based on elementary reformulations. SIAM J. Opt. 25, 1441–1454 (2015)
  • Michałek, M., Sturmfels, B.: Invitation to Nonlinear Algebra, Graduate Studies in Mathematics, vol. 211. American Mathematical Society, Providence...
  • Nie, J., Ranestad, K., Sturmfels, B.: The algebraic degree of semidefinite programming. Math. Program. 122, 379–405 (2010)
  • Pataki, G.: Strong duality in conic linear programming: Facial reduction and extended duals, Computational and Analytical Mathematics, 613–634,...
  • Pataki, G.: Bad semidefinite programs: they all look the same. SIAM J. Opt. 27, 146–172 (2017)
  • Pataki, G.: Characterizing semidefinite programs: normal forms and short proofs. SIAM Rev. 61, 839–859 (2019)
  • Plaumann, D., Sturmfels, B., Vinzant, C.: Quartic curves and their bitangents. J. Symbolic Comput. 46, 712–733 (2011)
  • Rockafellar, R.T.: Convex Analysis, Princeton Mathematical Series 28. Princeton University Press, Princeton (1970)
  • Sinn, R., Sturmfels, B.: Generic spectrahedral shadows. SIAM J. Opt. 25, 1209–1220 (2015)
  • Sturmfels, B.: The Hurwitz form of a projective variety. J. Symbolic Comput. 79, 186–196 (2017)
  • Sturmfels, B., Uhler, C.: Multivariate Gaussians, semidefinite matrix completion, and convex algebraic geometry. Ann. Inst. Stat. Math. 62,...