A simplex-cut method for nearest facets in Minkowski polytopes
University of New Brunswick
The Support Vector Machine algorithms are well known machine learning algorithms focused on classification and regression. The main idea of an SVM problem is to find a function to separate two data sets with a maximum margin. In this thesis, we focus on solving the linear SVM problem where the training sets cannot be separated by a linear function. We follow Cui’s thesis  which converts the problem into a Minkowski Norm Minimization problem. We first introduce the basic formulation of SVM problem and some theory. We also briefly introduce Cui’s geometric framework and show how the SVM problem can be view geometrically. In order to solve the Minkowski Norm Minimization problem, we propose to algorithms two trim the polytope. The implementation uses lrs  for enumeration and cdd  for linear programming; gmplib  is used for multi-precision calculation. The results of the experiments show that our methods have better performance than brute-force enumeration and that the cutting polytope method has better performance than cutting planes.