%A O. L. Mangasarian
%T Machine Learning via Polyhedral Concave Minimization
%D November 1995
%R 95-20
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X Two fundamental problems of machine learning, misclassification
minimization and feature selection, are formulated as the minimization
of a concave function on a polyhedral set. Other formulations
of these problems utilize linear programs with equilibrium
constraints which are generally intractable.
In contrast, for the proposed concave minimization formulation, a
successive linearization algorithm without stepsize terminates after a maximum
average of 7 linear programs on problems with as many as 2124 points in
2082-dimensional space. The algorithm terminates at a stationary point or a
global solution to the problem. Preliminary numerical results indicate
that the proposed approach is quite effective and more efficient than
other approaches.