%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.