An O(√nL) Iteration Large-Step Logarithmic Barrier Function Algorithm for Linear Programming

As a natural extension of Roos and Vial's "Long steps with logarithmic penalty barrier function in llnear programming" (1989) and Ye's "An O(n³L) potential reduction algorithm for linear programming" (1989), it will be shown that the classical logarithmic barrier function method can be adjusted so that it generates the optimal solution in O(√nL) iterations, where n is the number of variables and L is the data length.departmental bulletin pape