Convex Duality in Perturbed Utility Route Choice

A continuación presento un resumen técnico detallado del artículo "Convex Duality in Perturbed Utility Route Choice" (Dualidad Convexa en la Elección de Rutas con Utilidad Perturbada) de Mogens Fosgerau y Jesper R.-V. Sørensen.

1. Planteamiento del Problema

El artículo aborda el desafío de modelar la elección de rutas en redes de transporte a gran escala (carreteras, bicicletas, transporte público).

• El problema de la explosión combinatoria: En redes urbanas complejas, el número de rutas sin ciclos entre dos puntos es astronómicamente grande (del orden del cuadrado del número de átomos en el universo). Esto hace que los modelos clásicos de elección discreta (como el Logit Multinomial), que requieren definir un conjunto de rutas factibles, sean computacionalmente inviables o estadísticamente sesgados.
• Limitaciones de los modelos existentes: Los modelos recursivos (como el Logit Recursivo) mejoran la situación pero siguen enfrentando dificultades para escalar a redes masivas debido a la necesidad de invertir matrices grandes.
• El modelo PURC: El artículo se centra en el modelo de Elección de Rutas con Utilidad Perturbada (PURC). A diferencia de los modelos discretos, PURC opera directamente sobre la estructura de la red, tratando el flujo en cada enlace como una variable continua. El viajero maximiza una utilidad perturbada:
  $$U(x) = \langle v, x \rangle - H(x)$$
  donde $x$ es el vector de flujos, $v$ son los índices de utilidad (costos negativos) y $H(x)$ es una función de perturbación convexa y separable por enlaces que representa el "costo de información" o la desviación de un flujo base.

2. Metodología y Marco Teórico

Los autores desarrollan una fundamentación de dualidad convexa rigurosa para el modelo PURC.

• Formulación Primal (Problema del Viajero):
  El problema original es una minimización de costos generalizados sujeta a la conservación de flujo:
  $$\min_{x} \{ \langle c, x \rangle + H(x) \mid Ax = b, x \ge 0 \}$$
  Donde $A$ es la matriz de incidencia de la red, $b$ representa la demanda (origen-destino) y $H(x) = \sum h_e(x_e)$ es la suma de funciones de perturbación convexas por enlace.

  • Desafío: El problema primal puede ser no suave (no diferenciable) si las funciones $h_e$ tienen "puntas" (kinks) y tiene restricciones de igualdad que complican la optimización en redes grandes.

• Formulación Dual:
  Mediante el uso de la conjugada de Fenchel ($h_e^*$) de las funciones de perturbación, los autores derivan un problema dual:
  $$\max_{u} \{ \langle b, u \rangle - H^*(A^\top u - c) \}$$
  Donde $u$ son los multiplicadores de Lagrange (potenciales en los nodos).

  • Propiedades clave del dual:
    1. Sin restricciones: El problema dual es unconstrained (no tiene restricciones de igualdad o desigualdad).
    2. Concavidad y Diferenciabilidad: Aunque el problema primal puede ser no suave, el objetivo dual es concavo y diferenciable en todo su dominio.
    3. Recuperación del flujo: El flujo óptimo primal $x$ se recupera directamente del dual mediante la gradiente de la conjugada: $x = \nabla H^*(A^\top u - c)$.

• Analogía con Circuitos Eléctricos:
  El marco teórico revela una isomorfía matemática con los circuitos resistivos (Rockafellar, 1984):

  • El flujo $x$ corresponde a la corriente eléctrica.
  • Los potenciales $u$ corresponden al voltaje.
  • Las funciones de perturbación $h_e$ actúan como la resistencia (o conductancia inversa).
  • La conservación de flujo es la Ley de Kirchhoff.

3. Contribuciones Clave

1. Existencia y Unicidad: Se demuestra que el problema primal tiene una solución única y finita bajo condiciones generales de convexidad estricta en las perturbaciones.
2. Dualidad Fuerte: Se establece que no hay "gap" de dualidad ($p^* = p$), permitiendo resolver el problema primal a través del dual.
3. Optimización Eficiente: La naturaleza diferenciable y sin restricciones del problema dual permite el uso de algoritmos modernos de optimización basados en gradientes (como Newton o métodos de primer orden) que son extremadamente eficientes para redes con decenas de miles de enlaces.
4. Análisis de Sensibilidad (Jacobiano): Se deriva una expresión cerrada y computacionalmente simple para el Jacobiano del flujo óptimo con respecto a los costos de los enlaces ($\nabla x(c)$). Esto es crucial para el análisis de políticas (ej. peajes) sin necesidad de re-solver el equilibrio completo.
5. Generalidad: El marco no requiere que las funciones de perturbación sean diferenciables ni que los costos sean estrictamente positivos, lo que amplía la aplicabilidad del modelo.

4. Resultados Principales

• Teorema de Dualidad (Teorema 3): El valor óptimo dual es igual al primal. Cualquier solución dual óptima $u$ genera el flujo óptimo $x$ mediante la fórmula $x = \nabla H^*(A^\top u - c)$.
• Propiedades de Sensibilidad (Teorema 5 y 6):
  • El mapeo de costos a flujos es continuo y antimonótono (si sube el costo de un enlace, el flujo en él no aumenta).
  • Si las funciones de perturbación son fuertemente convexas, el mapeo es Lipschitz continuo, proporcionando cotas cuantitativas sobre cómo cambian los flujos ante variaciones de costos.
• Estructura del Jacobiano (Teorema 7): El Jacobiano del flujo tiene una estructura de bloque que depende de la red de enlaces "activos" (con flujo positivo). Se puede calcular eficientemente resolviendo sistemas lineales que involucran el Laplaciano ponderado de la red activa, evitando la inversión de matrices densas grandes.
• Ejemplo Numérico: Se demuestra en una red de 4 nodos y 6 enlaces que el algoritmo dual converge rápidamente y permite calcular el Jacobiano exacto, mostrando cómo un cambio en el costo de un enlace afecta los flujos en toda la red de manera coherente con la topología.

5. Significado e Impacto

• Escalabilidad: La principal contribución práctica es la viabilidad de aplicar modelos de elección de ruta a redes masivas (ej. redes de bicicletas en ciudades enteras, como se muestra en los datos de Copenhague) donde los métodos tradicionales fallan.
• Análisis de Políticas: La capacidad de calcular derivadas (sensibilidad) de forma eficiente permite realizar análisis de bienestar y evaluación de impacto de intervenciones (peajes, nuevas infraestructuras) de manera rápida y precisa.
• Unificación Teórica: El trabajo conecta la teoría de redes de transporte con la teoría de optimización convexa y la física de circuitos, ofreciendo una interpretación intuitiva y robusta del comportamiento de los viajeros.
• Aplicabilidad General: El marco se extiende más allá del transporte físico a redes sociales, educativas, dinámicas (con tiempo) y modelos basados en actividades.

En resumen, el artículo transforma el modelo PURC de una formulación teórica interesante a una herramienta computacionalmente robusta y escalable, resolviendo el problema de la "explosión combinatoria" de rutas mediante la dualidad convexa y la analogía con circuitos eléctricos.