×

zbMATH — the first resource for mathematics

An \(O(\sqrt{n} L)\)-iteration homogeneous and self-dual linear programming algorithm. (English) Zbl 0799.90087
Summary: We present an \(O(\sqrt n L)\)-iteration homogeneous and self-dual linear programming (LP) algorithm. The algorithm possesses the following features: (1) It solves the linear programming problem without any regularity assumption concerning the existence of optimal, feasible, or interior feasible solutions. (2) It can start at any positive primal-dual pair, feasible or infeasible, near the central ray of the positive orthant (cone), and it does not use any big \(M\) penalty parameter or lower bound. (3) Each iteration solves a system of linear equations whose dimension is almost the same as that solved in the standard (primal-dual) interior-point algorithms. (4) If the LP problem has a solution, the algorithm generates a sequence that approaches feasibility and optimality simultaneously; if the problem is infeasible or unbounded, the algorithm will correctly detect infeasibility for at least one of the primal and dual problems.

MSC:
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI