Polynomial time second order mehrotra-type predictor--corrector algorithms (Q864824)

An improvement of the second-order Mehrotra-type predictor-corrector interior point algorithm is proposed. The original algorithm was published by [\textit{Y. Zhang} and \textit{D. Zhang} [Math. Program 68, No. 3(A), 303--318 (1995; Zbl 0837.90087)]. The algorithm solves the standard linear programming problem under the assumption that the relative interiors of the feasible solution set of this problem and its dual are nonempty. The authors explain on an example the possible bad behavior of the algorithm and propose so called safeguarded versions of the algorithm, which does not suffer from this bad behavior. A polynomial complexity of the safeguarded algorithms is proved. Some computational experience with, the proposed algorithms is summarized in the concluding part of the paper.