Midpoint solutions to linear programs There is a linear program for which I want not merely a solution but a solution that's as central as possible on the face of the polytope that assumes the minimal value.

A priori, we expect the minimizing face should be high dimensional for various reasons, including that the objective function being minimized is the maximum of many of the constraints :

Minimize $\epsilon$ subject to $f_i(\bar x) \leq \epsilon &lt; 0$ with $f_i$ linear and $x_i &gt; 0$ for all $i$ and $\sum_i x_i = 1$.

We'd never obtain any centrality-like property form the simplex algorithm of course.  Do any of the usual interior point algorithms exhibit such properties though?  Do any even guarantee they'll avoid vertices or lower dimensional faces whenever possible?



In fact, I'm probably content with a easy quadratic program that finds the midpoint of the entire polytope since centrality matters more than minimality, just vaguely curious if other linear programming algorithms offer relevant properties.

Update : I've reduced the underlying problem to a simple constrained minimization problem solvable with Lagrange multipliers, but the question above remains interesting anyways.
First find the optimal solution, then add the linear constraint that the solution must have value equal to the optimal you want, and restate your LP as the one looking for the largest ball inside the feasible region. Solve this modiefied LP, and you have what you want. 

Why the second problem can be solved using LP is a stnadard cute problem in Computational Geometry...

==============

More formally, you find the affine subspace spanning the feasible points containing the optimal solution. So, assume that the optimal solution lies on the hyperplane $h \equiv cx = \alpha$ (i.e., $\min c x$ was the original LP target function). If $P$ is the feasible region of the original LP, we are looking for the largest ball in $P \cap h$. To this end, we need to compute the smallest dimensional affine subspace containing this set. Once you found this subspace, change variables so that you consider only this affine subapce. Now, your polytope is full dimenisonal, and you can use the second LP as I described above.

So, let $v$ be the vertex computed by the first LP.
Considering all the neighboring vertices to $v$. Consider the affine subspace of $v$ together with all its neighbors that have the same target value (i.e., $\alpha$). It is not hard to see, that this affine subspace is the desired subspace.

So, to summerize: 
(A) solve LP to discover optimal value.
(B) Compute the smallest dimensional subspace containing the feasible solution with the optimal value.
(C) Rewrite the original LP in this affine subpsace (i.e., dropping all the irrelevant dimensions), add a variable, and turn it into an LP for finding the largest ball inside this polytope.