Some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming (Q1012253): Difference between revisions

The author presents a primal-dual corrector algorithm for linear programming problems which computes a corrector direction at each iteration. The paper begins with a introductory section containing the background of this problem and previous approaches to solving it, including \textit{S. Mehrotra}'s predictor-corrector algorithm [SIAM J. Optim. 2, No.~4, 575--601 (1992; Zbl 0773.90047)]. In the second section the necessary definitions and nomenclature are outlined, followed by the problem formulation and a description of the algorithm. The next section presents examples of linear programs where the algorithm fails to converge to a solution mainly due to the correctors exerting too much influence on the direction in which the iterates move. Several useful theorems are presented, with proof, to investigate this feature in detail. The article concludes with an outline for an algorithm that overcomes this problem, an appendix and a list of relevant references.