New trajectory-following polynomial-time algorithm for linear programming problems (Q1114587)

From MaRDI portal
scientific article
Language Label Description Also known as
English
New trajectory-following polynomial-time algorithm for linear programming problems
scientific article

    Statements

    New trajectory-following polynomial-time algorithm for linear programming problems (English)
    0 references
    0 references
    1989
    0 references
    A new interior point method for the solution of the linear programming problem is presented. It is shown that the method admits a polynomial time bound. The method is based on the use of the trajectory of the problem, which makes it conceptually very simple. It has the advantage above related methods that it requires no problem transformation (either affine or projective) and that the feasible region may be unbounded. More importantly, the method generates at each stage solutions of both the primal and the dual problem. This implies that, contrary to the simplex method, the quality of the present solution is known at each stage. The paper also contains a practical (i.e., a deep step) version of the algorithm.
    0 references
    0 references
    0 references
    0 references
    0 references
    interior point method
    0 references
    polynomial time bound
    0 references
    path following methods
    0 references
    0 references