The precision parameter L

  • L ≈ max( log‖b‖_∞ , log det_max , log‖c‖_∞ ) (16:37).
  • det_max is the largest magnitude determinant over submatrices of A; it appears because vertices are found by solving linear systems on submatrices of A, and the bits of precision needed to invert a matrix scale with the log of its determinant (16:37, 17:23, 17:47).
  • Practical reading: "just think of this as precision" (17:47).

When can we stop?

  • Stop when cᵀx_λ − cᵀx* < ε, with ε exponentially small in the precision; at that point the iterate rounds to the true minimizing vertex (18:16, 19:11, 19:32).
  • If one is uncomfortable with the rounding step, the weaker reading is that the LP is minimized up to very small error (19:53).

The derivation

  1. f_λ is strictly convex in x, so it has a unique minimizer x_λ, characterized by ∇f_λ(x_λ) = 0 — the multivariate analogue of setting the derivative to zero (20:10, 21:11).
  2. With the log barrier, ∇f_λ(x) = λc − Aᵀ S(x)⁻¹ 𝟙, where 𝟙 is the all-ones vector and S(x) is the diagonal slack matrix with entries s(x)₁,…,s(x)_m; S(x)⁻¹ exists precisely because an interior point has no zero slack (22:45, 23:23, 23:55).
  3. Dot the zero gradient with x_λ − x*: 0 = (λc − AᵀS(x_λ)⁻¹𝟙) · (x_λ − x*) (24:37, 25:02).
  4. Hence λ·cᵀ(x_λ − x*) = 𝟙ᵀ S(x_λ)⁻¹ A(x_λ − x*); the b terms cancel, so A(x_λ − x*) = s(x_λ) − s(x*) (26:10, 27:08, 27:37).
  5. Expanding the diagonal product: Σᵢ ( s(x_λ)ᵢ − s(x*)ᵢ ) / s(x_λ)ᵢ (28:13, 28:38).
  6. The only inequality used: every slack vector is non-negative, so s(x*)ᵢ ≥ 0 and the sum is at most Σᵢ s(x_λ)ᵢ / s(x_λ)ᵢ = m (28:38, 29:19).

The result

  • cᵀx_λ − cᵀx* ≤ m/λ (29:42).
  • Therefore it suffices to run until λ ≥ m/ε, i.e. λ ≈ m · exp(CL) since ε is exponentially small in the precision (30:30, 30:52).
  • This fixes the target for λ but not yet the iteration count, since the step size for λ has not been proved (30:52).