A single linear program is proposed for discriminating between the elements of k disjoint point sets in the n-dimensional real space R n : When the conical hulls of the k sets are (k ? 1)-point disjoint in R n+1 , a k-piece piecewise-linear surface generated by the linear program completely separates the k sets. This improves on a previous linear programming approach which required that each set be linearly separable from the remaining k ? 1 sets. When the conical hulls of the k sets are not (k ? 1)-point disjoint, the proposed linear program generates an error-minimizing piecewise-linear separator for the k sets. For this case it is shown that the null solution is never a unique solver of the linear program and occurs only under the rather rare condition when the mean of each point set equals the mean of the means of the other k ? 1 sets. This makes the proposed linear computational programming formulation useful for approximately discriminating between k sets that are not piecewise-linear separable. Computational results are reported for three previously available databases.
As it is reported in [6] and noted in REF , when the set of R n points are not 'piecewise linear separable' the method exhibits poor results.
Multicategory Discrimination via Linear Programming
Optimization Methods and Software
Mathematics