Definitions

  • x is feasible if x ∈ P; an LP is feasible if some feasible x exists, infeasible otherwise 26:06, 26:37.
  • An LP is bounded if min { cᵀx : x ∈ P } ≠ −∞, i.e. the objective cannot be made arbitrarily small 26:37.

The claim

If the LP is bounded, then for every feasible x there is a vertex x′ with cᵀx′ ≤ cᵀx 27:38, 28:14.

The proof is a procedure that gradually pushes x toward a vertex without ever making the objective worse 31:54.

Proof setup

  • If x is already a vertex, take x′ = x 28:14, 28:48.
  • Otherwise there is y ≠ 0 with x ± y ∈ P. Both give A(x ± y) = b; subtracting yields Ay = 0, i.e. y ∈ ker(A) 28:48, 29:11, 29:30, 29:54.
  • WLOG cᵀy ≤ 0 — if not, replace y by −y 29:54, 30:50.
  • If cᵀy = 0, WLOG some coordinate y_j < 0 — since y ≠ 0, one of y or −y has a negative entry, and both keep cᵀy = 0 30:50, 31:28.
  • Key support fact: xᵢ = 0 ⟹ yᵢ = 0, otherwise one of x ± y has a negative coordinate 33:46, 34:25.

Case 1 — some y_j < 0 (progress toward a vertex)

  • Walk along x + t·y for t > 0; every coordinate j with y_j < 0 decreases toward zero 32:49, 34:45, 35:34.

  • Take t as large as possible while staying in P — the explicit formula:

    t* = min over { j : y_j < 0 } of (−x_j / y_j) 41:28

    (per-coordinate, feasibility needs t·y_j + x_j ≥ 0, and dividing by the negative y_j flips the inequality to an upper bound on t; take the smallest such bound 40:05, 40:40, 41:10).

  • t* > 0 strictly: y_j < 0 forces y_j ≠ 0, which by the support fact forces x_j ≠ 0, and feasibility makes x_j > 0 — so there is room to move 39:28, 40:05.

  • Each application of Case 1 creates at least one new zero coordinate, so it can happen at most n times 37:14, 41:49.

  • Worked illustration of why the sign matters: with x = (1,5,0,3,2) and y = (0,1,−2,0,1), no positive step is possible in the direction chosen naively, because a coordinate immediately goes negative 38:29, 38:59.

Case 2 — all y_j ≥ 0 (impossible when bounded)

  • Then A(x + t·y) = Ax + t·Ay = b and x + t·y ≥ 0 for all t > 0, so the ray stays feasible forever 42:15, 42:45, 43:09.
  • In Case 2 the inequality cᵀy ≤ 0 must be strict: if cᵀy = 0 there would be a j with y_j < 0, putting us in Case 1 — Case 1 covers a superset of the cᵀy = 0 situations 43:51, 44:45, 45:31, 46:02, 46:19.
  • So cᵀ(x + t·y) = cᵀx + t·cᵀy → −∞ as t → ∞: the LP is unbounded, contradicting the hypothesis. Case 2 cannot occur for a bounded LP 44:11, 44:30.
  • When neither case applies, no such y exists — you are at a vertex, and done 44:30.

Corollaries

  1. If the LP is finite (bounded and feasible), some vertex of P achieves OPT 46:59.
  2. If P ≠ ∅ then P has at least one vertex 48:15.
    • Proof: apply corollary 1 to the made-up objective min 0ᵀx — any objective works, so pick a trivial one, and the vertex achieving its optimum is a vertex of P 49:22, 49:55.
    • Standard form is essential here: with general constraints (e.g. "below this line and below that line") the feasible region can be a vertex-free strip/wedge 48:59, 49:22.