论文标题
二进制多项式优化的平方总和层次结构
Sum-of-squares hierarchies for binary polynomial optimization
论文作者
论文摘要
我们考虑了在布尔hyperean hyperemypube $ \ mathbb {b}^{n} = \ {0,1 \}^n $上最小化多项式$ f $的问题的近似值。 This hierarchy provides for each integer $r \in \mathbb{N}$ a lower bound $f_{(r)}$ on the minimum $f_{\min}$ of $f$, given by the largest scalar $λ$ for which the polynomial $f - λ$ is a sum-of-squares on $\mathbb{B}^{n}$ with degree at most $ 2R $。我们通过估算最坏情况的错误$ f _ {\ min} - f _ {（r）} $来分析这些边界的质量。结果，对于[0，1/2] $中的固定$ t \，我们可以证明该制度$ r \ cd t \ cdot n $在$ 1/2- \ sqrt {t（1-t）} $中的订单趋于$ n $倾向于$ \ infty $。我们的证明结合了$ \ mathbb {b}^{n} $的经典傅立叶分析与多项式内核技术和krawtchouk多项式极端根的现有结果。与正交多项式根部的链接依赖于下限$ f _ {（r）} $的层次结构与上限$ f^{（r）} $之间的连接，我们也能够建立相同的错误分析。我们的分析扩展到多项式对$ q $ -ary cube $（\ mathbb {z}/q \ mathbb {z}）^{n} $的最小化。
We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial $f$ over the boolean hypercube $\mathbb{B}^{n}=\{0,1\}^n$. This hierarchy provides for each integer $r \in \mathbb{N}$ a lower bound $f_{(r)}$ on the minimum $f_{\min}$ of $f$, given by the largest scalar $λ$ for which the polynomial $f - λ$ is a sum-of-squares on $\mathbb{B}^{n}$ with degree at most $2r$. We analyze the quality of these bounds by estimating the worst-case error $f_{\min} - f_{(r)}$ in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed $t \in [0, 1/2]$, we can show that this worst-case error in the regime $r \approx t \cdot n$ is of the order $1/2 - \sqrt{t(1-t)}$ as $n$ tends to $\infty$. Our proof combines classical Fourier analysis on $\mathbb{B}^{n}$ with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds $f_{(r)}$ and another hierarchy of upper bounds $f^{(r)}$, for which we are also able to establish the same error analysis. Our analysis extends to the minimization of a polynomial over the $q$-ary cube $(\mathbb{Z}/q\mathbb{Z})^{n}$.
