×

zbMATH — the first resource for mathematics

Equivariant semidefinite lifts and sum-of-squares hierarchies. (English) Zbl 1327.90175

MSC:
90C22 Semidefinite programming
52B15 Symmetry properties of polytopes
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] A. Barvinok and G. Blekherman, Convex geometry of orbits, in Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ. 52, J. E. Goodman, Já. Pach, and E. Welzl, eds., Cambridge University Press, Cambridge, UK, 2005, pp. 51–77. · Zbl 1096.52002
[2] A. Barvinok and A. Moiseevich Vershik, Convex hulls of orbits of representations of finite groups and combinatorial optimization, Funct. Anal. Appl., 22 (1988), pp. 224–225. · Zbl 0688.20006
[3] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MOS-SIAM Ser. Optim. 2, SIAM, Philadelphia, 2001. · Zbl 0986.90032
[4] G. Blekherman, P. A. Parrilo, and R. R. Thomas, eds., Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Ser. Optim. 13, SIAM, Philadelphia, 2013.
[5] R. D. Carr and G. Konjevod, Polyhedral combinatorics, in Tutorials on Emerging Methodologies and Applications in Operations Research, Int. Ser. Oper. Res. Mngt. Sci. 76, H. J. Greenberg, ed., Springer, New York, 2004, pp. 2-1–2-46.
[6] S. O. Chan, J. R. Lee, P. Raghavendra, and D. Steurer, Approximate constraint satisfaction requires large LP relaxations, in Proceedings of the IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2013, pp. 350–359. · Zbl 1394.68170
[7] H. Fawzi, J. Gouveia, P. A. Parrilo, R. Z. Robinson, and R. R. Thomas, Positive semidefinite rank, Math. Program., 153 (2015), pp. 133–177. · Zbl 1327.90174
[8] H. Fawzi, J. Saunderson, and P. A. Parrilo, Equivariant Semidefinite Lifts of Regular Polygons, preprint, arXiv:1409.4379, 2014. · Zbl 1364.90245
[9] H. Fawzi, J. Saunderson, and P. A. Parrilo, Sparse Sum-of-Squares Certificates on Finite Abelian Groups, preprint, arXiv:1503.01207, 2015. · Zbl 1327.90175
[10] M. Goemans, Smallest compact formulation for the permutahedron, Math. Program. Ser. B, 153 (2015), pp. 5––11. · Zbl 1322.90048
[11] J. Gouveia, M. Laurent, P. A. Parrilo, and R. Thomas, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, Math. Program., 133 (2012), pp. 203–225. · Zbl 1262.90123
[12] J. Gouveia, P. A. Parrilo, and R. R. Thomas, Theta bodies for polynomial ideals, SIAM J. Optim., 20 (2010), pp. 2097–2118. · Zbl 1213.90190
[13] J. Gouveia, P. A. Parrilo, and R. R. Thomas, Lifts of convex sets and cone factorizations, Math. Oper. Res., 38 (2013), pp. 248–264. · Zbl 1291.90172
[14] J. Gouveia, R. Z. Robinson, and R. R. Thomas, Polytopes of minimum positive semidefinite rank, Discrete Comput. Geom., 50 (2013), pp. 679–699. · Zbl 1279.52023
[15] A. Horn, Doubly stochastic matrices and the diagonal of a rotation matrix, Amer. J. Math., 76 (1954), pp. 620–630. · Zbl 0055.24601
[16] V. Kaibel and K. Pashkovich, Constructing extended formulations from reflection relations, in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 6655, O. Güünlüük and G. J. Woeginger, eds., Springer, Berlin, 2011, pp. 287–300. · Zbl 1341.90148
[17] V. Kaibel, K. Pashkovich, and D. O. Theis, Symmetry matters for the sizes of extended formulations, in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 6080, F. Eisenbrand and F. B. Shepherd, eds., Springer, Berlin, 2010, pp. 135–148. · Zbl 1285.90052
[18] J.-B. Lasserre, Convex sets with semidefinite representation, Math. Program., 120 (2009), pp. 457–477. · Zbl 1198.14055
[19] M. Laurent, Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope, Math. Oper. Res., 28 (2003), pp. 871–883. · Zbl 1082.90085
[20] M. Laurent, Semidefinite relaxations for max-cut, in The Sharpest Cut: The Impact of Manfred Padberg and His Work, M. Gröötschel, ed., SIAM, Philadelphia, 2004, pp. 257–290.
[21] J. R. Lee, P. Raghavendra, and D. Steurer, Lower Bounds on the Size of Semidefinite Programming Relaxations, preprint, arXiv:1411.6317, 2014.
[22] J. R. Lee, P. Raghavendra, D. Steurer, and N. Tan, On the power of symmetric LP and SDP relaxations, in Proceedings of the 29th IEEE Conference on Computational Complexity, IEEE Press, Piscataway, NJ, 2014, pp. 13–21.
[23] L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25 (1979), pp. 1–7.
[24] K. Pashkovich, Tight lower bounds on the sizes of symmetric extensions of permutahedra and similar results, Math. Oper. Res., 39 (2014), pp. 1330–1339. · Zbl 1310.90100
[25] R. Sanyal, F. Sottile, and B. Sturmfels, Orbitopes, Mathematika, 57 (2011), pp. 275–314.
[26] J. Saunderson, P. A. Parrilo, and A. S. Willsky, Semidefinite descriptions of the convex hull of rotation matrices, SIAM J. Optim., 25 (2015), pp. 1314–1343. · Zbl 1317.90231
[27] J.-P. Serre, Linear Representations of Finite Groups, Springer, New York, 1977.
[28] L. Tuncel, Potential reduction and primal-dual methods, in Handbook of Semidefinite Programming, Int. Ser. Oper. Res. Mngt. Sci. 27, H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Springer, New York, 2000, pp. 235–265. · Zbl 0957.90524
[29] M. Yannakakis, Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci., 43 (1991), pp. 441–466. · Zbl 0748.90074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.