Duality Outcomes: Optimal, Unbounded, Infeasible

For any LP and its dual, exactly four outcome combinations are possible: both optimal (with equal values), primal unbounded and dual infeasible, primal infeasible and dual unbounded, or both infeasible. This lesson establishes the classification using weak and strong duality, and develops the skills to identify each outcome.

Step 1 of 157%

Tutorial

The Four Possible Primal-Dual Outcomes

By the Strong Duality Theorem, if a primal LP has an optimal solution, then so does its dual, with equal objective values. But a primal LP need not have an optimal solution — it may be unbounded (its objective grows without bound over the feasible region) or infeasible (its feasible region is empty). The same holds for the dual.

For any primal LP and its dual, exactly one of the following four outcome combinations occurs:

  1. Both have optimal solutions, with equal objective values.
  2. Primal is unbounded, dual is infeasible.
  3. Primal is infeasible, dual is unbounded.
  4. Both are infeasible.

Every other combination is impossible. In particular:

  • The primal and dual cannot both be unbounded.
  • An optimal LP cannot be paired with an unbounded or infeasible LP.
  • If the primal is optimal, the dual must be optimal with the same value.

Throughout this lesson we use the standard pair

(P): max⁡ cTx  s.t.  Ax≤b, x≥0,(D): min⁡ bTy  s.t.  ATy≥c, y≥0.\text{(P): } \max\ \mathbf{c}^T\mathbf{x} \ \text{ s.t. }\ A\mathbf{x} \le \mathbf{b},\ \mathbf{x} \ge \mathbf{0}, \qquad \text{(D): } \min\ \mathbf{b}^T\mathbf{y} \ \text{ s.t. }\ A^T\mathbf{y} \ge \mathbf{c},\ \mathbf{y} \ge \mathbf{0}.
↑ ↓ navigate · Enter open · Esc close · ⌘K/Ctrl K toggle