Interior Point Methods 3
summary
Derives a path-following interior‑point method that minimizes the barrier f_mu = (c^T x)/mu + sum_j -log(slack_j) using Newton steps in the local Hessian norm, proves a safe step size delta ≤ O(1/√m) so following the central path gives Õ(√m · log(1/ε)) iterations (surprising √m rate and delta ~1/√m), and explains key tools: Taylor expansion, Hessian = Â^TÂ, Newton decrement, self‑concordance and a projection/optimization bound. Discusses practical issues (initialization, perturbing costs) and directions that beat √m via reweighting / L4‑norm tricks and recent ~√n and specialized max‑flow bounds.
AI-written summary · about