Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals (Q1205513): Difference between revisions

A class of primal-dual path following interior point methods for solving linear programming problems is analyzed. The method's iteration steps consist of a Newton-type predictor step along the tangent of an optimal trajectory and some corrector steps recentering the resulting point in order to get close to the trajectory again. It is shown that the number of iterations being necessary to obtain a desired accuracy can be estimated by some curvature integral of the trajectory.