Linear Programming: Foundations and Extensions VI: The Homogeneous Self-Dual Predictor–Corrector MethodTextbook
Interior-point methods are the standard polynomial-time algorithms for linear programming, and the path-following method that practitioners implement (Chapter 18 of Vanderbei's Linear Programming: Foundations and Extensions) comes without a complete convergence proof. Chapter 22 of the same book presents a closely related algorithm for which a complete…