Solving the 2-norm k-hyperplane clustering problem via multi-norm formulations

We tackle the 2-norm (Euclidean) k-Hyperplane Clustering problem (k-HC2), which asks for finding k hyperplanes that minimize the sum of squared 2-norm (Euclidean) distances between each point and its closest hyperplane. We solve the problem to global optimality via spatial branch-and-bound techniques (SBB) by strengthening a mixed integer quadratically-constrained quadratic programming formulation with constraints that arise when formulating the problem in p-norms with p ̸= 2. In particular, we show that, for every (appropriately scaled) p ∈ N ∪ {∞}, one obtains a variant of k-HC2 whose optimal solutions yield lower bounds within a multiplicative approximation factor. We focus on the case of polyhedral norms where p = 1, ∞ (which admit a disjunctive-programming reformulation), and prove that strengthening the original formulation by including, on top of the original 2-norm constraints, the constraints of one of the polyhedral-norms leads to an SBB method where nonzero lower bounds are obtained in a linear (as opposed to exponential) number of SBB nodes. Experimentally, we show that our strengthened formulations lead to speedups from 41 to 1.5 orders of magnitude, drastically improving the problem’s solvability to global optimality.