Restricciones de programación lineal para la esfera más grande dentro de la región

Question

Sea $v_0, ..., v_n \in \mathbb{R}^3$ sean vectores y $k_0, ...,k_n$ sean números positivos.

Hay una región $\Pi$ definido como $\Pi = \{x \in \mathbb{R}^3\;|\;v_i^tx \le k_i \}$

El problema es encontrar el centro y el radio de la esfera más grande dentro de esta región.

¿Cómo puedo escribir este problema como un problema de LP? ¿Cómo identificar el variables de decisión El función objetivo a optimizar y el limitaciones ?

---

Las variables de decisión deben ser el centro y el radio de la esfera.

La función objetivo debe ser maximizar $\frac{4}{3}\pi r^3$ .

No soy capaz de visualizar $\Pi$ Así que estoy atascado en la definición de las restricciones para el centro y el radio.

Answer 1

Para cada punto de una circunferencia con centro $c$ y radio $r$ para satisfacer $v_i^T x \leq k_i$ necesita (1) que $c$ satisface $v_i^T c \leq k_i$ y (2) la distancia entre el círculo y la línea $v_i^Tx = k_i$ ser al menos $r$ . La primera condición es obviamente lineal. La segunda condición podemos expresarla utilizando un resultado bien conocido : $$\frac{|v_i^Tc-k_i|}{||v_i||} \geq r,$$ de la que podemos eliminar los valores absolutos debidos a la primera condición: $$\frac{k_i-v_i^Tc}{||v_i||} \geq r.$$ También se trata de una restricción lineal.

El objetivo se puede sustituir por $\max r$ ya que una transformación monótona de la función objetivo no cambia la localización del óptimo (sólo su valor).