A Principal Pivoting Simplex Algorithm for Linear and Quadratic Programming

Abstract

This paper presents a simplex algorithm for finding a nonnegative solution (or demonstrating the inconsistency) of y = a + Ax where A is positive semi-definite. Linear and quadratic programming problems are of this form. The function exhibited in the proof of finiteness does not appear in other algorithms. If a primal feasible solution is available in the linear programming case, the actual choice of pivot rows is exactly that made in the usual lexicographic simplex method.