Más cercano, más lejano, más amplio
Autores: Lange, Kenneth
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Más cercano, más lejano, más amplio
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmos
Conjunto convexo
Frank-Wolfe
Ascenso de gradiente proyectado
Función de soporte
Homotopía
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 40
Citaciones: Sin citaciones
El artículo actual propone y prueba algoritmos para encontrar el diámetro de un conjunto convexo compacto y el punto más lejano en el conjunto a otro punto. Para estos dos problemas no convexos, construyo algoritmos de Frank-Wolfe y ascenso de gradiente proyectado. Aunque estos algoritmos están garantizados para ir cuesta arriba, pueden quedar atrapados por máximos locales. Para evitar este defecto, investigo un método de homotopía que deforma gradualmente una bola en el conjunto objetivo. Motivado por el algoritmo de Frank-Wolfe, también encuentro la función de soporte de la intersección de un cono convexo y una bola centrada en el origen y elaboro un algoritmo de bisección conocido para calcular la función de soporte de un conjunto subnivel convexo. Los algoritmos de Frank-Wolfe y gradiente proyectado se prueban en cinco conjuntos convexos compactos: (a) la caja cuyas coordenadas van de -1 a 1, (b) la intersección de la bola unitaria y el ortante no negativo, (c) el simplex de probabilidad, (d) la bola unitaria de norma Manhattan y (e) un conjunto subnivel de la penalización de red elástica. Frank-Wolfe y el ascenso de gradiente proyectado son aproximadamente igual de rápidos en estos problemas de prueba. Ignorando la homotopía, el algoritmo de Frank-Wolfe es más confiable. Sin embargo, la homotopía permite que el ascenso de gradiente proyectado se recupere de sus fallas.
Descripción
El artículo actual propone y prueba algoritmos para encontrar el diámetro de un conjunto convexo compacto y el punto más lejano en el conjunto a otro punto. Para estos dos problemas no convexos, construyo algoritmos de Frank-Wolfe y ascenso de gradiente proyectado. Aunque estos algoritmos están garantizados para ir cuesta arriba, pueden quedar atrapados por máximos locales. Para evitar este defecto, investigo un método de homotopía que deforma gradualmente una bola en el conjunto objetivo. Motivado por el algoritmo de Frank-Wolfe, también encuentro la función de soporte de la intersección de un cono convexo y una bola centrada en el origen y elaboro un algoritmo de bisección conocido para calcular la función de soporte de un conjunto subnivel convexo. Los algoritmos de Frank-Wolfe y gradiente proyectado se prueban en cinco conjuntos convexos compactos: (a) la caja cuyas coordenadas van de -1 a 1, (b) la intersección de la bola unitaria y el ortante no negativo, (c) el simplex de probabilidad, (d) la bola unitaria de norma Manhattan y (e) un conjunto subnivel de la penalización de red elástica. Frank-Wolfe y el ascenso de gradiente proyectado son aproximadamente igual de rápidos en estos problemas de prueba. Ignorando la homotopía, el algoritmo de Frank-Wolfe es más confiable. Sin embargo, la homotopía permite que el ascenso de gradiente proyectado se recupere de sus fallas.