A framework for quadratic form maximization over convex sets through nonconvex relaxations

We investigate the approximability of the following optimization problem. The input is an 𝑛 × 𝑛 matrix 𝐴 = (𝐴 𝑖 𝑗 ) with real entries and an origin-symmetric convex body 𝐾 ⊆ R 𝑛 that is given by a membership oracle. The task is to compute (or approximate) the maximum of the quadratic form 𝑛 𝑖=1 𝑛 𝑗=1 𝐴 𝑖 𝑗 𝑥 𝑖 𝑥 𝑗 = ⟨𝑥, 𝐴𝑥⟩ as 𝑥 ranges over 𝐾. This is a rich and expressive family of optimization problems; for different choices of matrices 𝐴 and convex bodies 𝐾 it includes a diverse range of optimization problems like max-cut, Grothendieck/non-commutative Grothendieck inequalities, small set expansion and more. While the literature studied these special cases using case-specific reasoning, here we develop a general methodology for treatment of the approximability and inapproximability aspects of these questions.

The underlying geometry of 𝐾 plays a critical role; we show under commonly used complexity assumptions that polytime constantapproximability necessitates that 𝐾 has type-2 constant that grows slowly with 𝑛. However, we show that even when the type-2 constant is bounded, this problem sometimes exhibits strong hardness of approximation. Thus, even within the realm of type-2 bodies, the approximability landscape is nuanced and subtle.

However, the link that we establish between optimization and geometry of Banach spaces allows us to devise a generic algorithmic approach to the above problem. We associate to each convex body a new (higher dimensional) auxiliary set that is not convex, but is approximately convex when 𝐾 has a bounded type-2 constant. If our auxiliary set has an approximate separation oracle, then we design an approximation algorithm for the original quadratic optimization problem, using an approximate version of the ellipsoid method. Even though our hardness result implies that such an oracle does not exist in general, this new question can be solved in specific cases of interest by implementing a range of classical tools from functional analysis, most notably the deep factorization theory of linear operators.

Beyond encompassing the scenarios in the literature for which constant-factor approximation algorithms were found, our generic framework implies that that for convex sets with bounded type-2