Todd's low-complexity algorithm is a predictor-corrector path-following method (Q1197903)

A variant of Todd's low complexity algorithm, an interior-point method, which requires at most \(O(\sqrt nL)\) iteration steps for solving linear programming problems, is analyzed to be a predictor-corrector path- following method. It is shown that after an initial centering phase each time an affinely scaled Newton-step along an optimal trajectory is performed (predictor step), which is followed then by at most three so- called constant cost entering steps (corrector steps) in order to get back more closely to the trajectory before another affine scaling step is taken. Unfortunately, it is not possible so far to obtain the optimal convergence rate of the method within the proposed setting.