Bad projections of the PSD cone
Tóm tắt
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.
Tài liệu tham khảo
Blekherman, G., Parrilo, P., Thomas, R.: Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Series on Optimization 13. SIAM, Philadelphia (2012)
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, 134–183 (1975)
Fawzi, H., Safey El Din, M.: A lower bound on the positive semidefinite rank of convex bodies. SIAM Journal on Applied Algebra and Geometry 2, 126–139 (2018)
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 (2021)
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, Proceedings in Mathematics and Statistics 50. Springer, New York (2013)
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, 603–638 (2010)