I have two polyhedral sets $\mathscr{P}_1, \mathscr{P}_2,$ defined as convex hulls
$$\mathscr{P}_1 = \mbox{conv} \left\{ v_{1},\dots, v_{N} \right\}, \qquad \mathscr{P}_2 = \mbox{conv} \left\{ w_{1},\dots,w_{M} \right\}$$
If $\mathscr{P}_1 \bigcap \mathscr{P}_2 \neq \emptyset$, then there is a point that is in convex hull $v_{1},\dots, v_{N}$ and in convex hull $w_{1},\dots, w_{N}$. I have to find this point by using linear programming. Can you please help me with that?
If these two sets intersect, then there must be a point $\vec p \in \mathscr{P}_1 \cap \mathscr{P}_2$, representable as a convex combination of both the set of points $\{\vec v_1,\ldots,\vec v_N \}$ and the set of points $\{\vec w_1,\ldots,\vec v_M\}$. Let's denote a vector of coefficients, participating in these combinations, as:
$$\vec \alpha = (\alpha_1,\ldots,\alpha_N,\alpha_{N+1},\ldots,\alpha_{N+M}) \in \mathbb R^{N+M}$$
We can express the point $\vec p$ as either of two vector sums below:
$$\vec p = \sum_{i=1}^N \alpha_i \vec v_i = \sum_{j=N+1}^{N+M} \alpha_j \vec w_j $$
The components of the vector $\vec \alpha$ must also satisfy two scalar equations:
$$\sum_{i=1}^N \alpha_i = 1,\sum_{j=N+1}^{N+M} \alpha_j = 1$$
We can represent three equations above in the matrix form:
$$A\vec\alpha = b$$
where the matrix $A$ contains $(d+2)$ rows and $(N+M)$ columns, and the vector $b$ contains $(d+2)$ elements ($d$ - the number of dimensions of the vector space, containing points $v_i$ and $w_j$):
$$ A = \begin{bmatrix} \vec v_1 \cdots \vec v_N & -\vec w_1 \cdots -\vec w_M \\ 1 \cdots 1 & 0 \cdots 0 \\ 0 \cdots 0 & 1 \cdots 1 \end{bmatrix}, b = \begin{bmatrix} \vec 0 \\ 1 \\ 1 \end{bmatrix} $$
If this system of linear equations above has a solution $\vec \alpha \ge 0$ (the non-negativity is necessary for the convex combination), then two sets $\mathscr{P}_1$ and $\mathscr{P}_2$ have a non-empty intersection.
It's convenient to use the Farkas' lemma to determine the solvability of the system above. According to this lemma, the existence of the vector $\vec\beta$, such that inequalities below are satisfied:
$$ b^T\vec\beta < 0 \\ A^T\vec\beta \ge 0 $$
guarantees, that the matrix equation $A\vec\alpha = b$ doesn't have a solution $\vec\alpha \ge 0$. Also, the matrix inequality $A^T\vec\beta \ge 0$ always has a solution $\vec\beta=0$. So, we just need to start from this initial solution and try to minimize the value of the scalar product $b^T\vec\beta$. As soon as we find a vector $\vec\beta$, such that this scalar product is negative, we can conclude, that the original matrix equation is not solvable (no intersection). If we get stuck on the solution $\vec\beta=0$, then the matrix equation is solvable (the intersection is not empty).
EXAMPLE. Let's consider two segments on the plane, i.e. $d=n=M=2$.
$$ \vec v_1=(v_{1x},v_{1y}),\vec v_2=(v_{2x},v_{2y}), \vec w_1=(w_{1x},w_{1y}),\vec w_2=(w_{2x},w_{2y}) $$
The (dual) Linear Programming problem will become:
$$b^T\vec\beta = \beta_3 + \beta_4 \to min$$
subject to constraints $A^T\vec\beta \ge 0$:
$$ \begin{bmatrix} v_{1x} & v_{1y} & 1 & 0 \\ v_{2x} & v_{2y} & 1 & 0 \\ -w_{1x} & -w_{1y} & 0 & 1 \\ -w_{2x} & -w_{2y} & 0 & 1 \end{bmatrix} \begin{bmatrix} \beta_1 \\ \beta_2 \\ \beta_3 \\ \beta_4 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$
The case, when two segments intersect:
$$\vec v_1=(1,1),\vec v_2=(2,2),\vec w_1=(2,1),\vec w_2=(1,2)$$
We get a system of inequalities:
$$ \left\{ \begin{aligned} \beta_1 + \beta_2 + \beta_3 \ge 0 \\ 2\beta_1 + 2\beta_2 + \beta_3 \ge 0 \\ -2\beta_1 - \beta_2 + \beta_4 \ge 0 \\ -\beta_1 - 2\beta_2 + \beta_4 \ge 0 \end{aligned} \right. $$
Let's add these four inequalities:
$$2(\beta_3 + \beta_4) \ge 0$$
Therefore, the objective function can't be negative, and we conclude, that two segments $conv\{\vec v_1,\vec v_2\}$ and $conv\{\vec w_1,\vec w_2\}$ do intersect (which is obvious, if you draw them).
The case, when two segments don't intersect:
$$\vec v_1=(2,2),\vec v_2=(3,3),\vec w_1=(2,1),\vec w_2=(1,2)$$
We get a system of inequalities:
$$ \left\{ \begin{aligned} 2\beta_1 + 2\beta_2 + \beta_3 \ge 0 \\ 3\beta_1 + 3\beta_2 + \beta_3 \ge 0 \\ -2\beta_1 - \beta_2 + \beta_4 \ge 0 \\ -\beta_1 - 2\beta_2 + \beta_4 \ge 0 \end{aligned} \right. $$
It's easy to see that the vector $\vec\beta = (1,1,-4,3)$ is a solution of the system above, and the objective function value is negative on this vector (actually this value can be made a negative infinity). Therefore we can conclude, that two segments $conv\{\vec v_1,\vec v_2\}$ and $conv\{\vec w_1,\vec w_2\}$ don't intersect (again, it's obvious if to draw them).