×

Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization. (English) Zbl 1420.90043

Summary: The abbreviations LMI and SOS stand for “linear matrix inequality“ and “sum of squares,” respectively. The cone \(\Sigma_{n,2d}\) of SOS polynomials in \(n\) variables of degree at most \(2d\) is known to have a semidefinite extended formulation with one LMI of size \(\binom{n+d}{n}\). In other words, \(\Sigma_{n,2d}\) is a linear image of a set described by one LMI of size \(\binom{n+d}{n}\). We show that \(\Sigma_{n,2d}\) has no semidefinite extended formulation with finitely many LMIs of size less than \(\binom{n+d}{n}\). Thus, the standard extended formulation of \(\Sigma_{n,2d}\) is optimal in terms of the size of the LMIs. As a direct consequence, it follows that the cone of \(k\times k\) symmetric positive semidefinite matrices has no extended formulation with finitely many LMIs of size less than \(k\). We also derive analogous results for further cones considered in polynomial optimization, such as truncated quadratic modules, the cones of copositive and completely positive matrices, and the cone of sums of nonnegative circuit polynomials.

MSC:

90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
90C25 Convex programming
05D10 Ramsey theory
14P10 Semialgebraic sets and related spaces
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)

References:

[1] A. A. Ahmadi, G. Hall, A. Papachristodoulou, J. Saunderson, and Y. Zheng, {\it Improving efficiency and scalability of sum of squares optimization: Recent advances and limitations}, in Proceedings of the 56th Annual IEEE Conference on Decision and Control (CDC), 2017, pp. 453-462.
[2] M. F. Anjos and J. B. Lasserre, eds., {\it Handbook on Semidefinite, Conic and Polynomial Optimization}, Internat. Ser. Oper. Res. Management Sci. 166, Springer, New York, 2012, . · Zbl 1235.90002
[3] G. Averkov, V. Kaibel, and S. Weltge, {\it Maximum semidefinite and linear extension complexity of families of polytopes}, Math. Program., 167 (2018), pp. 381-394, . · Zbl 1384.52008
[4] A. Ben-Tal and A. Nemirovski, {\it Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications}, MPS/SIAM Ser. Optim. 2, SIAM, Philadelphia; MPS, Philadelphia, 2001, . · Zbl 0986.90032
[5] V. Chandrasekaran and P. Shah, {\it Relative entropy relaxations for signomial optimization}, SIAM J. Optim., 26 (2016), pp. 1147-1173, . · Zbl 1345.90066
[6] V. Chandrasekaran and P. Shah, {\it Relative entropy optimization and its applications}, Math. Program., 161 (2017), pp. 1-32, . · Zbl 1357.81037
[7] T. de Wolff, {\it private communication}, 2018.
[8] M. Dressler, {\it Sums of Nonnegative Circuit Polynomials}, Ph.D. thesis, Goethe-Universität Frankfurt am Main, Frankfurt, Germany, 2018. · Zbl 1514.14070
[9] M. Dressler, S. Iliman, and T. de Wolff, {\it A Positivstellensatz for sums of nonnegative circuit polynomials}, SIAM J. Appl. Algebra Geom., 1 (2017), pp. 536-555, . · Zbl 1372.14051
[10] M. Dressler, S. Iliman, and T. de Wolff, {\it An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming}, J. Symbolic Comput., 91 (2019), pp. 149-172, . · Zbl 1411.12003
[11] R. J. Duffin, E. L. Peterson, and C. Zener, {\it Geometric Programming: Theory and Application}, John Wiley & Sons, New York, London, Sydney, 1967. · Zbl 0171.17601
[12] M. Dür, {\it Copositive programming – a survey}, in Recent Advances in Optimization and Its Applications in Engineering, Springer, Berlin, Heidelberg, 2010, pp. 3-20.
[13] H. Fawzi, {\it On representing the positive semidefinite cone using the second-order cone}, Math. Program., (2018), . · Zbl 1412.90103
[14] H. Fawzi, J. Gouveia, P. A. Parrilo, R. Z. Robinson, and R. R. Thomas, {\it Positive semidefinite rank}, Math. Program., 153 (2015), pp. 133-177, . · Zbl 1327.90174
[15] H. Fawzi and M. Safey El Din, {\it A lower bound on the positive semidefinite rank of convex bodies}, SIAM J. Appl. Algebra Geom., 2 (2018), pp. 126-139, . · Zbl 1391.90456
[16] H. Fawzi, J. Saunderson, and P. A. Parrilo, {\it Equivariant semidefinite lifts and sum-of-squares hierarchies}, SIAM J. Optim., 25 (2015), pp. 2212-2243, . · Zbl 1327.90175
[17] H. Fawzi, J. Saunderson, and P. A. Parrilo, {\it Sparse sums of squares on finite abelian groups and improved semidefinite lifts}, Math. Program., 160 (2016), pp. 149-191, . · Zbl 1387.90180
[18] H. Fawzi, J. Saunderson, and P. A. Parrilo, {\it Equivariant semidefinite lifts of regular polygons}, Math. Oper. Res., 42 (2017), pp. 472-494, . · Zbl 1364.90245
[19] S. Fiorini, V. Kaibel, K. Pashkovich, and D. O. Theis, {\it Combinatorial bounds on nonnegative rank and extended formulations}, Discrete Math., 313 (2013), pp. 67-83, . · Zbl 1259.90111
[20] M. Ghasemi and M. Marshall, {\it Lower bounds for a polynomial in terms of its coefficients}, Arch. Math. (Basel), 95 (2010), pp. 343-353, . · Zbl 1205.12001
[21] M. Ghasemi and M. Marshall, {\it Lower bounds for polynomials using geometric programming}, SIAM J. Optim., 22 (2012), pp. 460-473, . · Zbl 1272.12004
[22] A. P. Goucha, J. Gouveia, and P. M. Silva, {\it On ranks of regular polygons}, SIAM J. Discrete Math., 31 (2017), pp. 2612-2625, . · Zbl 1384.52004
[23] J. Gouveia, P. A. Parrilo, and R. R. Thomas, {\it Lifts of convex sets and cone factorizations}, Math. Oper. Res., 38 (2013), pp. 248-264, . · Zbl 1291.90172
[24] R. L. Graham, B. L. Rothschild, and J. H. Spencer, {\it Ramsey Theory}, 2nd ed., Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, New York, 1990. · Zbl 0705.05061
[25] D. Hilbert, {\it Über die Darstellung definiter Formen als Summe von Formenquadraten}, Math. Ann., 32 (1888), pp. 342-350. · JFM 20.0198.02
[26] S. Iliman and T. de Wolff, {\it Amoebas, nonnegative polynomials and sums of squares supported on circuits}, Res. Math. Sci., 3 (2016), 9, . · Zbl 1415.11071
[27] J. B. Lasserre, {\it An Introduction to Polynomial and Semi-Algebraic Optimization}, Cambridge Texts Appl. Math., Cambridge University Press, Cambridge, UK, 2015, . · Zbl 1320.90003
[28] M. Laurent, {\it Sums of squares, moment matrices and optimization over polynomials}, in Emerging Applications of Algebraic Geometry, IMA Vol. Math. Appl. 149, Springer, New York, 2009, pp. 157-270, . · Zbl 1163.13021
[29] J. R. Lee, P. Raghavendra, and D. Steurer, {\it Lower bounds on the size of semidefinite programming relaxations}, in Proceedings of the ACM Symposium on Theory of Computing (STOC), 2015, pp. 567-576. · Zbl 1321.90099
[30] M. Marshall, {\it Positive Polynomials and Sums of Squares}, Math. Surveys Monogr. 146, American Mathematical Society, Providence, RI, 2008, . · Zbl 1169.13001
[31] J. E. Maxfield and H. Minc, {\it On the matrix equation X’X=A}, Proc. Edinburgh Math. Soc. (2), 13 (1962/1963), pp. 125-129, . · Zbl 0112.25101
[32] H. D. Mittelmann, {\it An independent benchmarking of SDP and SOCP solvers}, Math. Program., 95 (2003), pp. 407-430, . · Zbl 1030.90080
[33] J. Nie, {\it Linear optimization with cones of moments and nonnegative polynomials}, Math. Program., 153 (2015), pp. 247-274, . · Zbl 1327.65113
[34] R. T. Rockafellar, {\it Convex Analysis}, Princeton Landmarks Math., Princeton University Press, Princeton, NJ, 1997. · Zbl 0932.90001
[35] J. Saunderson and P. A. Parrilo, {\it Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones}, Math. Program., 153 (2015), pp. 309-331, . · Zbl 1327.90180
[36] J. Saunderson, P. A. Parrilo, and A. S. Willsky, {\it Semidefinite descriptions of the convex hull of rotation matrices}, SIAM J. Optim., 25 (2015), pp. 1314-1343, . · Zbl 1317.90231
[37] J. F. Saunderson, {\it Semidefinite Representations with Applications in Estimation and Inference}, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 2015; available online from .
[38] C. Scheiderer, {\it Spectrahedral shadows}, SIAM J. Appl. Algebra Geom., 2 (2018), pp. 26-44, . · Zbl 1391.90462
[39] H. Seidler and T. de Wolff, {\it An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization}, preprint, , 2018.
[40] H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., {\it Handbook of Semidefinite Programming. Theory, Algorithms, and Applications}, Internat. Ser. Oper. Res. Management Sci. 27, Kluwer Academic Publishers, Boston, MA, 2000, . · Zbl 0962.90001
[41] G. M. Ziegler, {\it Lectures on Polytopes}, Grad. Texts in Math. 152, Springer-Verlag, New York, 1995, . · Zbl 0823.52002
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.