Résumé Technique : Décomposition par étapes basée sur les Transformers pour l'optimisation stochastique multi-étapes à grande échelle

1. Énoncé du Problème

L'article traite des défis computationnels inhérents à la résolution de problèmes de Programmation Stochastique Multi-étapes (MSP) à grande échelle. Bien que la MSP soit efficace pour la prise de décision séquentielle en situation d'incertitude (par exemple, l'optimisation de la production, la gestion actif-passif), elle souffre de la « malédiction de la dimensionnalité ». À mesure que le nombre d'étapes et de nœuds de scénarios augmente, le problème équivalent déterministe devient numériquement intraitable.

Les méthodes de décomposition existantes, particulièrement la Programmation Stochastique Duale Dynamique (SDDP), approximent la fonction de valeur par des fonctions convexes par morceaux linéaires construites en accumulant progressivement des plans de coupure de sous-gradients. Bien que la SDDP garantisse la convergence, son temps de calcul augmente de manière monotone à chaque itération car la taille de l'approximation linéaire par morceaux augmente à mesure que les coupes sont ajoutées. De plus, la SDDP traditionnelle nécessite de résoudre le problème à partir de zéro pour chaque nouvelle instance, manquant ainsi la capacité de généraliser à une famille de problèmes apparentés.

2. Méthodologie : TranSDDP

Les auteurs proposent TranSDDP, un nouvel algorithme qui exploite les architectures Transformer pour générer des plans de coupure de sous-gradients afin d'approximer la fonction de valeur dans la SDDP.

Concept Central

Au lieu de résoudre de manière itérative des sous-problèmes pour générer des coupes une par une, TranSDDP traite la génération de plans de coupure comme une tâche de modélisation de séquence. Il utilise un cadre encodeur-décodeur basé sur le Transformer pour apprendre la correspondance entre les paramètres du problème et une séquence de coupes qui approxime la fonction de valeur.

Architecture du Modèle

• Séquence d'Entrée : Le modèle prend un ensemble de paramètres définissant les distributions de probabilité des éléments stochastiques ($\xi_t$) dans les contraintes de région admissible (matrices $A_t, B_t$ et vecteur $b_t$). Ces paramètres sont échantillonnés à partir d'une distribution a priori pour représenter une famille paramétrique de problèmes.
• Séquence de Sortie : Le décodeur génère une séquence de paramètres représentant les coupes : gradients ($\tilde{\beta}_k$), intercepts ($\tilde{\alpha}_k$) et jetons de catégorie ($\tilde{\tau}_k$) indiquant la position dans la séquence (début, milieu, fin ou remplissage/padding).
• Adaptations : L'architecture Transformer standard est modifiée pour gérer des séquences d'entrée et de sortie continues. L'encodage d'entrée est remplacé par des couches linéaires, et la couche softmax est appliquée uniquement aux jetons de catégorie. Une variante, TranSDDP-Decoder, n'utilise que la composante décodeur, les auteurs ayant constaté que l'auto-attention sur les paramètres d'entrée de taille fixe offrait des rendements décroissants.

Système d'Apprentissage

• Génération de Données : Le jeu de données d'entraînement est construit en exécutant la SDDP standard sur diverses instances de problèmes échantillonnées à partir de la famille paramétrique. Les coupes résultantes servent de vérité terrain (ground truth).
• Fonction de Perte : Le modèle est entraîné pour minimiser une perte combinée d'Erreur Quadratique Moyenne (MSE) pour les paramètres de coupe continus ($\beta, \alpha$) et d'Entropie Croisée (CE) pour les jetons de catégorie discrets ($\tau$).
• Teacher Forcing : Pendant l'entraînement, le décodeur reçoit la séquence cible réelle (décalée d'un pas) plutôt que ses propres prédictions pour stabiliser l'apprentissage.
• Initialisation : Le processus de génération est initié avec une « coupe triviale » (par exemple, $\theta \ge 0$) comme premier élément, imitant l'initialisation standard de la SDDP.

3. Principales Contributions

