**O. L. Mangasarian
olvi@cs.wisc.edu
Computer Sciences Department
University of Wisconsin
Madison, WI 53706
David R. Musicant
dmusican@carleton.edu
Department of Mathematics and Computer Science
Carleton College
Northfield, MN 55057
**

An implicit Lagrangian for the dual of a simple reformulation of the
standard quadratic program of a linear support vector machine is
proposed. This leads to the minimization of an ** unconstrained**
differentiable convex function in a space of dimensionality equal to
the number of classified points. This problem is solvable by an
extremely simple linearly convergent Lagrangian support vector machine
(LSVM) algorithm. LSVM requires the inversion at the outset
of a single matrix of
the order of the much smaller dimensionality of the original input
space plus one. The full algorithm is given in this paper in 11 lines
of MATLAB code without any special optimization tools
such as linear or quadratic programming solvers. This LSVM code
can be used ``as is'' to solve classification problems with
millions of points. For example, 2 million points in 10 dimensional
input space were classified
by a linear surface
in 82 minutes on a Pentium III 500 MHz
notebook with 384 megabytes of memory (and additional swap space), and
in 7 minutes on a 250 MHz UltraSPARC II processor with 2 gigabytes of
memory. Other standard classification test problems were also solved.
Nonlinear kernel classification can also be solved by LSVM. Although
it does not scale up to very large problems, it can handle any
positive semidefinite kernel and is guaranteed to converge. A short
MATLAB code is also given for nonlinear kernels and tested on a number
of problems.

- 1. Introduction
- 2. The Linear Support Vector Machine
- 3. LSVM (Lagrangian Support Vector Machine) Algorithm
- 4. LSVM for Nonlinear Kernels
- 5. Numerical Implementation and Comparisons
- 6. Conclusion
- Acknowledgements
- Bibliography
- About this document ...