An Exact Algorithm for Semi-Supervised Support Vector Machines using Strong SDP Bounds

Support vector machines (SVMs) are well-studied supervised learning models for binary classification. They have proven to be powerful machine learning techniques, and efficient algorithms exist to solve the underlying optimization problems. However, most data in real life is unclassified, leading to semi-supervised support vector machines (S3VMs) instead. State-of-the-art MIP and MINLP solvers can only solve small S3VM instances to optimality. In this talk, we present a new branch-and-cut approach for S3VMs using semidefinite programming (SDP) relaxations. We first apply optimality-based bound tightening to bound the feasible set. Then, at each branch-and-bound node, we strengthen the SDPs by adding RLT cuts and applying bound tightening techniques. We provide numerical results showing that our approach is capable of producing very small duality gaps for real-world instances. Moreover, we solve S3VM instances with ten times more data points to optimality than was possible before.