A weighted least squares study of robustness in interior point linear programming (Q1260620)

Although global convergence of the affine scaling algorithm has been proved, it is known that, for a bad choice of the initial interior point, the convergence may become very slow, or even numerical stall may occur. The paper in question studied the robustness of interior point linear programming algorithms, with respect to initial iterates that are close to the boundary (bad initial point). The author computes a modified Newton centering direction and shows that the approach which uses this direction is more robust than both the pure affine scaling approach and one which uses the Newton direction as the centering direction.