## Extension complexity of low-dimensional polytopes

HTML articles powered by AMS MathViewer

- by Matthew Kwan, Lisa Sauermann and Yufei Zhao PDF
- Trans. Amer. Math. Soc.
**375**(2022), 4209-4250

## Abstract:

Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the *extension complexity* of a polytope $P$ is defined to be the minimum number of facets of a (possibly higher-dimensional) polytope from which $P$ can be obtained as a (linear) projection. This notion is motivated by its relevance to combinatorial optimisation, and has been studied intensively for various specific polytopes associated with important optimisation problems. In this paper we study extension complexity as a parameter of general polytopes, more specifically considering various families of low-dimensional polytopes.

First, we prove that for a fixed dimension $d$, the extension complexity of a random $d$-dimensional polytope (obtained as the convex hull of random points in a ball or on a sphere) is typically on the order of the square root of its number of vertices. Second, we prove that any cyclic $n$-vertex polygon (whose vertices lie on a circle) has extension complexity at most $24\sqrt n$. This bound is tight up to the constant factor $24$. Finally, we show that there exists an $n^{o(1)}$-dimensional polytope with at most $n$ vertices and extension complexity $n^{1-o(1)}$. Our theorems are proved with a range of different techniques, which we hope will be of further interest.

## References

- Sanjeev Arora, Rong Ge, Ravi Kannan, and Ankur Moitra,
*Computing a nonnegative matrix factorization—provably*, SIAM J. Comput.**45**(2016), no. 4, 1582–1611. MR**3542024**, DOI 10.1137/130913869 - Imre Bárány,
*Random polytopes, convex bodies, and approximation*, Stochastic geometry, Lecture Notes in Math., vol. 1892, Springer, Berlin, 2007, pp. 77–118. MR**2327291**, DOI 10.1007/978-3-540-38175-4_{2} - Imre Bárány,
*Random points and lattice points in convex bodies*, Bull. Amer. Math. Soc. (N.S.)**45**(2008), no. 3, 339–365. MR**2402946**, DOI 10.1090/S0273-0979-08-01210-X - Imre Bárány and Leoni Dalla,
*Few points to generate a random polytope*, Mathematika**44**(1997), no. 2, 325–331. MR**1600549**, DOI 10.1112/S0025579300012638 - LeRoy B. Beasley, Hartmut Klauck, Troy Lee, and Dirk Oliver Theis,
*Communication complexity, linear optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl Seminar 13082)*, Dagstuhl Rep.**3**(2013), 127–143. - LeRoy B. Beasley and Thomas J. Laffey,
*Real rank versus nonnegative rank*, Linear Algebra Appl.**431**(2009), no. 12, 2330–2335. MR**2563025**, DOI 10.1016/j.laa.2009.02.034 - Aharon Ben-Tal and Arkadi Nemirovski,
*On polyhedral approximations of the second-order cone*, Math. Oper. Res.**26**(2001), no. 2, 193–205. MR**1895823**, DOI 10.1287/moor.26.2.193.10561 - Cristiano Bocci, Enrico Carlini, and Fabio Rapallo,
*Perturbation of matrices and nonnegative rank with a view toward statistical models*, SIAM J. Matrix Anal. Appl.**32**(2011), no. 4, 1500–1512. MR**2869495**, DOI 10.1137/110825455 - Stéphane Boucheron, Gábor Lugosi, and Pascal Massart,
*Concentration inequalities using the entropy method*, Ann. Probab.**31**(2003), no. 3, 1583–1614. MR**1989444**, DOI 10.1214/aop/1055425791 - Gábor Braun and Sebastian Pokutta,
*Common information and unique disjointness*, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science—FOCS 2013, IEEE Computer Soc., Los Alamitos, CA, 2013, pp. 688–697. MR**3246272**, DOI 10.1109/FOCS.2013.79 - C. Buchta, J. Müller, and R. F. Tichy,
*Stochastical approximation of convex bodies*, Math. Ann.**271**(1985), no. 2, 225–235. MR**783553**, DOI 10.1007/BF01455988 - Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer,
*Approximate constraint satisfaction requires large LP relaxations*, J. ACM**63**(2016), no. 4, Art. 34, 22. MR**3570928**, DOI 10.1145/2811255 - Joel E. Cohen and Uriel G. Rothblum,
*Nonnegative ranks, decompositions, and factorizations of nonnegative matrices*, Linear Algebra Appl.**190**(1993), 149–168. MR**1230356**, DOI 10.1016/0024-3795(93)90224-C - Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli,
*Extended formulations in combinatorial optimization*, Ann. Oper. Res.**204**(2013), 97–143. MR**3039264**, DOI 10.1007/s10479-012-1269-0 - Samuel Fiorini, Volker Kaibel, Kanstantsin Pashkovich, and Dirk Oliver Theis,
*Combinatorial bounds on nonnegative rank and extended formulations*, Discrete Math.**313**(2013), no. 1, 67–83. MR**3016973**, DOI 10.1016/j.disc.2012.09.015 - Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf,
*Exponential lower bounds for polytopes in combinatorial optimization*, J. ACM**62**(2015), no. 2, Art. 17, 23. MR**3346156**, DOI 10.1145/2716307 - Samuel Fiorini, Thomas Rothvoß, and Hans Raj Tiwary,
*Extended formulations for polygons*, Discrete Comput. Geom.**48**(2012), no. 3, 658–668. MR**2957636**, DOI 10.1007/s00454-012-9421-9 - P. Frankl and R. M. Wilson,
*Intersection theorems with geometric consequences*, Combinatorica**1**(1981), no. 4, 357–368. MR**647986**, DOI 10.1007/BF02579457 - Nicolas Gillis,
*The why and how of nonnegative matrix factorization*, Regularization, optimization, kernels, and support vector machines, Chapman & Hall/CRC Mach. Learn. Pattern Recogn. Ser., CRC Press, Boca Raton, FL, 2015, pp. 257–291. MR**3380642** - João Gouveia, Roland Grappe, Volker Kaibel, Kanstantsin Pashkovich, Richard Z. Robinson, and Rekha R. Thomas,
*Which nonnegative matrices are slack matrices?*, Linear Algebra Appl.**439**(2013), no. 10, 2921–2933. MR**3116402**, DOI 10.1016/j.laa.2013.08.009 - Peter M. Gruber,
*Comparisons of best and random approximation of convex bodies by polytopes*, Rend. Circ. Mat. Palermo (2) Suppl.**50**(1997), 189–216. II International Conference in “Stochastic Geometry, Convex Bodies and Empirical Measures” (Agrigento, 1996). MR**1602970** - Pavel Hrubeš,
*On the nonnegative rank of distance matrices*, Inform. Process. Lett.**112**(2012), no. 11, 457–461. MR**2905148**, DOI 10.1016/j.ipl.2012.02.009 - Daniel Hug,
*Random polytopes*, Stochastic geometry, spatial statistics and random fields, Lecture Notes in Math., vol. 2068, Springer, Heidelberg, 2013, pp. 205–238. MR**3059649**, DOI 10.1007/978-3-642-33305-7_{7} - Volker Kaibel,
*Extended formulations in combinatorial optimization*, Optima 85, 2011. - Volker Kaibel and Kanstantsin Pashkovich,
*Constructing extended formulations from reflection relations*, Integer programming and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 6655, Springer, Heidelberg, 2011, pp. 287–300. MR**2820916**, DOI 10.1007/978-3-642-20807-2_{2}3 - Volker Kaibel and Stefan Weltge,
*A short proof that the extension complexity of the correlation polytope grows exponentially*, Discrete Comput. Geom.**53**(2015), no. 2, 397–401. MR**3316228**, DOI 10.1007/s00454-014-9655-9 - Hartmut Klauck, Troy Lee, Dirk Oliver Theis, and Rekha R. Thomas,
*Limitations of convex programming: lower bounds on extended formulations and factorization ranks (Dagstuhl Seminar 15082)*, Dagstuhl Rep.**5**(2015), 109–127. - Troy Lee,
*Some open problems around nonnegative rank*, http://research.cs.rutgers.edu/~troyjlee/open_problems.pdf, 2013. - S. Li,
*Concise formulas for the area and volume of a hyperspherical cap*, Asian J. Math. Stat.**4**(2011), no. 1, 66–70. MR**2813331**, DOI 10.3923/ajms.2011.66.70 - Lek-Heng Lim and Pierre Comon,
*Nonnegative approximations of nonnegative tensors*, J. Chemometrics**23**(2009), 432–441. - Matthew M. Lin and Moody T. Chu,
*On the nonnegative rank of Euclidean distance matrices*, Linear Algebra Appl.**433**(2010), no. 3, 681–689. MR**2653832**, DOI 10.1016/j.laa.2010.03.038 - Ankur Moitra,
*An almost optimal algorithm for computing nonnegative rank*, SIAM J. Comput.**45**(2016), no. 1, 156–173. MR**3456395**, DOI 10.1137/140990139 - Arnau Padrol,
*Extension complexity of polytopes with few vertices or facets*, SIAM J. Discrete Math.**30**(2016), no. 4, 2162–2176. MR**3574580**, DOI 10.1137/16M1063721 - Arnau Padrol and Julian Pfeifle,
*Polygons as sections of higher-dimensional polytopes*, Electron. J. Combin.**22**(2015), no. 1, Paper 1.24, 16. MR**3315466** - Kanstantsin Pashkovich,
*Extended formulations for combinatorial polytopes*, Ph.D. Thesis, Otto-von-Guericke-Universität Magdeburg, 2012. - H. Raynaud,
*Sur l’enveloppe convexe des nuages de points aléatoires dans $R^{n}$. I*, J. Appl. Probability**7**(1970), 35–48 (French). MR**258089**, DOI 10.2307/3212146 - Matthias Reitzner,
*The combinatorial structure of random polytopes*, Adv. Math.**191**(2005), no. 1, 178–208. MR**2102847**, DOI 10.1016/j.aim.2004.03.006 - A. Rényi and R. Sulanke,
*Über die konvexe Hülle von $n$ zufällig gewählten Punkten*, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete**2**(1963), 75–84 (1963) (German). MR**156262**, DOI 10.1007/BF00535300 - Thomas Rothvoss,
*The matching polytope has exponential extension complexity*, J. ACM**64**(2017), no. 6, Art. 41, 19. MR**3713797**, DOI 10.1145/3127497 - Rolf Schneider,
*Discrete aspects of stochastic geometry*, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 167–184. MR**1730165** - Rolf Schneider,
*Recent results on random polytopes*, Boll. Unione Mat. Ital. (9)**1**(2008), no. 1, 17–39. MR**2387995** - Jiří Sgall,
*Bounds on pairs of families with restricted intersections*, Combinatorica**19**(1999), no. 4, 555–566. MR**1773657**, DOI 10.1007/s004939970007 - Ya. N. Shitov,
*Tropical lower bounds for extended formulations. II. Deficiency graphs*, Izv. Ross. Akad. Nauk Ser. Mat.**83**(2019), no. 1, 203–216 (Russian, with Russian summary); English transl., Izv. Math.**83**(2019), no. 1, 184–195. MR**3920396**, DOI 10.4213/im8698 - Yaroslav Shitov,
*An upper bound for nonnegative rank*, J. Combin. Theory Ser. A**122**(2014), 126–132. MR**3127681**, DOI 10.1016/j.jcta.2013.10.004 - Yaroslav Shitov,
*Sublinear extensions of polygons*, Preprint, arXiv:1412.0728v1, 2014. - Yaroslav Shitov,
*A universality theorem for nonnegative matrix factorizations*, Preprint, arXiv:1606.09068, 2018. - Yaroslav Shitov,
*Euclidean distance matrices and separations in communication complexity theory*, Discrete Comput. Geom.**61**(2019), no. 3, 653–660. MR**3918551**, DOI 10.1007/s00454-018-9988-x - Yaroslav Shitov,
*Sublinear extensions of polygons*, Preprint, arXiv:1412.0728v2, 2020. *Combinatorics and probability*, Oberwolfach Rep.**10**(2013), no. 2, 1087–1152. Abstracts from the workshop held April 14–20, 2013; Organized by Béla Bollabás, Michael Krivelevich and Emo Welzl. MR**3013922**, DOI 10.4171/OWR/2013/18- Dirk Oliver Theis,
*Extension complexity of (convex) polygons*, Open Problem Garden, http://www.openproblemgarden.org/op/extension_complexity_of_convex_polygons, 2011. - Dirk Oliver Theis,
*Open questions about nonnegative rank and related concepts*, 2013, Archived at https://web.archive.org/web/20170111025052/http://dirkolivertheis.blogspot.de/2013/08/open-questions-about-nonnegative-rank.html. - Arnaud Vandaele, Nicolas Gillis, François Glineur, and Daniel Tuyttens,
*Heuristics for exact nonnegative matrix factorization*, J. Global Optim.**65**(2016), no. 2, 369–400. MR**3498572**, DOI 10.1007/s10898-015-0350-z - François Vanderbeck and Laurence A. Wolsey,
*Reformulation and decomposition of integer programs*, 50 Years of Integer Programming 1958-2008, Springer, Berlin Heidelberg, November 2009, pp. 431–502. - Stephen A. Vavasis,
*On the complexity of nonnegative matrix factorization*, SIAM J. Optim.**20**(2009), no. 3, 1364–1377. MR**2587731**, DOI 10.1137/070709967 - V. H. Vu,
*Sharp concentration of random polytopes*, Geom. Funct. Anal.**15**(2005), no. 6, 1284–1318. MR**2221249**, DOI 10.1007/s00039-005-0541-8 - Wolfgang Weil and John A. Wieacker,
*Stochastic geometry*, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 1391–1438. MR**1243013** - Mihalis Yannakakis,
*Expressing combinatorial optimization problems by linear programs*, J. Comput. System Sci.**43**(1991), no. 3, 441–466. MR**1135472**, DOI 10.1016/0022-0000(91)90024-Y

## Additional Information

**Matthew Kwan**- Affiliation: IST Austria, Klosterneuburg, Austria
- MR Author ID: 1056015
- ORCID: 0000-0002-4003-7567
- Email: matthew.kwan@ist.ac.at
**Lisa Sauermann**- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachussetts
- MR Author ID: 1051738
- Email: lsauerma@mit.edu
**Yufei Zhao**- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts
- MR Author ID: 864404
- Email: yufeiz@mit.edu
- Received by editor(s): June 25, 2020
- Received by editor(s) in revised form: October 7, 2021
- Published electronically: March 31, 2022
- Additional Notes: The research of the first author was supported by SNSF Project 178493 and NSF Award DMS-1953990.

The research of the second author supported by NSF Award DMS-1953772.

The research of the third author was supported by NSF Award DMS-1764176, NSF CAREER Award DMS-2044606, a Sloan Research Fellowship, and the MIT Solomon Buchsbaum Fund. - © Copyright 2022 Copyright by Matthew Kwan; Lisa Sauermann; Yufei Zhao
- Journal: Trans. Amer. Math. Soc.
**375**(2022), 4209-4250 - MSC (2020): Primary 52B05
- DOI: https://doi.org/10.1090/tran/8614
- MathSciNet review: 4419057