On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones

• 成果类型: Article
• 署名作者: Song, Dogyoon; Parrilo, Pablo A.
• 署名单位: University of Michigan System; University of Michigan; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01795-7
• 发表日期: 2023
• 页码: 733-785
• 关键词: Optimization; matrices; squares; SUM

摘要

We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a cone that can be described by smaller-sized PSD constraints. Specifically, we ask the question: how closely can we approximate the set of unit-trace nxn PSD matrices, denoted by D, using at most N number of k x k PSD constraints? In this paper, we prove lower bounds on N to achieve a good approximation of D by considering two constructions of an approximating set. First, we consider the unit-trace nxn symmetric matrices that are PSD when restricted to a fixed set of k-dimensional subspaces in R-n. We prove that if this set is a good approximation of D, then the number of subspaces must be at least exponentially large in n for any k = o(n). Second, we show that any set S that approximates D within a constant approximation ratio must have superpolynomial S-+(k)-extension complexity. To be more precise, if S is a constant factor approximation of D, then S must have S-+(k)-extension complexity at least exp(C . min{root n, n/k}) where C is some absolute constant. In addition, we show that any set S such that D subset of S and the Gaussian width of S is at most a constant times larger than the Gaussian width of D must have S-+(k)-extension complexity at least exp(C . min{n(1/3), root n/k}). These results imply that the cone of n x n PSD matrices cannot be approximated by a polynomial number of k x k PSD constraints for any k = o(n/ log(2) n). These results generalize the recent work of Fawzi (Math Oper Res 46(4):1479-1489, 2021) on the hardness of polyhedral approximations of S-+(n), which corresponds to the special case with k = 1.