Facial Reduction for the SDP Relaxation of the Maximum $k$-Cluster Problem
A standard technique for bounding combinatorial optimization problems is to obtain a semidefinite relaxation by ``lifting'' the problem into a higher dimensional space of symmetric matrices. For some combinatorial problems such as the maximum $k$-cluster, the resulting SDP relaxation is not strictly feasible. In the context of the maximum $k$-cluster problem, we present an equivalent strictly feasible SDP relaxation by way of the dimensionality reduction technique known as facial reduction. We then present a recipe to form this strictly feasible SDP relaxation directly from the original problem.