¿cómo obtener la mediana geométrica en 1D resolviendo un problema de optimización?

Question

Tengo un conjunto de números $\{x_1,x_2,\cdots\}$ . La mediana podría obtenerse ordenando, pero quiero conseguirla mediante la resolución de un problema de optimización. Sé que la mediana minimiza $$\sum_i \left| {{x_i} - \mu } \right|$$

Sin embargo, al resolver el problema de optimización mediante un solucionador, obtengo una discrepancia entre la mediana verdadera y la mediana obtenida.

P.D. la mediana podría pensarse como el punto que si se coloca entre los puntos, la distancia entre él y todos los puntos es la más pequeña.

Answer 1

Es cierto que la mediana tiene esta propiedad.

Si el número de puntos es impar, entonces la mediana es el sólo número con esta propiedad. Si obtienes una discrepancia allí, entonces o el solucionador es inexacto, o hay un problema con tu entrada.

Sin embargo, si se tiene un número par de puntos, puede haber muchas soluciones igualmente buenas. Supongamos que los puntos están en orden creciente: $x_1 \le x_2 \le \dots \le x_{2n}$ . Entonces, para cualquier punto $\mu \in [x_n, x_{n+1}]$ tenemos $$\sum_{i=1}^{2n} |x_i - \mu| = \sum_{i=1}^n (\mu - x_i) + \sum_{i=n+1}^{2n} (x_i - \mu) = \sum_{i=n+1}^{2n} x_i - \sum_{i=1}^n x_i.$$ Hay $n$ términos en los que $\mu$ es positivo y $n$ términos en los que $\mu$ es negativo, por lo que se cancelan, y no hay dependencia de $\mu$ : ¡todos los puntos de esta gama son igual de buenos!

De hecho, todos los puntos de la gama $[x_n, x_{n+1}]$ serán las soluciones óptimas. (Si $\mu > x_{n+1}$ , entonces hay más $+\mu$ términos que $-\mu$ términos, por lo que disminuimos la suma disminuyendo $\mu$ . Si $\mu < x_n$ , entonces hay más $-\mu$ términos que $+\mu$ términos, por lo que disminuimos la suma aumentando $\mu$ .)

La mediana suele definirse como $\frac{x_n + x_{n+1}}{2}$ en este caso, pero es más probable que un solucionador de LP dé $x_n$ o $x_{n+1}$ como la solución óptima.