Cover

Harvard University · 1:24:42 · Watch on YouTube

Summary

This lecture completes the analysis of the interior point method (IPM) for linear programming by supplying its missing engine: Newton's method, a second-order optimization method with oracle access to f, ∇f, and ∇²f. The first half states and proves a progress theorem — if the Hessian is spectrally stable along the segment between consecutive iterates (within a factor 1 ± ε), one Newton step shrinks the gradient's Hessian-norm by a factor ε/(1−ε). The second half plugs that theorem into IPM: it defines centrality as the progress measure, proves that the Hessian of the log-barrier objective is stable precisely because the centrality is small, and derives the classic λ ← (1 + 1/√m)·λ step size, giving ≈ √m·L outer iterations. The lecture closes with the current best bound (√rank(A)·L, via Lee–Sidford's weighted barrier) and a sketch of how to construct the initial central point.

Classification: educational video — a university lecture in a theory course, structured as theorem → proof → application.

Topic breakdown

  1. Recap: Interior Point and Second-Order Methods — the LP setup, the barrier objective f_λ, and what a second-order oracle is.
  2. Newton's Method: the Update Rule and Where It Comes From — x₁ = x₀ − (∇²f)⁻¹∇f as the minimizer of the second-order Taylor model.
  3. The Progress Theorem and the Hessian Promise — the 1 ± ε Loewner sandwich along the segment, and the ‖·‖_A norm.
  4. Preliminary: Rewriting the Spectral Sandwich — whitening (1−ε)A ⪯ B ⪯ (1+ε)A into −εI ⪯ A^{−1/2}(B−A)A^{−1/2} ⪯ εI.
  5. Proof of the Newton Progress Theorem — FTC, norm swap, whitening, and the M² ⪯ ε²I bound.
  6. Back to Interior Point: Centrality, Fine and Coarse — ∇f_λ, ∇²f_λ, and the 1/100 vs 1/3 thresholds.
  7. Verifying Newton's Hypothesis: How Much the Hessian Moves — reducing Hessian stability to slack stability, and showing ε = δ(x₀).
  8. How Fast Can λ Grow? The 1 + 1/√m Bound — the add-and-subtract trick, the projection-matrix bound √m, and the iteration count.
  9. State of the Art: Lee–Sidford's Weighted Barrier — why the unweighted barrier double-counts constraints, and the √rank(A) improvement.
  10. Initialization: Getting the First Central Point — the augmented LP′, the fake-cost trick, and running the IPM in reverse.
graph TD
    subgraph P1["Part 1 — Newton's method"]
        A["2nd-order oracle<br/>(1–2)"] --> B["progress theorem:<br/>Hessian stable ⇒ gradient shrinks<br/>(3)"]
        B --> C["whitening lemma<br/>(4)"]
        C --> D["proof: ‖∇f(x₁)‖ ≤ ε/(1−ε)·‖∇f(x₀)‖<br/>(5)"]
    end
    subgraph P2["Part 2 — Interior point"]
        E["centrality δ_k(x)<br/>fine 1/100 · coarse 1/3<br/>(6)"] --> F["Hessian stability ⇐ δ ≤ 1/3<br/>(7)"]
        F --> G["λ ← (1+1/√m)λ<br/>≈ √m·L iterations<br/>(8)"]
        G --> H["√rank(A)·L via weighted barrier<br/>(9)"]
        G --> I["how to start: LP′ + reverse IPM<br/>(10)"]
    end
    D --> E

Key takeaways

  • One Newton step contracts the gradient by ε/(1−ε) in the Hessian-inverse norm, provided the Hessian stays within (1±ε)·∇²f(x₀) everywhere on the segment from x₀ to x₁ 8:13, 11:22, 33:20.
  • The Hessian of the log-barrier objective ∇²f_λ(x) = AᵀS(x)⁻²A does not depend on c or λ — only on the slacks — so Hessian stability reduces entirely to slack-matrix stability 34:59, 44:01, 58:06.
  • The ε in Newton's hypothesis equals the centrality of the starting point: along the Newton segment the relative slack change is at most t·δ(x₀) ≤ δ(x₀). Starting coarsely central (δ ≤ 1/3) gives ε = 1/3 < 1/2, hence a contraction factor of 1/2 per step and O(1) steps to return from 1/3 to 1/100 40:05, 51:44, 52:16, 53:45.
  • λ can be multiplied by 1 + Θ(1/√m) per outer step. The bound δ_{k+1} ≤ (1+α)·δ_k + α√m comes from an orthogonal-projection argument (‖𝟙‖₂ = √m); requiring δ_{k+1} ≤ 1/3 from δ_k ≤ 1/100 forces α ≈ 1/(10√m) 1:10:58, 1:11:33, 1:12:05.
  • Total outer-loop cost is ≈ √m·L iterations, driving λ from roughly exp(−L) up to m·exp(L) for precision L; the best known bound improves this to √rank(A)·L (Lee–Sidford), by replacing the barrier with a weighted one so that duplicated constraints are not over-counted — making algorithmic an earlier non-constructive existence result of Nesterov (and Nemirovski) 1:12:30, 1:12:52, 1:13:18, 1:14:26, 1:16:25.
  • Initialization is solved by running the method in reverse. Augment the LP with a slack variable z penalized by N ≈ 10^L (bounded + feasible original LP ⇒ optimum has z = 0), take the obvious interior point x = 0, z = ‖b‖_∞, declare a fake cost c = AᵀS(x′)⁻¹𝟙 for which that point is perfectly central at λ = 1, decrease λ to exponentially small while running Newton — then swap in the real cost, which no longer matters at tiny λ, and run forward 1:18:40, 1:20:02, 1:22:23, 1:22:48, 1:23:27.