A convergent decomposition algorithm for support vector machines |
| |
Authors: | S. Lucidi L. Palagi A. Risi M. Sciandrone |
| |
Affiliation: | (1) Dipartimento di Informatica e Sistemistica “Antonio Ruberti”, Università di Roma “La Sapienza”, Via Buonarroti 12, 00185 Roma, Italy;(2) Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti”, Consiglio Nazionale delle Ricerche, Viale Manzoni 30, 00185 Roma, Italy;(3) Dipartimento di Sistemi e Informatica, Università di Firenze, Via di S.ta Marta 3, 50139 Firenze, Italy |
| |
Abstract: | In this work we consider nonlinear minimization problems with a single linear equality constraint and box constraints. In particular we are interested in solving problems where the number of variables is so huge that traditional optimization methods cannot be directly applied. Many interesting real world problems lead to the solution of large scale constrained problems with this structure. For example, the special subclass of problems with convex quadratic objective function plays a fundamental role in the training of Support Vector Machine, which is a technique for machine learning problems. For this particular subclass of convex quadratic problem, some convergent decomposition methods, based on the solution of a sequence of smaller subproblems, have been proposed. In this paper we define a new globally convergent decomposition algorithm that differs from the previous methods in the rule for the choice of the subproblem variables and in the presence of a proximal point modification in the objective function of the subproblems. In particular, the new rule for sequentially selecting the subproblems appears to be suited to tackle large scale problems, while the introduction of the proximal point term allows us to ensure the global convergence of the algorithm for the general case of nonconvex objective function. Furthermore, we report some preliminary numerical results on support vector classification problems with up to 100 thousands variables. |
| |
Keywords: | Large scale optimization Decomposition methods Proximal point modification Support vector machine |
本文献已被 SpringerLink 等数据库收录! |
|