A Novel Algorithm for Linear Programming
For optimization researchers, this introduces a novel algorithmic paradigm for linear programming, though no empirical results or comparisons are provided.
This paper presents a new recursive method for solving linear programming problems that reduces dimensionality step by step, with a correctness proof. The method is also extendable to convex optimization problems with nonlinear constraints.
The problem of optimizing a linear objective function,given a number of linear constraints has been a long standing problem ever since the times of Kantorovich, Dantzig and von Neuman. These developments have been followed by a different approach pioneered by Khachiyan and Karmarkar. In this paper we present an entirely new method for solving an old optimization problem in a novel manner, a technique that reduces the dimension of the problem step by step and interestingly is recursive. A theorem which proves the correctness of the approach is given. The method can be extended to other types of optimization problems in convex space, e.g. for solving a linear optimization problem subject to nonlinear constraints in a convex region.