Abstract
In the dual optimization problem behind Support Vector Machine (SVM), each data point corresponds to a decision variable. Therefore, removing data points is equivalent to reducing the dimensionality of the dual problem, leading to a more efficient optimization process. We introduce linear programming models to determine whether two sets of points are linearly separable efficiently, compute the misclassification rate, and reduce the dimension of the optimization problems behind the SVM procedure. Data reduction can be conducted using a simple convexity property for the linearly separable case. The misclassification rate is a key indicator of the complexity of separating the two sets, providing valuable insights into the classification performance. Our approach combines SVM optimization with linear programming techniques to offer a comprehensive classification and complexity analysis framework.