Sesión Análisis Numérico y Optimización

Diciembre 14, 11:40 ~ 12:00

Métodos newtonianos para el problema de localización de Fermat-Weber con restricciones en las variables

Montes, Laura

El problema de localización de Fermat-Weber consiste en determinar un punto en el espacio $n$-dimensional que minimice la suma ponderada de las distancias desde ese nuevo punto a $m$ puntos dados [1]. Se asume que los pesos de esta suma son positivos y que se utiliza la norma euclideana. El problema fue inicialmente propuesto por Fermat para el caso bidimensional con tres puntos. El método más reconocido para resolver este problema fue propuesto por Weiszfeld en 1937, el cual se basa en un método de punto fijo aplicado a una reformulación de las condiciones de optimalidad de primer orden. Desde entonces este algoritmo y sus variantes han sido ampliamente estudiados. La principal desventaja de esta formulación es que el gradiente de la función objetivo no está definido en todo el espacio y el algoritmo podría no converger. Algunas versiones solucionan este problema pero aún así \ la convergencia podría ser lenta [3]. Recientemente fueron propuestas variantes que combinan el método de Weiszfeld con ideas newtonianas y que utilizan puntos iniciales arbitrarios, pero la no diferenciabilidad de la función objetivo continua siendo un inconveniente. Por otro lado, en [2] se presentó una formulación del problema de Fermat-Weber sujeto a restricciones de cotas en las variables. El método propuesto allí \ se basa en el método de punto fijo de Weiszfeld con proyecciones. En el presente trabajo también se considera el problema de Fermat-Weber con restricciones de cotas en las variables y se utiliza un algoritmo para obtener un punto inicial adecuado para luego utilizar un método mewtoniano con búsqueda lineal a fin de obtener la solución. Se realizan experimentos numéricos y comparaciones con otras formulaciones. \begin{thebibliography}{99} \bibitem{Beck-Sabach:2015} A. Beck, S. Sabach. {\em Weiszfeld's method: old and new results}, Journal of Optimization Theory and Applications, V. 164, pp. 1--40, 2015. \bibitem{PilottaTorres:2011} {E. A. Pilotta, G. Torres}, {\em A projected Weiszfeld algorithm for the box-constrained Weber location problem}, Applied Mathematics and Computation 218, pp.~2932-2943, 2011. \bibitem{Vardi-Zhang:2001} Y. Vardi, C. Zhang. {\em A modified Weiszfeld algorithm for the Fermat-Weber location problem}, Mathematical Programming, V. 90 (3), pp. 559-–566, 2001. \end{thebibliography}

Autores: Montes, Laura / PILOTTA, Elvio Angel .