How can I find the center of a region in a linear programming problem?

Question

I have an optimization problem that in most respects can be very elegantly expressed via linear programming.

The twist is that I don't actually want to minimize or maximize any of my variables; I want to find the center of the feasible region.

The problem is coming up with a definition of "center" that I can optimize for using an LP solver.

I started out by finding the Chebyshev center; that works for larger feasible regions but many of my feasible regions I'm interested in are extremely long and narrow. I'd like something that's more logically in the "middle" than a Chebyshev sphere can give. An added bonus would be something that still works if one of my constraints is actually an equality (essentially specifying a hyperplane through my problem space), so that it can find the center of the hyperplane within the space. The Chebyshev approach can't do this at all.

As an example problem: I'd like to find the "center" of the region specified by:

x >= 0
x <= 100
y >= 0
y <= 100
x + y >= 90
x + y <= 100

Graph is here

Ideally, I'd like the solution to be x=47.5, y=47.5; however, everything I've thought of so far gives me something either with a very small x or a very small y.

Answer 1

The centroid of a simplex might work for you:

$$ \frac{1}{n} \sum_{i=1}^n v_i. $$

Here, the $v_i$ are the vertices of the polytope.

Addendum: If you're familiar with the theory behind linear programming, you'll find it easy to go from your constraint matrix $A$ to vertices on the polytope. "Selecting" a vertex is equivalent to selecting your basic variables.

Answer 2

The only way I think you can use a quickly solvable linear programming formulation to find something close to a center would be to take your "truly free" inequalities in the form $Ax \leq b$, i.e. after all the implicit equations $Cx = d$ have been identified and removed from the inequalities and expressed separately, and then add one extra variable $\epsilon$ and solve the LP: $\max \epsilon$ subject to $Ax + \epsilon \leq b$ and $Cx = d$. Then whatever solution $(x,\epsilon)$ you get, you will have that $x$ will be toward the center of your original feasible region.

Answer 3

It seems that this cannot be done with linear programming. You have to look into finding the "analytic center of the feasible region" which involves minimizing a sum of logs. Therefore this is a convex optimization problem.

One way to do it is to formulate your problem as $A\mathbf{x}=b$ and $\mathbf{x}>=0$ (to convert all your inequalities to equalities, use slack variables). Then minimize $-\sum_{i}\log{x_{i}}$ with a convex optimization algorithm. $\mathbf{x}$ should contain all the slack variables you had to create.