标题： 单位根上的二次优化的精确算法 显示英文标题

标题： Exact algorithms for quadratic optimization over roots of unity

摘要： 我们考虑优化一个多元二次函数的问题，其中每个决策变量被限制为复数$m$次单位根。 此类问题在信号处理、MIMO检测以及统计物理中基态的计算等方面有应用。 本文的贡献有两个方面。 我们首先研究了平方和层次结构的收敛性，并证明在仅经过$\lfloor n/2\rfloor+1$层后即可收敛到精确解（而不是$n$层）。 我们的证明遵循并推广了Fawzi、Saunderson、Parrilo为二进制$m=2$情况开发的技术和结果。 其次，我们基于平行六面体构建了一个整数二进制重写形式，这将简单重写中的二进制变量数量减少了一半。 我们在数值实验中展示了这种重写可以显著加快求解速度（最高达10倍）。 显示英文摘要

摘要： We consider the problem of optimizing a multivariate quadratic function where each decision variable is constrained to be a complex $m$'th root of unity. Such problems have applications in signal processing, MIMO detection, and the computation of ground states in statistical physics, among others. Our contributions in this paper are twofold. We first study the convergence of the sum-of-squares hierarchy and prove its convergence to the exact solution after only $\lfloor n/2\rfloor+1$ levels (as opposed to $n$ levels). Our proof follows and generalizes the techniques and results used for the binary $m=2$ case developed by Fawzi, Saunderson, Parrilo. Second, we construct an integer binary reformulation of the problem based on zonotopes which reduces by half the number of binary variables in the simple reformulation. We show on numerical experiments that this reformulation can result in significant speedups (up to 10x) in solution time.