%A Michael C. Ferris
%A Todd S. Munson
%T Interior Point Methods for Massive Support Vector Machines
%D May 2000
%R 00-05
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X
We investigate the use of interior point methods for solving quadratic
programming problems with a small number of linear constraints where
the quadratic term consists of a low-rank update to a positive
semi-definite matrix. Several formulations of the support vector
machine fit into this category. An interesting feature of these
particular problems is the volume of data, which can lead to quadratic
programs with between 10 and 100 million variables and a dense $Q$
matrix. We use OOQP, an object-oriented interior point code, to solve
these problem because it allows us to easily tailor the required
linear algebra to the application. Our linear algebra implementation
uses a proximal point modification to the underlying algorithm, and
exploits the Sherman-Morrison-Woodbury formula and the Schur
complement to facilitate efficient linear system solution. Since we
target massive problems, the data is stored out-of-core and we overlap
computation and I/O to reduce overhead. Results are reported for
several linear support vector machine formulations demonstrating the
reliability and scalability of the method.