betaFeedback

WorksMathematics

Optimality Guarantees for Minimum Variance Subset Selection via Semidefinite Programming

Abstract

Given a set of data points in Euclidean space and a prescribed cardinality kk, the minimum variance kk-subset problem asks for kk points minimizing their average squared distance from their centroid. We develop a semidefinite programming (SDP) framework for exact recovery and global optimization. First, we show that the natural SDP relaxation fails Slater's condition. Identifying the proper face containing its feasible region yields an equivalent, lower-dimensional, strictly feasible formulation that enjoys strong duality. A primal–dual characterization of optimality then gives geometric necessary and sufficient conditions under which the SDP relaxation is guaranteed to be tight. These conditions reveal how tightness depends on the internal geometry of the selected subset and on its separation from the remaining points. Second, we embed the SDP relaxation in a branch-and-cut algorithm combining first-order optimization, valid inequalities and dimension-reducing branching. Extensive experiments on public data sets, with up to 1,500 points and different values of kk, show that the method strongly outperforms general-purpose exact solvers as the number of points and cardinality increase.

Paper details

vlnc:W_xyner57r
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…