Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I found very interesting proof by Farkas' lemma Proof of Helly's Theorem but this is doesn't help to answer the questions :( –  pok Nov 26 '11 at 18:55

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you very much, great proof. But why do we actually need restriction. When you showed that the dual is unbounded we can go straightforward to the final inequality, don't we. –  pok Nov 30 '11 at 19:20
    
@pok: We already know that $Ax \leq b$ has no solution, and we're trying to prove that there is some restriction of $Ax \leq b$ to $d+1$ of its rows that has no solution, either. (So we do need a restriction somewhere.) The argument immediately following the claim about the dual being unbounded finds a set of $d+1$ rows that works. –  Mike Spivey Nov 30 '11 at 20:12
    
ok, thanks, understood –  pok Nov 30 '11 at 20:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.