%A O. L. Mangasarian
%T Misclassification Minimization
%D October 1993, Revised April 6, 1994
%R tr1186
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X The problem of minimizing the number of misclassified points by a plane,
attempting to separate two point sets with intersecting convex hulls in
$n$-dimensional real space, is formulated as a linear program with
equilibrium constraints (LPEC). This general LPEC can be converted to an
exact penalty problem with a quadratic objective and linear constraints.
A Frank-Wolfe-type algorithm is proposed for the penalty problem that
terminates at a stationary point or a global solution. Novel aspects of
the approach include: (i) A linear complementarity formulation of the
step function that ``counts'' misclassifications, (ii) Exact penalty
formulation without boundedness, nondegeneracy or constraint qualification
assumptions, (iii) An exact solution extraction from the sequence of
minimizers of the penalty function for a finite value of the penalty parameter
for the general LPEC and an explicitly exact solution for the LPEC with
uncoupled constraints, and (iv) A parametric quadratic programming formulation
of the LPEC associated with the misclassification minimization problem.