General central path and the largest step general central path following algorithm for linear programming

摘要

In this paper, we propsoe a general path following method, in which the starting point can be any feasible interior pair and each iteration uses a step with the largest possible reduction in duality gap. The algorithm maintains the O(sq root(n) L) ineration complexity. It enjoys quadratic convergence if the optimal vertex is nondegenerate.