On the convergence of a modified version of SVMlightalgorithm

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, that split the original problem into a sequence of smaller subproblems. SVM light 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 SVM light 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 based on a proximal point modification of the subproblem and on a working set selection rule that includes, as a particular case, the one used by the SVM light algorithm. We establish the asymptotic convergence of the method, for any size q ≥ 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.