Equivariant Semidefinite Lifts of Regular Polygons

References

• Ben-Tal A, Nemirovski A (2001) On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2):193–205.Link, Google Scholar
• Blekherman G, Parrilo PA, Thomas RR (2013) Semidefinite Optimization and Convex Algebraic Geometry (SIAM, Philadelphia).Google Scholar
• Briët J, Dadush D, Pokutta S (2013) On the existence of 0/1 polytopes with high semidefinite extension complexity. Bodlaender HL, Italiano GF, eds. Algorithms—ESA 2013, Lecture Notes in Computer Science, Vol. 8125 (Springer, New York), 217–228.Crossref, Google Scholar
• Chan SO, Lee JR, Raghavendra P, Steurer D (2013) Approximate constraint satisfaction requires large LP relaxations. IEEE 54th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 350–359.Crossref, Google Scholar
• Fawzi H, Saunderson J, Parrilo PA (2015) Equivariant semidefinite lifts and sum-of-squares hierarchies. SIAM J. Optim. 25(4): 2212–2243.Crossref, Google Scholar
• Fawzi H, Saunderson J, Parrilo PA (2016) Sparse sums of squares on finite abelian groups and improved semidefinite lifts. Math. Programming 160(1):149–191.Crossref, Google Scholar
• Fawzi H, Gouveia J, Parrilo PA, Robinson RZ, Thomas RR (2015) Positive semidefinite rank. Math. Programming 153(1):133–177.Crossref, Google Scholar
• Fiorini S, Rothvoß T, Tiwary HR (2012) Extended formulations for polygons. Discrete Comput. Geometry 48(3):658–668.Crossref, Google Scholar
• Fiorini S, Massar S, Pokutta S, Tiwary HR, de Wolf R (2012) Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds. Proc. 44th Sympos. Theory Comput. (ACM, New York), 95–106.Crossref, Google Scholar
• Goemans M (2015) Smallest compact formulation for the permutahedron. Math. Programming 153(1):5–11.Crossref, Google Scholar
• Gouveia J, Thomas R (2012) Convex hulls of algebraic sets. Anjos MF, Lasserre JB, eds. Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, New York), 113–138.Crossref, Google Scholar
• Gouveia J, Parrilo PA, Thomas RR (2010) Theta bodies for polynomial ideals. SIAM J. Optim. 20(4):2097–2118.Crossref, Google Scholar
• Gouveia J, Parrilo PA, Thomas RR (2013) Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2):248–264.Link, Google Scholar
• Gouveia J, Robinson RZ, Thomas RR (2013) Polytopes of minimum positive semidefinite rank. Discrete Comput. Geometry 50(3): 679–699.Crossref, Google Scholar
• Gouveia J, Robinson RZ, Thomas RR (2015) Worst-case results for positive semidefinite rank. Math. Programming 153(1):201–212.Crossref, Google Scholar
• Gouveia J, Laurent M, Parrilo PA, Thomas RR (2012) A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs. Math. Programming 133(1–2):203–225.Crossref, Google Scholar
• Grande F, Sanyal R (2014) Theta rank, levelness, and matroid minors. Preprint arXiv:1408.1262, https://arxiv.org/abs/1408.1262.Google Scholar
• Kaibel V, Pashkovich K, Theis DO (2012) Symmetry matters for sizes of extended formulations. SIAM J. Discrete Math. 26(3): 1361–1382.Crossref, Google Scholar
• Lasserre JB (2009) Convex sets with semidefinite representation. Math. Programming 120(2):457–477.Crossref, Google Scholar
• Pashkovich K (2014) Tight lower bounds on the sizes of symmetric extensions of permutahedra and similar results. Math. Oper. Res. 39(4):1330–1339.Link, Google Scholar
• Sanyal R, Sottile F, Sturmfels B (2011) Orbitopes. Mathematika 57(2):275–314.Crossref, Google Scholar
• Tunçel L (2000) Potential reduction and primal-dual methods. Wolkowicz H, Saigal R, Vandenberghe L, eds. Handbook of Semidefinite Programming: Theory, Algorithms, and Applications (Springer, New York), 235–265.Crossref, Google Scholar
• Yannakakis M (1991) Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci. 43(3):441–466.Crossref, Google Scholar