Theorems of the alternative
Infeasibility and unboundedness (dual infeasibility) conditions are provided by the so-called theorems of the alternative.
The weak theorems of the alternative, state that
- (Primal feasibility). At most one of the following two systems is solvable
- Ax\preceq_{\mathcal{K}} b (i.e., b-Ax\in\mathcal{K} or Ax+s=b for some s\in\mathcal{K})
- A^* y = 0, y \succeq_{\mathcal{K}^*} 0 and \langle b,y \rangle < 0
- (Dual feasibility). At most one of the following two systems is solvable
- A^*y {}+{} c {}={} 0 and y\succeq_{\mathcal{K}} 0
- Ax\succeq 0 and \langle c,x\rangle {}\leq{} 0
This result is used in the derivation of infeasibility and unbounddedness certificates.