论文标题
更快的内点方法优化总和
A Faster Interior-Point Method for Sum-of-Squares Optimization
论文作者
论文摘要
我们提出了一种更快的内点方法，用于优化平方总和（SOS）多项式，该方法是多项式优化的中心工具，并捕获了Lasserre层次结构中的凸面编程。令$ p = \ sum_i q^2_i $为$ n $ - Variate SOS多项式$ 2D $。用$ l：= \ binom {n+d} {d} $和$ u：= \ binom {n+2d} {2d} {2d} $分别为$ q_i $'s和$ p $ live的向量空间的尺寸，我们的algorithms live，我们的algorithms $ $ \ tilde $。这比最先进的SOS和半决赛编程求解器更快，该求解器可实现运行时$ \ tilde {o}（l^{0.5} \ min \ min \ {u^{2.37}，l^{4.24} \} \} \}）$。 我们算法的核心是一种动态数据结构，用于在多项式插值基础下维持SOS屏障函数的Hessian的倒数，该基础有效地扩展到多元SOS优化，并需要维持与元素对元素的低率元素（hastamard）产物的光谱近似。这是与最近使用倒数的IPM突破的主要挑战，也是倒数的突破，在此，对于Hessian Matrix来说，对Slack Matrix的低排名更新很容易暗示相同。
We present a faster interior-point method for optimizing sum-of-squares (SOS) polynomials, which are a central tool in polynomial optimization and capture convex programming in the Lasserre hierarchy. Let $p = \sum_i q^2_i$ be an $n$-variate SOS polynomial of degree $2d$. Denoting by $L := \binom{n+d}{d}$ and $U := \binom{n+2d}{2d}$ the dimensions of the vector spaces in which $q_i$'s and $p$ live respectively, our algorithm runs in time $\tilde{O}(LU^{1.87})$. This is polynomially faster than state-of-art SOS and semidefinite programming solvers, which achieve runtime $\tilde{O}(L^{0.5}\min\{U^{2.37}, L^{4.24}\})$. The centerpiece of our algorithm is a dynamic data structure for maintaining the inverse of the Hessian of the SOS barrier function under the polynomial interpolant basis, which efficiently extends to multivariate SOS optimization, and requires maintaining spectral approximations to low-rank perturbations of elementwise (Hadamard) products. This is the main challenge and departure from recent IPM breakthroughs using inverse-maintenance, where low-rank updates to the slack matrix readily imply the same for the Hessian matrix.
