Criss-Cross Algorithm for Support Vector Machines

Abstract

The Support Vector Machine is a popular family of machine learning models for classification problems. Its goal of finding maximum-margin separating hyperplanes results in a quadratic programming problem. We examine the specific properties of the problem from the perspective of mathematical optimization and whether it can be reformulated as a linear complementarity problem. We also present a new variant of the quadratic criss-cross algorithm of Klafszky and Terlaky adapted to the special structure of the optimization problem of the Support Vector Machine.