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.

Intro
Linear Programming Problem
Motivation
Background Knowledge
State of the art
Semidefinite programming
Block diagonal matrix
Branch bound algorithm
Cardinality constraint formulation
Cardinality constraint reformulation
Cardinality constraint relaxation
Postprocessing
Inequalities
Branching Strategy
Linear Constraints
Heuristics
Initial Set of Centers
Numerical Results
Instances
Results
Branching bound
Conclusion