Analysis of programming properties and the row-column generation method for 1-norm support vector machines

作者：Zhang Li^*; Zhou WeiDa

来源：Neural Networks, 2013, 48: 32-43.

DOI：10.1016/j.neunet.2013.07.005

• 1-norm SVM
• Linear programming
• Column generation
• Row-column generation
• Sparse constraints

This paper deals with fast methods for training a 1-norm support vector machine (SVM). First, we define a specific class of linear programming with many sparse constraints, i.e., row-column sparse constraint linear programming (RCSC-LP). In nature, the 1-norm SVM is a sort of RCSC-LP. In order to construct subproblems for RCSC-LP and solve them, a family of row-column generation (RCG) methods is introduced. RCG methods belong to a category of decomposition techniques, and perform row and column generations in a parallel fashion. Specially, for the 1-norm SVM, the maximum size of subproblems of RCG is identical with the number of Support Vectors (SVs). We also introduce a semi-deleting rule for RCG methods and prove the convergence of RCG methods when using the semi-deleting rule. Experimental results on toy data and real-world datasets illustrate that it is efficient to use RCG to train the 1-norm SVM, especially in the case of small SVs.

• 出版日期2013-12
• 单位苏州大学