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

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 ̸ = 2. In particular, we show that, for every (suitably scaled) p ∈ N ∪ ∞, 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, ∞ (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 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× while increasing the total number of solved instances by up to 63%, drastically improving the problem's solvability to global optimality. 1 Throughout the paper, we adopt the notation [ξ] := 1, . . . , ξ for every ξ ∈ N. 2 Two norms where 1 p + 1 p ′ = 1 are called dual. The 2-norm is self dual and the 1 and ∞-norms are dual. 3 We report mathematical programming formulations in brackets and optimization problems without them.