Browse Prior Art Database

Use of Linear Programming for Set Separation

IP.com Disclosure Number: IPCOM000085138D
Original Publication Date: 1976-Feb-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Crowder, HP: AUTHOR [+2]

Abstract

Standard linear programming computer routines can be used for determining the linear separability of point sets. A minor modification of the standard technique reduces the work required by a significant factor.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 2

Use of Linear Programming for Set Separation

Standard linear programming computer routines can be used for determining the linear separability of point sets. A minor modification of the standard technique reduces the work required by a significant factor.

The separation of point sets by linear discriminant functions is an important tool in automatic pattern classification. Applications include cluster analysis, optical character recognition, and speech recognition. The point set separation problem can be solved using the simplex method for for linear programming. A variation of the simplex algorithm is introduced which significantly reduces the amount of work required to determine set separability.

Let two point sets P, Q in Euclidean n-space E/n/be given, represented as the m(p) columns {P(j)} and the m(O) columns {Q(k)} of the two matrices P, Q. If the linear separation of P from Q is possible, then there exists an n-vector u such that u/T/P(j) < u/T/Q(k) for all j, k, i.e., such that: z = Min(k) u/T/Q(k) - Max (j) u/T/Pj > 0 (1).

An efficient way to find such u using linear programming is to solve the problem. Minimize z = Sigma/n/(i=1) (v(i) + w(i)) under the constraints:

(Image Omitted)

Associated with each of the n constraints (2) is the dual variable u(i) (i=1,...,n), and with the two constraints (3) the two dual variables s,t . At any stage of the simplex algorithm for solving the above linear programming problem there are at hand numerical values for the dual variables, from which are obtained the reduced costs: d(j) = -Sigma(i)u(i)P(ij) + s, e(k) = Sigma(i)u(i)Q(ik) +
t. (4). AB In the standard application of the simplex method all of these quantities are calculated together, and; Min {d(j), e(k) : all j,k} (5). is determined. If that quantity is negative, the procedure continues, while otherwise the algorithm...