Unboundedness and infeasibility

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.