Dual Column Generation Scheme

In many real-world applications, Support Vector Machines (SVM) have proven to be an attractive and easy-to-handle technique for solving classification problems, requiring only a small number of parameters and producing solutions with few classification errors. In the linear case, the method generates a separating hyperplane by solving an optimization problem whose computational time does, however, increase more than linearly as the number of objects to be classified grows. This characteristic eventually becomes a drawback as the classification problem gets larger. For such cases, this paper presents an alternative in the form of a column generation scheme that finds an epsilon-optimal solution for the linear formulation of SVM problem. Different approaches are evaluated for selecting both the initial column set and the columns to be added at each iteration. Extensive computational experimentation was conducted on more than 100 data sets ranging in size from 200 to 5,000,000 objects, some drawn from the literature and others artificially generated.