1. Première application des Transformers en MSP : L'article présente la première investigation des approximations de fonctions de valeur basées sur les Transformers spécifiquement dans le domaine de la Programmation Stochastique Multi-étapes, se distinguant ainsi des applications d'Apprentissage par Renforcement.
2. Génération de Coupes Séquentielle : Contra-irement aux approches neuronales précédentes (par exemple, $\nu$-SDDP) qui génèrent un nombre fixe de coupes basées uniquement sur un vecteur de contexte du problème, TranSDDP génère des coupes séquentiellement. Cela permet au modèle de considérer les coupes précédemment générées lors de la production de nouvelles, capturant plus efficacement la nature itérative de la SDDP.
3. Généralisation et Efficacité : Le modèle apprend à générer des coupes pour une famille de problèmes. Une fois entraîné, il peut approximer la fonction de valeur pour de nouvelles instances de problèmes au sein de cette famille sans avoir à résoudre le problème d'optimisation à partir de zéro, réduisant ainsi considérablement le temps d'évaluation.
4. Gestion de la Non-Linéarité : La méthode proposée gère avec succès les problèmes d'optimisation convexe non linéaires (par exemple, la planification financière), là où les approches neuronales précédentes comme $\nu$-SDDP étaient limitées aux programmes linéaires.

4. Résultats Expérimentaux

Les auteurs ont évalué TranSDDP et TranSDDP-Decoder sur trois problèmes de référence : Planification Énergétique, Planification Financière et Planification de la Production, avec 7 et 10 étapes.

• Qualité de la Solution :
  • Les modèles TranSDDP ont obtenu des ratios d'erreur comparables ou supérieurs à la SDDP standard et à l'heuristique de dominance de Niveau 1 (L1).
  • En Planification Énergétique, TranSDDP-Decoder a atteint un ratio d'erreur de 1,01 % (7 étapes) et ~3,8 % (10 étapes), surpassant la SDDP standard (3,3 % et ~3,4 %).
  • En Planification Financière, TranSDDP-Decoder a nettement surpassé la SDDP (0,61 % contre 1,78 % d'erreur pour 7 étapes).
  • Les modèles ont généralement été moins performants que VFGL (Value Function Gradient Learning) sur certains indicateurs spécifiques, mais ont offert une robustesse et une applicabilité supérieures dans les cas non linéaires où $\nu$-SDDP échouait.
• Temps de Calcul :
  • Temps d'Évaluation : TranSDDP a démontré une réduction massive du temps d'évaluation (secondes) par rapport à la SDDP (minutes à heures). Par exemple, en Planification Énergétique, le temps d'évaluation est passé de ~183s (SDDP) à ~1,99s (TranSDDP).
  • Scalabilité : Alors que le temps de calcul total des méthodes traditionnelles augmente linéairement avec le nombre de problèmes à résoudre, le temps total de TranSDDP reste presque constant après la phase d'entraînement initiale, ce qui le rend hautement efficace pour résoudre de grands lots de problèmes apparentés.
• Faisabilité : Les modèles ont initialement généré des coupes infaisables lors des premières époques d'entraînement, mais le ratio d'infaisabilité a convergé vers zéro à mesure que l'entraînement progressait, garantissant que les solutions finales respectent les contraintes.

5. Signification et Revendications

L'article affirme que TranSDDP représente une « progression prometteuse » dans le traitement des problèmes MSP à grande échelle. Sa principale importance réside dans :

• Surmonter la Limite de « Re-résolution » : En apprenant la correspondance entre les paramètres du problème et les approximations de la fonction de valeur, la méthode évite la nécessité de construire explicitement des coupes pour chaque nouvelle instance, répondant ainsi à une limitation clé des méthodes de décomposition traditionnelles.
• Adresser les Limitations de $\nu$-SDDP : Elle résout les contraintes de $\nu$-SDDP en incorporant l'historique des coupes générées (via la nature séquentielle du Transformer) et en étendant l'applicabilité au-delà des programmes linéaires vers les problèmes convexes non linéaires.
• Compromis Efficacité-Qualité : La méthode offre un compromis favorable, réduisant considérablement le temps de calcul tout en préservant la qualité de la solution, particulièrement pour les instances à grande échelle où la SDDP traditionnelle devient prohibitivement lente.

Les auteurs concluent que, bien que la méthode dépende de la qualité des données d'entraînement (générées par la SDDP), elle parvient à apprendre à générer des plans de coupure de sous-gradients sans compromettre la qualité de la solution, offrant une alternative évolutive pour les optimisations stochastiques complexes.