Optimization Online


Interior point methods for massive support vector machines

Michael Ferris (ferris***at***cs.wisc.edu)
Todd Munson (tmunson***at***cs.wisc.edu)

Abstract: 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.

Keywords: support vector machine, interior-point method, linear algebra

Category 1: Applications -- Science and Engineering (Data-Mining )

Citation: Data Mining Institute Technical Report 00-05, Computer Sciences Department University of Wisconsin, Madison.

Download: [Postscript]

Entry Submitted: 08/22/2000
Entry Last Modified: 04/18/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society