Hongbo Sun propone un algoritmo para desigualdades variacionales: 6400 problemas, 1e-5

Hongbo Sun ha presentado un algoritmo universal para desigualdades variacionales (VI) que no necesita que la aplicación sea monótona. El método funciona con aplicaciones continuas arbitrarias sobre dominios poliédricos y garantiza una convergencia lineal global. Para las soluciones no degeneradas es exacta; para las degeneradas, se alcanza cualquier precisión fijada de antemano. En 6400 problemas aleatorios de hasta 1024 dimensiones, la brecha bajó de 1e-5 en todos los casos.

Por qué las desigualdades variacionales siguen siendo un problema difícil

Una desigualdad variacional exige encontrar, dentro del conjunto admisible, un punto en el que el campo de direcciones no ofrezca mejora en ninguna dirección admisible. Esta formulación abarca problemas de optimización, de complementariedad, problemas de punto de silla y equilibrios de juegos. Por eso las VI aparecen con frecuencia allí donde varios participantes optimizan objetivos distintos a la vez: en planteamientos minimax y en sistemas multiagente.

El problema es que, en la mayoría de los métodos clásicos, las garantías dependen de la monotonía o de condiciones cercanas. Sin ellas, los algoritmos entran en ciclos o divergen. En el resumen del artículo, la propia autora describe el desarrollo de algoritmos universales con garantías de convergencia global como un problema abierto desde hace tiempo.

Un fibrado en lugar de esquivar las singularidades a mano

El método se basa en path-following: la solución se busca siguiendo una trayectoria continua desde un punto de partida sencillo. El punto débil de este enfoque es conocido. En los puntos singulares las garantías se rompen y la trayectoria puede quedar atrapada en un callejón sin salida.

Sun primero transforma la VI general en una VI suave sobre un símplex. Después describe el conjunto de soluciones del sistema KKT con punto fijo como un fibrado sobre el símplex, al que llama «fixed-point bundle». La geometría del fibrado separa dos tipos de movimiento: a lo largo de la base y a lo largo de las fibras. Gracias a ello, un único esquema integra tres elementos que normalmente se resuelven por separado:

• la elección del punto de partida;
• el movimiento a lo largo de la trayectoria;
• el rodeo de las singularidades.

En un punto singular, el algoritmo simplemente se desplaza por la fibra hasta un punto no degenerado y continúa el recorrido desde allí.

Qué mostraron los experimentos

La validación se realizó con problemas generados de forma aleatoria. Parámetros clave:

• número de instancias: 6400;
• dimensión máxima: 1024;
• precisión alcanzada: brecha inferior a 1e-5 en todas las instancias;
• convergencia para soluciones no degeneradas: lineal global, exacta;
• convergencia para soluciones degeneradas: lineal global hasta cualquier precisión prefijada;
• supuestos de monotonía o propiedades similares: no se requieren;
• dominio: poliedros que se reducen a un símplex;
• código y datos: github.com/shb20tsinghua/FiberBundle_VI;
• continuación: arXiv:2609.16158, donde el marco se extiende a productos de símplices para calcular equilibrios de Nash.

Conviene fijarse en el resultado «en todos los casos». Para un algoritmo sin supuestos estructurales, que no falle en un número tan grande de problemas aleatorios importa más en la práctica que su velocidad en ejemplos favorables.

Dónde puede resultar útil y qué conviene comprobar

El trabajo no tiene una aplicación directa de producto; es una herramienta fundamental. Pero la demanda es evidente para quienes desarrollan aprendizaje multiagente, planteamientos de juegos y problemas de equilibrio. Para ellos, la falta de garantías fuera del caso monótono sigue siendo un dolor constante.

El repositorio es abierto, así que lo primero que deberían hacer los profesionales es probar el método con sus propios problemas estructurados. Las instancias aleatorias muestran bien la robustez, pero no sustituyen la prueba con datos reales, donde las aplicaciones tienen una estructura propia. Además, conviene comprobar cómo crece el coste de cada paso con dimensiones superiores a 1024 y cómo se comporta el algoritmo con exigencias de precisión muy altas en soluciones degeneradas. El siguiente paso ya está marcado: la extensión a productos de símplices abrirá el camino al cálculo de equilibrios de Nash en juegos con varios participantes.