论文标题
在非负轨道上进行多项式优化的凸松弛的易于处理的层次结构
Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant
论文作者
论文摘要
我们考虑在非负轨道中包含的半格式集中的多项式优化问题（POP）（紧凑型集合上的每个POP都可以通过对Origin的简单翻译来以这种格式放置）。通过将每个变量平行，可以将这样的POP转换为等效的POP。使用偶数对称性和因子宽度的概念，我们根据Dickinson-Povh提出了基于Pólya的Potitivstellensatz的扩展，提出了半决赛松弛的层次结构。作为其显着特征和至关重要的特征，可以任意选择每个结果的半芬矿放松的最大矩阵大小，此外，我们证明，新层次结构返回的值返回的值顺序会收敛到原始POP以速率$ o（\ varepsilon^{ - c}）$ interment interment interment interment interment interment interment interment intermiory interiory。当应用于（i）多层神经网络的鲁棒性认证以及（ii）正值最大奇异值的计算时，我们基于Pólya的Potitivstellensatz的方法可提供更好的界限，并比标准瞬间SOS SOS层次制度更快地运行了几百倍。
We consider polynomial optimization problems (POP) on a semialgebraic set contained in the nonnegative orthant (every POP on a compact set can be put in this format by a simple translation of the origin). Such a POP can be converted to an equivalent POP by squaring each variable. Using even symmetry and the concept of factor width, we propose a hierarchy of semidefinite relaxations based on the extension of Pólya's Positivstellensatz by Dickinson-Povh. As its distinguishing and crucial feature, the maximal matrix size of each resulting semidefinite relaxation can be chosen arbitrarily and in addition, we prove that the sequence of values returned by the new hierarchy converges to the optimal value of the original POP at the rate $O(\varepsilon^{-c})$ if the semialgebraic set has nonempty interior. When applied to (i) robustness certification of multi-layer neural networks and (ii) computation of positive maximal singular values, our method based on Pólya's Positivstellensatz provides better bounds and runs several hundred times faster than the standard Moment-SOS hierarchy.
