Operations Research Letters
A zonotope-based reformulation for quadratic optimization over roots of unity
Ahmad Al-Sulami, Hamza Fawzi, Shengding Sun
Abstract
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. In this paper, we construct an integer binary reformulation of the problem based on zonotopes. Compared to the standard reformulation, the number of binary variables is reduced by half or even m . ealWe also provide, with the help of tools from number theory, lower bounds on the number of variables in a real binary reformulation when m is an odd prime or a power of 2. We show on numerical experiments that zonotope reformulation can result in one order of magnitude speedup in solution time.