Semismooth Support Vector Machines
Abstract
The linear support vector machine can be posed as a quadratic pro-
gram in a variety of ways. In this paper, we look at a formulation using
the two-norm for the misclassi cation error that leads to a positive de -
nite quadratic program with a single equality constraint when the Wolfe
dual is taken. The quadratic term is a small rank update to a positive def-
inite matrix. We reformulate the optimality conditions as a semismooth
system of equations using the Fischer-Burmeister function and apply a
damped Newton method to solve the resulting problem. The algorithm
is shown to converge from any starting point with a Q-quadratic rate of
convergence. At each iteration, we use the Sherman-Morrison-Woodbury
update formula to solve a single linear system of equations. Signi cant
computational savings are realized as the inactive variables are identi ed
and exploited during the solution process. Results for a 60 million variable
problem are presented, demonstrating the e ectiveness of the proposed
method on a personal computer.
Subject
support vector machines
Permanent Link
http://digital.library.wisc.edu/1793/64292Citation
00-09