Q&A aside: removing redundant constraints

  • Degeneracies like "bases don't have size exactly m" also afflict ellipsoid and interior point; the course deliberately skips them to avoid pedantry (23:17).
  • To enforce full row rank: add constraints one at a time; if the rank does not increase, the new row was already in the span of the earlier ones, so drop it (24:07).
  • Computing rank: a crude option is det(AᵀA) ≠ 0 (24:44). Better — rank is computable in input-sparsity time: number of non-zeros times a log factor, a result with Lap Chi Lau among the authors, around 2010 (24:44, 25:05). Either way it is clearly in P (25:29).

The dual

  • Primal: min cᵀx s.t. Ax = b, x ≥ 0. Dual: max yᵀb s.t. Aᵀy ≤ c (26:57, 27:38).
  • The primal right-hand side becomes the dual objective (27:38).
  • With equality primal constraints, the corresponding dual variable is unrestricted in sign (27:38).

Two routes to strong duality

  • Non-algorithmic, via convex geometry — the usual choice in other graduate algorithms courses (25:45, 32:34).
  • Algorithmic, as a corollary of simplex working — the route taken here, and considered a nice fact to know (25:45, 32:54).

The shadow price vector

  • Define y = A_B⁻ᵀ c_B — the shadow price vector. It changes as B changes during simplex (25:45, 26:39).

Claim: at every iterate, cᵀ v_B = bᵀ y, where v_B is the current vertex (28:15).

Proof (29:22, 30:11):

  • A_B v_B = b ⟹ v_B = A_B⁻¹ b.
  • cᵀ v_B = c_Bᵀ A_B⁻¹ b = bᵀ A_B⁻ᵀ c_B = bᵀ y.

Why this is not yet strong duality: v_B is primal-feasible by construction, but y need not be dual-feasible — and in fact it is not feasible until the very end (28:48).

Closing the argument with the dual slack

  • Define the dual slack r = c − Aᵀy; dual feasibility means r ≥ 0 (30:11, 31:09).
  • The definition of y forces r_B = 0, and — conveniently — r_N = c̃_N, the reduced cost (31:09).
  • Simplex halts exactly when c̃_N ≥ 0, which is precisely dual feasibility. Equal objective values plus feasibility on both sides gives strong duality (31:55).

Caveat stated openly: the proof is incomplete only because Bland's rule (termination) was not proved (31:55, 32:54).