Degeneracy degrees of constraint collections

This paper presents an unifying approach to the theory of degeneracy of basic feasible solutions, vertices, faces, and all subsets of polyhedra. It is a generalization of the usual concept of degeneracy defined for basic feasible solutions of an LP-problem. We use the concept of degeneracy degree for arbitrary subsets of ℝ n with respect to linear constraint collections. We discuss the connection with the usual definitions, and establish the relationship between minimal representations of polyhedra and the degeneracy of their faces. We also consider a number of complexity aspects of the problem of determining degeneracy degrees. In the last section we show how our definition of degeneracy can be used to analyze the convergence of interior point methods when the optimal solutions are degenerate. Copyright Springer-Verlag Berlin Heidelberg 2003