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.

A convergent decomposition algorithm for support vector machines / Lucidi, Stefano; Palagi, Laura; Risi, Arnaldo; Sciandrone, M.. - In: COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. - ISSN 0926-6003. - STAMPA. - 38:2(2007), pp. 217-234. ((Intervento presentato al convegno Conference on Mathematical Methods for Learning (MML-2004) tenutosi a Como, ITALY nel JUN 21-24, 2004 [10.1007/s10589-007-9044-x].

A convergent decomposition algorithm for support vector machines

LUCIDI, Stefano;PALAGI, Laura;RISI, ARNALDO;M. Sciandrone
2007

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.
decomposition methods; large scale optimization; proximal point modification; proximal point modificationj; support vector machine
01 Pubblicazione su rivista::01a Articolo in rivista
A convergent decomposition algorithm for support vector machines / Lucidi, Stefano; Palagi, Laura; Risi, Arnaldo; Sciandrone, M.. - In: COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. - ISSN 0926-6003. - STAMPA. - 38:2(2007), pp. 217-234. ((Intervento presentato al convegno Conference on Mathematical Methods for Learning (MML-2004) tenutosi a Como, ITALY nel JUN 21-24, 2004 [10.1007/s10589-007-9044-x].
File allegati a questo prodotto
File Dimensione Formato  
VE_2007_11573-361513.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 407.41 kB
Formato Adobe PDF
407.41 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/361513
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 25
  • ???jsp.display-item.citation.isi??? 21
social impact