Linear programming via least squares

AbstractThe paper suggests a new implementation of the active set method for solving linear programming problems. The proposed method is based on the observation that the search direction can be obtained via the solution of a linear least squares subproblem. It is shown that the steepest descent direction can be computed by solving the same least squares subproblem but with simple bounds on the variables. This direction is used to prevent cycling at degenerate dead points. Numerical experiments illustrate the feasibility of the new approach