Global Optimization for Cardinality-Constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming

Explore a seminar on global optimization techniques for cardinality-constrained minimum sum-of-squares clustering using semidefinite programming. Delve into the world of unsupervised learning and discover how background knowledge can enhance cluster quality and interpretability in semi-supervised or constrained clustering. Learn about exact algorithms for various MSSC problem variants, including unconstrained MSSC, MSSC with pairwise constraints, and strict cardinality constraints. Understand the application of semidefinite programming tools in solving large-scale clustering problems to global optimality. Examine the numerical results demonstrating the increased capacity to solve larger instances and the state-of-the-art status of this approach. Follow the presentation's structure, covering topics such as linear programming, motivation, background knowledge, semidefinite programming, branch-bound algorithms, cardinality constraint formulations, relaxations, postprocessing, branching strategies, linear constraints, heuristics, and numerical results.