Interior Point Methods 2
summary
Covers concrete algorithms and guarantees: path-following Newton steps on the log barrier give the usual sqrt(n) iteration bound for short-step primal‑dual methods, while a parameterized barrier with rho>n+√n yields a guaranteed per‑iteration drop of ~0.15 but still forces an Ω(√n) dependence; infeasible interior-point variants remove a feasible start at the cost of O(n^2 log(1/ε)) iterations, each costing about O(n^3) so practical op‑cost is ~O(n^{3.5} log(1/ε)). Describes the homogeneous self-dual embedding that provides a clear initial point and certificates of infeasibility; notes production codes usually use infeasible frameworks (Mosek uses the embedding) and typical solves take a few dozen iterations.
AI-written summary · about