I am new to linear programming and I'm struggling to formulate a linear program for hyperplane separation:
I came up with two sets of points where the convex hull are not disjoint:
A: {(0,1), (1,2), (2,0)}
B: {(1,1), (3,0), (3,2)}
I want to show that no feasible solution exists by solving a linear program.
I formulated the LP with:
- Objective function: max $\alpha^{T}x$
- s.t.
- $0x_1 + 1x_2 \leq \beta$
- $1x_1 + 2x_2 \leq \beta$
- $2x_1 + 0x_2 \leq \beta$
- $1x_1 + 1x_2 \geq \beta$
- $3x_1 + 0x_2 \geq \beta$
- $3x_1 + 2x_2 \geq \beta$
- $\alpha \neq (0,0)$
Assuming that I formulated the problem correctly, and I wanted to solve this problem by hand using a matrix, would I simply reduce an augmented matrix, such as:
\begin{bmatrix} 0 & 1 & 1\\ 1 & 2 & 1\\ 2 & 0 & 1\\ -3 & 0 & -1\\ -3 & -2 & -1\\ -1 & -1 & -1\\ \end{bmatrix}
..?