Optimization Online


Semismooth Support Vector Machines

Michael C Ferris (ferris***at***cs.wisc.edu)
Todd S Munson (tmunson***at***mcs.anl.gov)

Abstract: The linear support vector machine can be posed as a quadratic program in a variety of ways. In this paper, we look at a formulation using the two-norm for the misclassification error that leads to a positive definite quadratic program with a single equality constraint when the Wolfe dual is taken. The quadratic term is a small rank update to a positive definite 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. Significant computational savings are realized as the inactive variables are identified and exploited during the solution process. Results for a 60 million variable problem are presented, demonstrating the effectiveness of the proposed method on a personal computer.

Keywords: data mining, semismooth method, convergence

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

Category 2: Complementarity and Variational Inequalities

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

Download: [Postscript][PDF]

Entry Submitted: 11/30/2000
Entry Accepted: 11/30/2000
Entry Last Modified: 11/30/2000

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