A general algorithm for determining all essential solutions and inequalities for any convex polyhedron

This paper describes a general non-simplex type algorithm for determining all essential solutions and inequalities for any convex polyhedron defined either in a tangential or in a barycentric form. This algorithm is based on Motzkin’s original Double Description Method, with some additional redundancy criteria in order to eliminate all the extraneous solutions and inequalities. These criteria are compared with other redundancy criteria published in the literature. Also, some simple examples and counter-examples highlighting their scope of validity are exhibited. The theoretical validity of the entire algorithm is proved in a straightforward way using Uzawa’s algorithm. As a consequence, a construction proof for the existence of an essential double description for any convex polyhedron is obtained. Finally, some classical feasibility conditions for general linear inequality systems are recovered.