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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Polynomial time second order mehrotra-type predictor--corrector algorithms
scientific article

    Statements

    Polynomial time second order mehrotra-type predictor--corrector algorithms (English)
    0 references
    0 references
    0 references
    13 February 2007
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    linear optimization
    0 references
    predictor--corrector methods
    0 references
    interior point methods
    0 references
    second order methods
    0 references
    polynomial complexity
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references