Extension complexity

In convex geometry and polyhedral combinatorics, the extension complexity of a convex polytope ${\displaystyle P}$ is the smallest number of facets among convex polytopes ${\displaystyle Q}$ that have ${\displaystyle P}$ as a projection. In this context, ${\displaystyle Q}$ is called an extended formulation of ${\displaystyle P}$; it may have much higher dimension than ${\displaystyle P}$.^[1][2][3]

The extension complexity depends on the precise shape of ${\displaystyle P}$, not just on its combinatorial structure. For instance, regular polygons with ${\displaystyle n}$ sides have extension complexity ${\displaystyle O(\log n)}$ (expressed using big O notation),^[4][5] but some other convex ${\displaystyle n}$-gons have extension complexity at least proportional to ${\displaystyle {\sqrt {n}}}$.^[5]

If a polytope describing the feasible solutions to a combinatorial optimization problem has low extension complexity, this could potentially be used to devise efficient algorithms for the problem, using linear programming on its extended formulation. For this reason, researchers have studied the extension complexity of the polytopes arising in this way.^[6] For instance, it is known that the matching polytope has exponential extension complexity.^[7] On the other hand, the independence polytope of regular matroids has polynomial extension complexity.^[8]

The notion of extension complexity has also been generalized from linear programming to semidefinite programming, by considering projections of spectrahedra in place of projections of polytopes.^[9][10]

References

1. Balas, Egon (2005), "Projection, lifting and extended formulation in integer and combinatorial optimization", Annals of Operations Research, 140: 125–161, doi:10.1007/s10479-005-3969-1, MR 2194735, S2CID 18252683
2. Kaibel, Volker (2011), "Extended formulations in combinatorial optimization", Optima, 85: 2–7, arXiv:1104.1023
3. Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2013), "Extended formulations in combinatorial optimization", Annals of Operations Research, 204: 97–143, doi:10.1007/s10479-012-1269-0, MR 3039264, S2CID 254236751
4. Ben-Tal, Aharon; Nemirovski, Arkadi (2001), "On polyhedral approximations of the second-order cone", Mathematics of Operations Research, 26 (2): 193–205, doi:10.1287/moor.26.2.193.10561, MR 1895823
5. Fiorini, Samuel; Rothvoß, Thomas; Tiwary, Hans Raj (2012), "Extended formulations for polygons", Discrete & Computational Geometry, 48 (3): 658–668, arXiv:1107.0371, doi:10.1007/s00454-012-9421-9, MR 2957636, S2CID 254032514
6. Avis, David; Tiwary, Hans Raj (2015), "On the extension complexity of combinatorial polytopes", Mathematical Programming, 153 (1, Ser. B): 95–115, arXiv:1302.2340, doi:10.1007/s10107-014-0764-2, MR 3395543, S2CID 254143169
7. Rothvoß, Thomas (2017), "The matching polytope has exponential extension complexity", Journal of the ACM, 64 (6): A41:1–A41:19, arXiv:1311.2369, doi:10.1145/3127497, MR 3713797, S2CID 47045361
8. Aprile, Manuel; Fiorini, Samuel (July 2021), "Regular matroids have polynomial extension complexity", Mathematics of Operations Research, 47: 540–559, arXiv:1909.08539, doi:10.1287/moor.2021.1137, S2CID 202660764
9. Briët, Jop; Dadush, Daniel; Pokutta, Sebastian (2015), "On the existence of 0/1 polytopes with high semidefinite extension complexity", Mathematical Programming, 153 (1, Ser. B): 179–199, doi:10.1007/s10107-014-0785-x, MR 3395546, S2CID 254144689
10. Lee, James R.; Raghavendra, Prasad; Steurer, David (2015), "Lower bounds on the size of semidefinite programming relaxations", in Servedio, Rocco A.; Rubinfeld, Ronitt (eds.), Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, Association for Computing Machinery, pp. 567–576, arXiv:1411.6317, doi:10.1145/2746539.2746599, S2CID 14438019