%A O. L. Mangasarian
%T Pattern recognition via linear programming :theory and application to medical diagnosis
%D 1989
%R 878
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X
A decision problem associated with a fundamental nonconvex model for
linearly inseparable pattern sets is shown to be NP-complete.
Another nonconvex model that employs an $\infty - $ norm instead
of the $2$-nor m, can be solved in polynomial time by solving $2n$
linear programs, where $n$ is t he (usually small) dimensionality
of the pattern space. An effective LP-based finite algorithm is
proposed for solving the latter model. The algorithm is employed
to obtain a nonconvex piecewise-linear function for se parating points
representing measurements made on fine needle aspirates taken from
benign and malignant human breasts. A computer program trained on 369
samples has correctly diagnosed each of 45 new samples encountered
and is currently in use at the University of Wisconsin Hospitals.