9
$\begingroup$

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 Monte-Carlo Markov Chains, 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 combinatorically 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user2566092 Jul 28 '15 at 20:44
  • $\begingroup$ @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! $\endgroup$ – Andy Yao Jul 28 '15 at 20:47
  • $\begingroup$ @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]: theory.stanford.edu/~megiddo/pdf/kmm4fin.pdf $\endgroup$ – Mihir Aug 4 '15 at 19:00
  • 1
    $\begingroup$ Boyd and Vandenberghe's book Convex Optimization 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. $\endgroup$ – Rahul Aug 6 '15 at 8:05
3
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wonderful. Thank you so much! $\endgroup$ – Andy Yao Aug 11 '15 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.