Abstract | ||
---|---|---|
In this work, we consider the convex quadratic programming problem arising in support vector machine (SVM), which is a technique designed to solve a variety of learning and pattern recognition problems. Since the Hessian matrix is dense and real applications lead to large-scale problems, several decomposition methods have been proposed, which split the original problem into a sequence of smaller subproblems. SVMlight algorithm is a commonly used decomposition method for SVM, and its convergence has been proved only recently under a suitable block-wise convexity assumption on the objective function. In SVMlight algorithm, the size q of the working set, i.e. the dimension of the subproblem, can be any even number. In the present paper, we propose a decomposition method on the basis of a proximal point modification of the subproblem and the basis of a working set selection rule that includes, as a particular case, the one used by the SVMlight algorithm. We establish the asymptotic convergence of the method, for any size q greater than or equal to 2 of the working set, and without requiring any further block-wise convexity assumption on the objective function. Furthermore, we show that the algorithm satisfies in a finite number of iterations a stopping criterion based on the violation of the optimality conditions. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1080/10556780512331318209 | OPTIMIZATION METHODS & SOFTWARE |
Keywords | DocType | Volume |
support vector machines,SVMlight algorithm,decomposition methods,proximal point | Journal | 20 |
Issue | ISSN | Citations |
2-3 | 1055-6788 | 6 |
PageRank | References | Authors |
0.50 | 3 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
L. Palagi | 1 | 46 | 5.24 |
M. Sciandrone | 2 | 335 | 29.01 |