On Polyhedral Approximations of the Positive Semidefinite Cone

• 成果类型: Article
• 署名作者: Fawzi, Hamza
• 署名单位: University of Cambridge
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2020.1077
• 发表日期: 2021
• 页码: 1479-1489
• 关键词: INEQUALITIES; optimization

摘要

It is well known that state-of-the-art linear programming solvers are more efficient than their semidefinite programming counterparts and can scale to much larger problem sizes. This leads us to consider the question, how well can we approximate semidefinite programs with linear programs? In this paper, we prove lower bounds on the size of linear programs that approximate the positive semidefinite cone. Let D be the set of n x n positive semidefinite matrices of trace equal to one. We prove two results on the hardness of approximating Dwith polytopes. We show that if 0 < epsilon < 1 and A is an arbitrary matrix of trace equal to one, any polytope P such that (1 - epsilon) (D - A) subset of P subset of D - A must have linear programming extension complexity at least exp(c root n), where c > 0 is a constant that depends on e. Second, we show that any polytope P such that D subset of P and such that the Gaussian width of P is at most twice the Gaussian width of D must have extension complexity at least exp(cn(1 / 3)). Our bounds are both superpolynomial in n and demonstrate that there is no generic way of approximating semidefinite programs with compact linear programs. The main ingredient of our proofs is hypercontractivity of the noise operator on the hypercube.