Encontrar equilibrios en el problema de asignación de tráfico con métodos de gradiente primal-dual para el modelo de dinámicas estables y el modelo de Beckmann
Autores: Kubentayeva, Meruza; Gasnikov, Alexander
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Encontrar equilibrios en el problema de asignación de tráfico con métodos de gradiente primal-dual para el modelo de dinámicas estables y el modelo de Beckmann
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Aplicación
Métodos de gradiente
Problema de asignación de tráfico
Equilibrios
Modelo de dinámica estable
Brecha de dualidad
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 33
Citaciones: Sin citaciones
En este documento, consideramos la aplicación de varios métodos de gradiente al problema de asignación de tráfico: buscamos equilibrios en el modelo de dinámica estable (Nesterov y De Palma, 2003) y en el modelo de Beckmann. A diferencia del célebre algoritmo de Frank-Wolfe ampliamente utilizado para el modelo de Beckmann, estos métodos de gradientes resuelven el problema dual y luego reconstruyen una solución al problema primal. Nos ocupamos del método de gradiente universal, el método universal de triángulos similares y el método de promedios duales ponderados y estimamos su complejidad para el problema. Debido a la naturaleza primal-dual de estos métodos, utilizamos una brecha de dualidad en un criterio de parada. En particular, presentamos una nueva forma de reconstruir flujos admisibles en el modelo de dinámica estable, lo que nos proporciona una brecha de dualidad computable.
Descripción
En este documento, consideramos la aplicación de varios métodos de gradiente al problema de asignación de tráfico: buscamos equilibrios en el modelo de dinámica estable (Nesterov y De Palma, 2003) y en el modelo de Beckmann. A diferencia del célebre algoritmo de Frank-Wolfe ampliamente utilizado para el modelo de Beckmann, estos métodos de gradientes resuelven el problema dual y luego reconstruyen una solución al problema primal. Nos ocupamos del método de gradiente universal, el método universal de triángulos similares y el método de promedios duales ponderados y estimamos su complejidad para el problema. Debido a la naturaleza primal-dual de estos métodos, utilizamos una brecha de dualidad en un criterio de parada. En particular, presentamos una nueva forma de reconstruir flujos admisibles en el modelo de dinámica estable, lo que nos proporciona una brecha de dualidad computable.