Intersection of convex hulls 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?
 A: 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).
