论文标题
对称的Grothendieck不平等
Symmetric Grothendieck inequality
论文作者
论文摘要
我们建立了Grothendieck不等式的类似物，其中矩形基质被对称/遗传学基质代替，而双线性形式则以二次形式代替。我们将其称为对称的Grothendieck不平等。尽管它的名称，但这是一个概括 - 原始的Grothendieck不平等是一种特殊情况。虽然还有其他提出这种不平等的建议，但我们的提议以两种重要方式有所不同：（i）我们没有其他要求，例如积极的半精力； （ii）我们的对称粒状常数是通用的，即独立于矩阵及其尺寸。对于任何对称的对称矩阵家族而言，我们对称的Grothendieck不平等的结果是“圆锥形的Grothendieck不平等”：原始的Grothendieck不平等是一种特殊情况；就像Nesterov $π/2 $ -Theorem一样，对应于正半矩阵的锥；以及与拉普拉斯人锥相对应的Goemans-Williamson不平等现象。对于其他锥体（例如，对角占主导地位的矩阵），我们会出现新的类似Grothendieck的不平等现象。略有扩展导致一个统一的框架，将任何类似于格罗望利克的不平等现象视为一个限制在圆锥体系列的“ grothendieck规范”家族中的两个规范之间的不平等。这使我们能够平等地站稳脚跟，nesterov $π/2 $ - 理论，本·泰尔·尼米罗夫斯基 - 根源$ 4/π$ - 理论 - 概括性的grothendieck不平等，订购-U $ $ p $ p $ pu $ po $ grothendieck不平等，良好的正面半限制的半固定的半透明的半透明式Grothendite grothendienite grothendieeckenecretalie; equality; equality；反过来，我们可以简化证据，将结果从实际到复杂，获得新的界限或建立现有界限的清晰度。对称的Grothendieck不等式也可以应用于获得NP-HARD组合，整数和非convex优化问题的多项式时间近似界限。
We establish an analogue of the Grothendieck inequality where the rectangular matrix is replaced by a symmetric/Hermitian matrix and the bilinear form by a quadratic form. We call this the symmetric Grothendieck inequality; despite its name, it is a generalization -- the original Grothendieck inequality is a special case. While there are other proposals for such an inequality, ours differs in two important ways: (i) we have no additional requirement like positive semidefiniteness; (ii) our symmetric Grothendieck constant is universal, i.e., independent of the matrix and its dimensions. A consequence of our symmetric Grothendieck inequality is a "conic Grothendieck inequality" for any family of cones of symmetric matrices: The original Grothendieck inequality is a special case; as is the Nesterov $π/2$-Theorem, which corresponds to the cones of positive semidefinite matrices; as well as the Goemans-Williamson inequality, which corresponds to the cones of Laplacians. For yet other cones, e.g., of diagonally dominant matrices, we get new Grothendieck-like inequalities. A slight extension leads to a unified framework that treats any Grothendieck-like inequality as an inequality between two norms within a family of "Grothendieck norms" restricted to a family of cones. This allows us to place on equal footing the Goemans-Williamson inequality, Nesterov $π/2$-Theorem, Ben-Tal-Nemirovski-Roos $4/π$-Theorem, generalized Grothendieck inequality, order-$p$ Grothendieck inequality, rank-constrained positive semidefinite Grothendieck inequality; and in turn allows us to simplify proofs, extend results from real to complex, obtain new bounds or establish sharpness of existing ones. The symmetric Grothendieck inequality may also be applied to obtain polynomial-time approximation bounds for NP-hard combinatorial, integer, and nonconvex optimization problems.
