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
- $y'$ is feasible; i.e., $A^T y' = 0$ and $y' \geq 0$;
- $b^T y' < 0$;
- $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.
Weak duality for maximization problems asserts that the if $\mathbf{p}$ is a feasible solution to the dual problem, and $\mathbf{x}$ is a feasible solution to the primal problem, then
$$\mathbf{p}^{T}\mathbf{b} \geq \mathbf{c}^{T}\mathbf{x}.$$
Unfortunately, the classic corollary in this case states that:
- If the optimal cost of the primal problem is unbounded, then the dual is infeasible.
- If the optimal cost of the dual problem is unbounded, then the primal is infeasible.
You want something like the converse of the first statement in the corollary. If you show that the dual is infeasible, then the primal must be unbounded or infeasible by weak duality, and then you just have to show that the primal is feasible.
Best Answer
From weak duality, we know that the dual objective evaluated at $u$ is less than or equal to the primal objective evaluated at $x$. But then we can also consider the "dual of the dual" (i.e. the primal). So we can consider the primal problem to be the dual problem and the dual problem to be the primal problem. So $bu' \geq 0x = 0$ but we know that $bu' <0$ from (ii). Hence both inequalities cannot hold. In other words, if $\textbf{x}$ is feasible for the primal and $\textbf{y}$ is feasible for the dual, then the objective function of the primal evaluated at $\textbf{x}$ is less than or equal to the objective function of the dual evaluated at $\textbf{y}$. So to sum up, the weak duality theorem really has two forms:
If the primal is a minimization problem and $\textbf{x}$ is feasible, then the dual is a maximization problem (and suppose $\textbf{y}$ is feasible for the dual). So from weak duality, the primal evaluated at $\textbf{x}$ will be greater than or equal to the dual evaluated at $\textbf{y}$.
If the primal is a maximization problem and $\textbf{x}$ is feasible then the dual is a minimization problem(and suppose $\textbf{y}$ is feasible for the dual). So from weak duality, the primal evaluated at $\textbf{x}$ will be less than or equal to the dual evaluated at $\textbf{y}$.
In this case, the primal is a maximization problem and the dual is a minimization problem. So the second case holds and hence the result.