Hongbo Sun propose un algorithme pour les inégalités variationnelles : 6400 problèmes, 1e-5

Hongbo Sun a présenté un algorithme universel pour les inégalités variationnelles (VI) qui n'exige pas la monotonie de l'application. La méthode fonctionne avec des applications continues arbitraires sur des domaines polyédriques et garantit une convergence linéaire globale. Elle est exacte pour les solutions non dégénérées ; pour les solutions dégénérées, elle atteint toute précision fixée à l'avance. Sur 6400 problèmes aléatoires de dimension allant jusqu'à 1024, l'écart est tombé sous 1e-5 dans chaque cas.

Pourquoi les inégalités variationnelles restent considérées comme un

problème difficile

Une inégalité variationnelle consiste à trouver, dans un ensemble admissible, un point où le champ de directions n'apporte aucune amélioration dans aucune direction admissible. Cette formulation englobe les problèmes d'optimisation, de complémentarité, les problèmes de point selle et les équilibres de jeux. C'est pourquoi les VI reviennent régulièrement dès que plusieurs acteurs optimisent simultanément des objectifs différents : dans les formulations minimax et les systèmes multi-agents.

Le problème est que, pour la plupart des méthodes classiques, les garanties reposent sur la monotonie ou sur des conditions voisines. Sans elles, les algorithmes se mettent à boucler ou divergent. Dans le résumé de l'article, l'autrice qualifie elle-même la conception d'algorithmes universels dotés de garanties de convergence globales de problème ouvert de longue date.

Un fibré plutôt qu'un contournement manuel des singularités

La méthode repose sur le path-following : on cherche la solution en suivant une trajectoire continue à partir d'un point de départ simple. La faiblesse de cette approche est connue. Aux points singuliers, les garanties se rompent et la trajectoire peut se retrouver dans une impasse.

Sun transforme d'abord la VI générale en une VI lisse sur un simplexe. Il décrit ensuite l'ensemble des solutions du système KKT à point fixe comme un fibré au-dessus du simplexe, baptisé « fixed-point bundle ». La géométrie du fibré distingue deux types de déplacement : le long de la base et le long des fibres. Elle permet ainsi de réunir dans un même schéma trois éléments que l'on traite d'ordinaire séparément :

• le choix du point de départ ;
• le déplacement le long de la trajectoire ;
• le contournement des singularités.

À un point singulier, l'algorithme se déplace simplement le long de la fibre jusqu'à un point non dégénéré et poursuit son chemin à partir de là.

Ce que montrent les expériences

La validation a été menée sur des problèmes générés aléatoirement. Principaux paramètres :

• nombre d'instances : 6400 ;
• dimension maximale : 1024 ;
• précision atteinte : écart inférieur à 1e-5 sur toutes les instances ;
• convergence pour les solutions non dégénérées : linéaire globale, exacte ;
• convergence pour les solutions dégénérées : linéaire globale jusqu'à toute précision fixée à l'avance ;
• hypothèses de monotonie ou de propriétés similaires : non requises ;
• domaine de définition : polyèdres ramenés à un simplexe ;
• code et données : github.com/shb20tsinghua/FiberBundle_VI ;
• suite : arXiv:2609.16158, où le cadre est étendu aux produits de simplexes pour le calcul d'équilibres de Nash.

Il faut souligner le résultat « dans chaque cas ». Pour un algorithme sans hypothèses structurelles, l'absence d'échec sur un tel nombre de problèmes aléatoires compte en pratique davantage que la vitesse sur des exemples favorables.

À quoi cela peut servir et ce qu'il faut vérifier

Ce travail n'a pas d'application produit directe : c'est un outil fondamental. Mais la demande est évidente pour ceux qui développent de l'apprentissage multi-agent, des formulations de jeux et des problèmes d'équilibre. Pour eux, l'absence de garanties hors du cas monotone reste une difficulté permanente.

Le dépôt est ouvert. Les praticiens devraient donc d'abord exécuter la méthode sur leurs propres problèmes structurés. Les instances aléatoires montrent bien la robustesse, mais ne remplacent pas un test sur des données réelles, où les applications ont leur propre structure. Il faut aussi vérifier séparément comment le coût d'une itération augmente au-delà de la dimension 1024, et comment l'algorithme se comporte face à des exigences de précision très élevées sur des solutions dégénérées. La suite est déjà tracée : l'extension aux produits de simplexes ouvrira la voie au calcul d'équilibres de Nash dans des jeux à plusieurs participants.