[Math] Proving Helly’s theorem

convex-analysislinear programming

The problem is to prove Helly's theorem for the case, when the convex bodies are polytopes, by using linear programming duality.

Helly's theorem

Let $B_{1},…,B_{m}$ be a collection of convex bodies in $\mathbb{R}^{d}$ with $m>d$. If every $d+1$ of these convex bodies have a point in common, then all $m$ of these convex bodies have a point in common.

Ideas for solution

By definition, polytopes is intersection of the half spaces, so intersection of polytopes is intersection of half spaces, therefore we can define inequalities
$Ax<b$. So we get linear programming problem.

In order to prove it, we can take a look at equivalent problem, according to Helly's theorem, $Ax<b$ (intersection of half spaces) doesn't have solution, when any $n+1$ selected inequalities don't have solution.

We should state dual LP problem, which should be feasible and unbounded. Next step is to show that $n + 1
$ nonzero dual variables sufficient for an unbounded solution.

Questions

Unfortunately, I can't figure out what exactly the dual problem will represent? And which objective function should be used? In contradiction to this problem, other usage of duality, in proving minimax theorem, was very clear. We have two LP problem, primal and dual (minimize the loss and maximize the payoff), where objective functions are loss and payoff.

Let's elaborate a little bit

It's primal LP problem

$max \space 0$

$Ax<b$

It's Dual

$min \space b^Ty$

$A^Ty=0$

$y \geq 0$

So now, the problem is prove that the dual LP problem is unbounded using $n+1$ nonzero dual variables.

But constraints in the dual problem is the Homogeneous systems. What we know about homogeneous system,

1) if $u$ and $v$ are two vectors representing solutions to a homogeneous system, then the vector sum $u + v$ is also a solution to the system.

2) If $u$ is a vector representing a solution to a homogeneous system, and $r$ is any scalar, then $ru$ is also a solution to the system.

3) The solution set to a homogeneous system is the same as the null space of the corresponding matrix A.

So may be using $n+1$ feasible solution we can show that there is infinite many basic feasible solutions, therefore the problem can be unbounded. I am sure this doesn't make sense. But I don't have a better explanation.

The second idea, actually by strong duality theorem, if the primal problem is infeasible that the dual problem is unbounded, but in this case, how can I apply $n+1$ nonzero solutions?

Best Answer

We'll prove the equivalent statement that the OP mentioned: If $m$ halfspaces in $\mathbb{R}^d$, $m > d$, do not have a point in common, then there exist some $d+1$ of them that do not have a point in common, either.

If the $m$ halfspaces defined by $Ax \leq b$ do not have a point in common, then that means that the following linear program has no solution:

$\begin{align} \max \text{ } &0 \\ \text{s.t. } &Ax \leq b. \end{align}$

By strong duality, its dual problem is either infeasible or unbounded:

$\begin{align} \min &b^T y \\ \text{s.t. } &A^T y =0, \\ &y \geq 0. \end{align}$

Since $y =0$ is feasible for the dual, though, the dual must be unbounded.

With respect to the simplex method, an unbounded problem means that there exists some basic feasible solution with an entering variable but no leaving variable. Assume, without loss of generality, that $y_1, y_2, \ldots, y_d$ are the basic variables for this basic feasible solution. (There are $d$ of these because the dual has $d$ constraints.) Assume, again without loss of generality, that $y_{d+1}$ is the entering variable for which there is no leaving variable. By increasing the value of $y_{d+1}$ enough we can obtain a solution $y'$ such that

  1. $y'$ is feasible; i.e., $A^T y' = 0$ and $y' \geq 0$;
  2. $b^T y' < 0$;
  3. $y'_{d+2} = y'_{d+3} = \cdots = y'_m = 0$. (This is because these variables remain nonbasic as $y_{d+1}$ is increased.)

Now, let $A^T_D$, $y_D$, and $b_D$ denote the restriction of $A^T$, $y'$, and $b$, respectively, to the variables $y_1, y_2, \ldots, y_{d+1}$. Because of property (3) of $y'$, we have $A^T_D y_D = 0$ and $b^T_D y_D < 0$. Of course, $y_D \geq 0$ as well.

Finally, consider the intersection of $d+1$ halfspaces defined by $A_D x \leq b_D$. If there exists an $x$ in this intersection, then

$\begin{align} & x^T A^T_D \leq b^T_D \\ & \Rightarrow x^T A^T_D y_D \leq b^T_D y_D \\ & \Rightarrow 0 \leq b^T y_D, \end{align}$

which is a contradiction. Therefore, the intersection of $d+1$ halfspaces defined by $A_D x \leq b_D$ is empty, and so we have found a set of $d+1$ of the $m$ halfspaces that do not have a point in common.

Related Question