Theorem of the Alternative
Table of Contents
We can apply duality theory of linear programs to prove statements that don’t mention linear programming at all! Here’s an example. Notice that the statement of the theorem doesn’t mention maximizing or minimizing at all, just linear inequalities.
(of the Alternative) Let \(A\) be an \(m \times n\) matrix and \(\mathbf{b}\) be a vector with \(m\) entries. Either there exists a vector \(\mathbf{x}\) such that \(A \mathbf{x} \le \mathbf{b}\) and \(\mathbf{x} \ge 0\), or there exists a vector \(\mathbf{y}\) such that \(A^\top \mathbf{y} \ge 0\), \(\mathbf{y} \ge 0\) and \(\mathbf{b} \cdot \mathbf{y} < 0\), but not both.
Since the alternatives both are reminiscent of LPs, let’s try to build up a primal-dual pair based on the alternatives we’re aiming for. First of all, \( A \mathbf{x} \le \mathbf{b} \) and \( \mathbf{x} \ge 0\) definitely look like primal constraints; \( A^\top \mathbf{y} \ge 0 \) and \( \mathbf{y} \ge 0\) look like dual constraints. Now, what to do with \(\mathbf{b} \cdot \mathbf{y} < 0\)? Despite being an inequality, it doesn’t look too much like a constraint: it says something is strictly less than zero and our constraints usually include the possibility of equality; also, the dot product looks more like an objective function for the dual. So let’s try \(\mathbf{b} \cdot \mathbf{y}\) as the dual objective function and deal with the “\(< 0\)” part later, in the course of the proof.
The only thing left to decide is what the objective function of the primal should be, but having the dual complete, we can just remember that the primal is the dual of the dual, and since the main constraint of the dual is \(A^\top \mathbf{y} \ge 0\), the primal objective function must be \(0 \cdot \mathbf{x}\). The finished pair looks like this:
| Primal LP | Dual LP |
|---|---|
| max \(0 \cdot \mathbf{x}\) | min \(\mathbf{b} \cdot \mathbf{y}\) |
| subject to | subject to |
| \( A \mathbf{x} \le \mathbf{b} \) | \( A^\top \mathbf{y} \ge 0 \) |
| \( \mathbf{x} \ge 0\) | \( \mathbf{y} \ge 0\) |
In terms of these LPs, the theorem we are trying to prove can be expressed as follows:
Either the primal is feasible, or the dual has a feasible solution with negative objective function, but not both.
Let’s see what’s special about these LPs:
- Since the objective function of the primal is the constant zero, the primal can’t possibly be unbounded.
- The dual is automatically feasible! Indeed, taking \(\mathbf{y} = 0\) we can satisfy both constraints in the dual.
So the primal can only be infeasible or have an optimal solution, while the dual can only be unbounded or have an optimal solution. Which combinations are possible? By strong duality, if either one has an optimal solution, then both do. So the only cases are:
- Both primal and dual have optimal solutions:
- In particular the primal is feasible, which is the first of the alternatives we were aiming for.
- The primal is infeasible and the dual is unbounded:
- In this case the dual has a family of feasible solutions with objective function tending1 to \(-\infty\). In particular, the dual must have feasible solutions with \(\mathbf{b} \cdot \mathbf{y} < 0\). So in this case, the second alternative holds.
We still need to show that both alternatives can’t happen at the same time, but that’s just from weak duality: \(\mathbf{x}\) would be feasible for the primal, \(\mathbf{y}\) would be feasible for the dual, but then weak duality would tell us that \(0 \cdot \mathbf{x} \le \mathbf{b} \cdot \mathbf{y}\), which is incompatible with \(\mathbf{b} \cdot \mathbf{y} < 0\).
Variants of the theorem of the alternative
The theorem of the alternative presented above “corresponds” to the standard form of a linear program. There are many variations that deal with LPs that are in other forms. The basic strategy for all variants is to setup a primal dual-pair whose constraints and objective functions match the alternatives the variant is about and then reason using the basic theorems we have at our disposal: the fundamental theorem of linear programming and the duality theorems.
Notice that you can even use your knowledge of duals to come up with the full statement given one of the alternatives. For example, say we wanted a variant that goes like:
Either there exists a vector \(\mathbf{x}\) such that \(A \mathbf{x} \le \mathbf{b}\), or there exists a vector \(\mathbf{y}\) such that ???, but not both.
We can write down the primal with those constraints for \(\mathbf{x}\), and take it’s dual (remember free variables produce equations in the dual):
| Primal LP | Dual LP |
|---|---|
| max \({?} \cdot \mathbf{x}\) | min \(\mathbf{b} \cdot \mathbf{y}\) |
| subject to | subject to |
| \( A \mathbf{x} \le \mathbf{b} \) | \( A^\top \mathbf{y} = {?} \) |
| \( \mathbf{y} \ge 0\) |
The question mark still needs to be decided. If we take \({?} = 0\), we can directly reuse the logic of the proof above (check this!). We get the following variant of the theorem of the alternative:
Either there exists a vector \(\mathbf{x}\) such that \(A \mathbf{x} \le \mathbf{b}\), or there exists a vector \(\mathbf{y}\) such that \(A^\top \mathbf{y} = 0\) and \(\mathbf{y} \ge 0\), but not both.
Streamlined logic
When I wrote the proof of theorem of the alternative above I tried to motivate each step, but strictly speaking that’s not necessary for a proof to be correct (though motivation sure helps to make the proof easier to understand, and above all, to feel non-magical). Here’s a streamlined proof that tries not to do more than necessary. When you later prove variants of the theorem of the alternative, you might want to think as in the first proof, but only write in the style of this next proof. (Although, there absolutely nothing wrong with writing your motivation anyway, to help the reader!)
Consider the following primal dual pair:
| Primal LP | Dual LP |
|---|---|
| max \(0 \cdot \mathbf{x}\) | min \(\mathbf{b} \cdot \mathbf{y}\) |
| subject to | subject to |
| \( A \mathbf{x} \le \mathbf{b} \) | \( A^\top \mathbf{y} \ge 0 \) |
| \( \mathbf{x} \ge 0\) | \( \mathbf{y} \ge 0\) |
Notice the dual is automatically feasible, because \(\mathbf{y} = 0\) is a feasible solution. By the fundamental theorem of linear programming that leaves two cases:
- The dual is unbounded:
- Then the dual has a family of feasible solutions with objective function tending to \(-\infty\). In particular, the dual must have feasible solutions with \(\mathbf{b} \cdot \mathbf{y} < 0\). So in this case, the second alternative holds.
- The dual has an optimal solution:
- Then so does the primal, by strong duality, in particular the primal is feasible which is the first alternative.
We’ve shown that in any case one of the alternatives holds. We still need to show that not both of them can hold simultaneously. If they did, then \(\mathbf{x}\) and \(\mathbf{y}\) would be feasible for the primal and dual respectively, and weak duality would tells us that \(0 \cdot \mathbf{x} \le \mathbf{b} \cdot \mathbf{y}\), contradicting that \(\mathbf{b} \cdot \mathbf{y} < 0\).
Remember that the dual is a minimization question, so for it being unbounded means the objective function can be as negative as you want.