Abstract: Quadratic programming (QP) problem reformulation has been a research problem for nearly two decades, but is seldom linked to Graph Theory. In fact, typical reformulations convexify a non-convex QP problem. This is accomplished by making the objective function differentiable, optimizing in the continuous domain while ensuring the final solution is binary, or adding regularizers and Lagrangian coefficients to optimize the dual problem. In this research, we demonstrate that QP problems can also be reformulated using the same mechanism as P/NP problem reduction, overcoming speed and memory footprint limitations from other type of reformulation. We use SVM to make the demonstration. In the demonstration, we show that SVM is comparable to a soft weighted edge maximum independent set problem where the amount of support vectors per class is balanced. As a result, SVM can also be reformulated as a maximum clique problem with the same class balancing constraint. After transforming the sequential minimal optimization (SMO) algorithm to our new maximum clique formulation, we demonstrate that such reformulation leads to improved training performance, reaching 36 times faster training time, and a sparser solution for less than one percent accuracy degradation in some datasets.

Index Terms: Quadratic Optimization, Classification algorithms, Support Vector Machines, Graph Theory, Independent Set, Maximum Weighted Clique.