A simplex-cut method for nearest facets in Minkowski polytopes
Loading...
Files
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of New Brunswick
Abstract
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 [6] 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 [1] for enumeration and cdd [8] for linear programming; gmplib [7] 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.