# 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
Full Text: