Analytic center of convex polytope

Question

I have a convex polytope defined by $Ax \leq b$. I want to know how to find the "analytic center" of my convex polytope, because my goal is to sample from the polytope using Markov chain Monte Carlo (MCMC) methods, and it mixes better if i start from the analytic center.

One way to find the "center" would be to find all the vertices of my convex polytope and then take an average of all the vertices. However, the number of vertices scale combinatorially with the dimension of my polytope, and and in terms of run-time, this is not a feasible approach.

I am wondering if there are any other good definitions of "analytic center" of my convex polytope defined by $Ax \leq b$. I am also looking for algorithms that are computationally feasible.

Answer 1

I think your best bet is to formulate your problem as a linear program that finds the Chebyshev center of a polyhedron.

By finding the Chebyshev center of the polyhedron, you try to find the largest hyper-sphere that fits inside the convex hull of the vertices. And, the center of this hyper-sphere can be defined as the center of your polytope.

Take a look at slide 4-19 here:

http://stanford.edu/class/ee364a/lectures/problems.pdf

This problem is surprisingly interesting, because it can be converted to a simple linear program, which can be efficiently solved.

Note that this solution is not necessarily unique, and in particular if the polytope is "thin", then "the center" will be less meaningful. (I.e., you may want to add extra constraints to the optimization program, or change the objective to account for that as well.)

I hope this helps.

Answer 2

The current answer is not addressing the original question. The analytic center of the polytope is defined for a polytope $a_i^T x\leq b_i \,\,\forall i\,$ as the point minimizing the sum of log-barriers of the constraints:

$$\hat{x} = \text{arg}\min_x -\sum_{i} \log \left( b_i - a_i^T x \right)$$

The analytic center is more complex to find than the Chebyshev center (it's a convex nonlinear optimization problem) but it produces more robust results. It has been used in the literature for discrete optimization as the center of reference of the feasible set.

It has a connection to interior point methods, this is the point where the central path starts.