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.

What is your definition of "analytic center"? There are several possible definitions for a "center" of a convex polytope, including the average of the vertices as well as the literal center-of-mass expressed in terms of integrals over the polytope. Furthermore, even with a good definition of "center", it's still possible that your polytope is, in vague terms, "long and thin," in which case standard MCMC will still take a while to mix because you'll keep running into the sides of the polytope. Maybe it doesn't really matter where you start, at least, asymptotically. — user2566092, Jul 28 '15 at 20:44
@user2566092 Thanks a lot for your response! I am currently using a Dikin walk, and according to some of the papers I've read, if I begin at an "analytic center" it mixes strongly in polynomial time. Do you perhaps have an idea of which center this could be? Thank you! — Andy Yao, Jul 28 '15 at 20:47
@AndyYao, does this help: [Kojima1998][1] They talk about finding the analytical centre by minimizing the logarithmic potential function (i.e. -sum_log(Ax-b)). [1]: http://theory.stanford.edu/~megiddo/pdf/kmm4fin.pdf — Mihir, Aug 04 '15 at 19:00
Boyd and Vandenberghe's book [*Convex Optimization*](http://stanford.edu/~boyd/cvxbook/) defines the analytic center of a set of convex inequalities and linear equalities in Sec. 8.5.3. It is equivalent to the definition in Mihir's comment. Note that two different sets of inequalities that define the same polytope can have different analytic centers. — , Aug 06 '15 at 08:05

score 4 · Accepted Answer · edited Oct 03 '17 at 11:14

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.

score 2 · Answer 2 · edited Feb 24 '23 at 10:43

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.

Analytic center of convex polytope

2 Answers2

Linked