Algunas cuestiones teóricas sobre la validez del algoritmo de Weiszfeld para el problema de Weber

Abstract

El problema económico de Weber se describe matemáticamente como la localización de un punto que minimice la suma ponderada de las distancias a una serie de puntos dados. El algoritmo de Weiszfeld es el método más utilizado para la resolución del problema de Weber a pesar de que puede existir un conjunto de puntos iniciales, denominado el conjunto de Kuhn, para los que el algoritmo no converja al óptimo. Chandrasekaran y Tamir conjeturaron que si los puntos dados no están contenidos en ningún hiperplano del espacio entonces el conjunto de Kuhn es numerable. Dicha conjetura fue probada por Brimberg en 1995, pero la utilización de argumentos incorrectos en la demostración reabrió de nuevo la conjetura de Chandrasekaran y Tamir. En este trabajo se muestra que, en las condiciones de Chandrasekaran y Tamir, el conjunto de Kuhn es de medida cero. Este resultado permite establecer la validez teórica del algoritmo de Weiszfeld (el objetivo de la conjetura de Chandrasekaran y Tamir) puesto que demuestra que es prácticamente nula la probabilidad de que al elegir al azar un punto inicial para el algoritmo de Weiszfeld, éste no converja al óptimo del problema de Weber.