×

zbMATH — the first resource for mathematics

Approximate cone factorizations and lifts of polytopes. (English) Zbl 1319.52010
Summary: In this paper, we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust generalization of the famous result of M. Yannakakis [J. Comput. Syst. Sci. 43, No. 3, 441–466 (1991; Zbl 0748.90074)] that polyhedral lifts of a polytope are controlled by (exact) nonnegative factorizations of its slack matrix. Our approximations behave well under polarity and have efficient representations using second order cones. We establish a direct relationship between the quality of the factorization and the quality of the approximations, and our results extend to generalized slack matrices that arise from a polytope contained in a polyhedron.

MSC:
52A23 Asymptotic theory of convex bodies
52-02 Research exposition (monographs, survey articles) pertaining to convex and discrete geometry
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95(1), 3-51 (2003) · Zbl 1153.90522
[2] Borwein, J; Wolkowicz, H, Regularizing the abstract convex program, J. Math. Anal. Appl., 83, 495-530, (1981) · Zbl 0467.90076
[3] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[4] Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 480-489. IEEE (2012) · Zbl 1343.68308
[5] Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 19, (2012) · Zbl 1293.68137
[6] Gillis, N; Glineur, F, On the geometric interpretation of the nonnegative rank, Linear Algebra Its Appl., 437, 2685-2712, (2012) · Zbl 1258.65039
[7] Gouveia, J; Parrilo, PA; Thomas, RR, Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 248-264, (2013) · Zbl 1291.90172
[8] Gouveia, J., Robinson, R. Z., Thomas, R. R.: Worst-Case Results for Positive Semidefinite Rank. arXiv:1305.4600 (2013) · Zbl 1344.90046
[9] Lobo, M; Vandenberghe, L; Boyd, S; Lebret, H, Applications of second-order cone programming, Linear Algebra Its Appl., 284, 193-228, (1998) · Zbl 0946.90050
[10] Nesterov, Y.E., Nemirovski, A.: Interior Point Polynomial Methods in Convex Programming, volume 13 of Studies in Applied Mathematics. Siam, Philadelphia (1994)
[11] Pashkovich, K.: Extended Formulations for Combinatorial Polytopes. PhD thesis, Magdeburg Universität (2012) · Zbl 1267.90098
[12] Pataki, G, On the closedness of the linear image of a closed convex cone, Math. Oper. Res., 32, 395-412, (2007) · Zbl 1341.90146
[13] Pataki, G, On the connection of facially exposed and Nice cones, J. Math. Anal. Appl., 400, 211-221, (2013) · Zbl 1267.90098
[14] Renegar, J, Hyperbolic programs, and their derivative relaxations, Found. Comput. Math., 6, 59-79, (2006) · Zbl 1130.90363
[15] Rockafellar, R.T.: Convex Analysis. Princeton Mathematical, vol. 28. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[16] Saunderson, J., Parrilo, P.A.: Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones. Math. Program. Ser. A. (2014). doi:10.1007/s10107-014-0804-y · Zbl 1327.90180
[17] Sonnevend, Gy.: An “analytical centre” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In: System Modelling and Optimization, pp. 866-875. Springer, Berlin (1986) · Zbl 0602.90106
[18] Sturm, JF; Zhang, S, An \({O(\sqrt{n L})}\) iteration bound primal-dual cone affine scaling algorithm for linear programming, Math. Program., 72, 177-194, (1996) · Zbl 0853.90085
[19] Yannakakis, M, Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci., 43, 441-466, (1991) · 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.