Some New Results Concerning the Primal-Dual Path-Following Interior Point Algorithm for Linear Programming

TL;DRAbstract

The Primal-Dual (PD) path-following interior point algorithm for solving Linear Programming (LP) problems is considered. Firstly, we investigate its convergence and complexity properties when a new long-step linesearch procedure suggested by M. J. D.Powell is employed. Assuming that a primal-dual strictly feasible starting point is available and that the centring parameters are bounded away from zero, we show that the duality gap of the iterates tends to zero, thereby proving that the limit points of the sequence of iterates are solutions of the {LP} problem. Further, we consider whether the limit points of the sequence of iterates generated by some long-step variants of the {PD} algorithm coincide with the analytic centre of the primal-dual solution set of the problem. Because of the difficulty of the analysis involved, we restrict attention to the case when the standard form of the {LP} problem has one equality constraint and multiple solutions. We find that, when the centring parame

Chat with Paper

AI Agents for this Paper