Centro analítico del politopo convexo

Question

Tengo un politopo convexo definido por $Ax \leq b$. Quiero saber cómo encontrar el "centro analítico" de mi politopo convexo, porque mi objetivo es muestrear del politopo usando métodos de Monte Carlo de cadenas de Markov (MCMC), y mezcla mejor si comienzo desde el centro analítico.

Una forma de encontrar el "centro" sería encontrar todos los vértices de mi politopo convexo y luego tomar un promedio de todos los vértices. Sin embargo, el número de vértices escala combinatoriamente con la dimensión de mi politopo, y en términos de tiempo de ejecución, este no es un enfoque factible.

Me pregunto si hay alguna otra buena definición de "centro analítico" de mi politopo convexo definido por $Ax \leq b$. También estoy buscando algoritmos que sean computacionalmente viables.

Answer 1

Creo que tu mejor opción es formular tu problema como un programa lineal que encuentra el centro de Chebyshev de un politopo.

Al encontrar el centro de Chebyshev del politopo, intentas encontrar la esfera hipergrande que se ajusta dentro del casco convexo de los vértices. Y, el centro de esta esfera hiperpuede ser definido como el centro de tu politopo.

Echa un vistazo a diapositiva 4-19 aquí:

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

Este problema es sorprendentemente interesante, porque puede ser convertido en un simple programa lineal, el cual puede ser resuelto eficientemente.

Nótese que esta solución no es necesariamente única, y en particular si el politopo es "delgado", entonces "el centro" será menos significativo. (Es decir, es posible que desees agregar restricciones adicionales al programa de optimización, o cambiar el objetivo para tener en cuenta eso también.)

Espero que esto te ayude.

Answer 2

La respuesta actual no está abordando la pregunta original. El centro analítico del politopo se define para un politopo $a_i^T x\leq b_i \,\,\forall i\,$ como el punto que minimiza la suma de las barreras logarítmicas de las restricciones:

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

Encontrar el centro analítico es más complejo que encontrar el centro de Chebyshev (es un problema de optimización no lineal convexo) pero produce resultados más robustos. Se ha utilizado en la literatura para la optimización discreta como el centro de referencia del conjunto factible.

Tiene una conexión con los métodos de punto interior, este es el punto donde comienza el camino central.