Solving the 2-Norm K-Hyperplane Clustering Problem via Multi-Norm Formulations

Abstract

We propose a method to solve $k$-HC$_2$—the $k$-Hyperplane Clustering problem that asks to find $k$ hyperplanes that minimize the sum of squared $2$-norm (Euclidean) distances between each point and its closest hyperplane—to global optimality via spatial branch-and-bound (SBB) techniques. Our method strengthens a mixed-integer quadratically constrained quadratic programming formulation for $k$-HC$_2$ with constraints that arise when formulating the problem in $p$-norms with $p \ge 2$. In particular, we show that, for every (suitably scaled) $p \in \mathbb{N} \cup \{\infty\}$, one obtains a variant of $k$-HC$_2$ whose optimal solutions yield lower bounds within a multiplicative approximation factor. We focus on the case of polyhedral norms where $p = 1, \infty$ (which are disjunctive-programming representable), and prove that strengthening the original formulation by including, on top of its $2$-norm constraints, the constraints of one of the polyhedral norms leads to an SBB method where nonzero lower bounds are obtained in a number of nodes that is linear in $n$ and $k$ (rather than exponential). Experimentally, our method leads to very large speedups, reducing median solve times by up to $41\times$ while increasing the total number of solved instances by up to $63\%$, drastically improving the problem's solvability to global optimality.