An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm 2: τᵏ Stays Bounded Below If (LP) Has an Optimum, and Otherwise κᵏ Stays Bounded Below and τᵏ/θᵏ Is BoundedResearch Paper
Interior-point methods for linear programming are usually analysed under two assumptions: a strictly feasible starting point is known, and the problem has an optimal solution. In practice neither is known in advance. The homogeneous self-dual embedding of Ye, Todd and Mizuno (Math. Oper. Res. 19(1), 1994) removes both assumptions. It embeds a standard-form…