El más cercano el más lejano el más ancho

Área de la Ciencia:

• Algoritmos de optimización
• Geometría computacional
• Análisis convexo

Sus antecedentes:

• Determinar el diámetro y el punto más lejano en conjuntos compactos convexos son problemas fundamentales en la optimización.
• Los algoritmos existentes como Frank-Wolfe y el ascenso de gradiente proyectado pueden quedar atrapados en máximos locales para problemas no convexos.

Objetivo del estudio:

• Proponer y probar nuevos algoritmos para calcular el diámetro y el punto más lejano de conjuntos compactos convexos.
• Investigar la eficacia de un método de homotopía para superar las limitaciones máximas locales de los algoritmos basados en gradientes.

Principales métodos:

• Construcción y prueba de algoritmos de ascenso de gradiente proyectados de Frank-Wolfe.
• Desarrollo y aplicación de un método de homotopía para deformar gradualmente una bola en el conjunto objetivo.
• Cálculo de las funciones de soporte para las intersecciones de conos y bolas convexas y para conjuntos de subniveles convexos.

Principales resultados:

• Los algoritmos de Frank-Wolfe y de ascenso de gradiente proyectado demuestran un rendimiento comparable en conjuntos compactos convexos probados.
• El algoritmo de Frank-Wolfe muestra una mayor fiabilidad cuando no se emplea el método de homotopía.
• El método de homotopía mejora el algoritmo de ascenso de gradiente proyectado, lo que le permite recuperarse de las fallas.

Conclusiones:

• Tanto Frank-Wolfe como el ascenso del gradiente proyectado son viables para el diámetro y los cálculos del punto más lejano.
• Los métodos de homotopía ofrecen una mejora significativa para el ascenso proyectado del gradiente, aumentando su robustez.
• El estudio contribuye con enfoques algorítmicos refinados para problemas de optimización geométrica.