论文标题
正方形和稀疏半决赛编程的总和
Sums of Squares and Sparse Semidefinite Programming
论文作者
论文摘要
我们考虑了两个看似无关的问题：非负多项式与真实品种的正方和总和之间的关系，以及稀疏的半决赛编程。当真正的品种$ x $由二次无方形的单样理想定义时，这种连接是自然的。在这种情况下，$ x $上的非负多项式和正方金总和也是正数矩阵完成中的天然对象。 $ x $以上的非负二次形式自然对应于部分指定的矩阵，在该矩阵中，所有完全指定的平方块都是PSD，正方形的二次形式的总和自然对应于可以完成的部分指定的矩阵，这些矩阵可以完成为PSD矩阵。我们通过平方和在非负多项式近似的近似值上显示了定量结果，这导致在稀疏的半限定编程中应用。
We consider two seemingly unrelated questions: the relationship between nonnegative polynomials and sums of squares on real varieties, and sparse semidefinite programming. This connection is natural when a real variety $X$ is defined by a quadratic square-free monomial ideal. In this case nonnegative polynomials and sums of squares on $X$ are also natural objects in positive semidefinite matrix completion. Nonnegative quadratic forms over $X$ naturally correspond to partially specified matrices where all of the fully specified square blocks are PSD, and sums of squares quadratic forms naturally correspond to partially specified matrices which can be completed to a PSD matrix. We show quantitative results on approximation of nonnegative polynomials by sums of squares, which leads to applications in sparse semidefinite programming.
