logo móvil
Contáctanos

Más cercano, más lejano, más amplio

Autores: Lange, Kenneth

Idioma: Inglés

Editor: MDPI

Año: 2024

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro