# 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.

## 2 Answers

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:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.8466&rep=rep1&type=pdf

• 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. – Arnold Neumaier Dec 2 '17 at 16:44
• Update: found a paper that provides such a solution, although you have to solve the LP with an interior point method rather than the simplex method. See the updated answer above. – Brian Borchers Dec 2 '17 at 20:25

You may want to take a look at a book on linear programming. Finding a starting point for the vertex algorithm of linear programming entails exactly the question you are asking on here. The algorithm used is usually called "phase 1" in linear programming.

• 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