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.
Citation
Data Mining Institute Technical Report 00-05, Computer Sciences Department University of Wisconsin, Madison.