Consider two sets of points {(y11, y12),(y21, y22), ...,(yn1, yn2)} and {(z11, z

Question

Consider two sets of points {(y11, y12),(y21, y22), ...,(yn1, yn2)} and {(z11, z12),(z21, z22), ...,(zm1, zm2)} containing n and m points in R2 , respectively.

Assume that it is known that there is a line separating these two sets of points. Formulate the problem of finding one such line. Specify the decision variables, objective function and constraints (example: in the 2-d plane with the horizontal x1-axis and the vertical x2-axis, the line x1 x2 = 1 separates the set of points {(1, 3),(1, 1)} from the set of points {(4, 2),(3, 0),(1, 1)})

Explanation / Answer

Consider a line L in x-y plane (2-d plane) ax+by+c=0

Call L(x,y)=ax+by+c

Points (x0,y0) and (w0,z0) lie on the same side of the line L if L(x0,y0) and L(w0,z0) have same sign (both +ve or both -ve), and they lie on the opposite sides of the line if L(x0,y0) and L(w0,z0) have opposite sign.

Thus, L(yi1,yi2) have same sign for i=1,2,...........,n

which is opposite to the sign of L(zi1,zi2) for i=1,2,..,m

There are following two possibilities.

Case I

a(yi1)+b(yi2)+c > 0 for i=1,......,n

a(zj1)+b(zj2)+c < 0 for j=1,......,m

There exists such a line if we can find a solution of the above system of inequations in a,b,c as variables.

These act as a set of constraints.

Decision variables: a,b,c

Objective function: ax+by+c

Case II

a(yi1)+b(yi2)+c < 0 for i=1,......,n

a(zj1)+b(zj2)+c > 0 for j=1,......,m

There exists such a line if we can find a solution of the above system of inequations in a,b,c as variables.

These act as a set of constraints.

Decision variables: a,b,c

Objective function: ax+by+c

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.