# implied equalities and relative interior

What is the best method to find for a linear system of inequalities $Ax\ge b$ with dense $A$ of moderate dimension the affine subspace spanned by the feasible points (i.e., the implied equalities $(Ax)i=b_i$) and a relatively interior feasible point in this subspace?

It shouldn't need the solution of many linear programs. I recall vaguely from long ago that appropriate postprocessing of the solution of a single appropriate LP should be sufficient, but don't remember details.

Probably not the most efficient way, but you could do:

1. Formulate the system of inequalities as

$Ax - s = b$

$s \geq 0$

Then maximize $s_{i}$ with respect to the inequalities for $i=1, 2, \ldots, m$. If the maximum value of some $s_{i}$ is 0, then that inequality is one of the implied equalities. You'll want to remove any redundant equations that appear.

1. Once you've found your system of equations, use LP to find a particular point that satisfies the original inequalities, and then express the affine hull in terms of that particular solution and a basis for the null space of the matrix of implied equality constraints. You can now rewrite the original system of inequalities in terms of the coefficients with respect to this basis and reduce the dimension.

2. In terms of this new basis, find the Chebyshev center of the feasible set within the implied affine set by solving another LP.

P.S. A little research on the internet found a solution to this problem that requires the solution of only one LP. However, the solution must be strictly complementary (something that you don't get from the simplex method but can get using a primal-dual interior point method.) See Theorem 8 in this 1996 paper by Harvey Greenberg and the earlier sources that he cites:

• I'm afraid that I don't see how having a basic feasible solution for $Ax \geq b$ tells you anything about the affine subspace spanned by all of the feasible points. – Brian Borchers Dec 2 '17 at 5:19