L’optimisation dans l’incertain

En gestion de la production électrique (et c’est un exemple parmi tant d’autres), nous cherchons à trouver des solutions optimales au sens de critères économiques, sous un grand nombre de contraintes techniques et à divers horizons temporels. Mais comment être capable de prendre des décisions pour dans un an, voire même pour dans 15 jours, alors que de très nombreux événements imprévisibles peuvent avoir lieu : des anomalies climatiques, des pannes de centrales, des pics de consommation électrique non prévus, … ? Evidemment, une décision prise à partir de mauvaises prévisions génèrera un planning qui ne correspondra pas à la situation réelle. Dans ce cas, soit nous sommes capables de corriger le tir, via des décisions de secours à des prix élevés, et nous désoptimisons complètement le problème ; soit nous n’en sommes pas capables et nous nous exposons à des situations extrêmes comme un black-out. Dans un contexte où les risques doivent être de mieux en mieux maîtrisés, il est donc nécessaire d’intégrer cette notion d’incertitude dans la modélisation.

Les modèles statiques

Introduisons quelques notations :
– χ ⊂ Rn l’espace des variables de décision ;
– X ⊂ χ l’ensemble des décisions réalisables ;
– x ∈ X un vecteur de décisions ;
– ω un élément de l’espace probabilisé Ω munie d’une probabilité P et d’une σ algèbre F ;
– une fonction objectif F(x, ω) mesurable et convexe en x pour tout ω.

Bien entendu, le problème mathématique de minimisation (ou maximisation) de F(x, ω) sous des contraintes x ∈ X dépend des réalisations de ω et n’a donc pas réellement de sens. Résoudre ce problème fournit autant de solutions possibles que nous disposons de réalisations de ω sans vraiment pouvoir affirmer quelle est la meilleure de toutes. Une façon de régler le problème est d’optimiser la fonction objectif en espérance (ou en moyenne si nous considérons que toutes les réalisations de ω sont équiprobables).

Un problème de ce type est appelé problème statique (ou 1-étape ou “Here and Now”). Cela signifie que, bien que le problème soit défini sur plusieurs périodes de temps, toutes les décisions ne sont prises qu’en une seule fois, et ce dès l’instant initial t0 de la période d’étude. Il n’y a donc aucun moyen de corriger les décisions prises au cours du temps en fonction des réalisations successives de l’aléa ω. Nous disons également que nous sommes en boucle ouverte pour signifier que, en tant que fonction de l’aléa ω, la commande optimale x est une fonction constante.

Nous pouvons souligner deux difficultés à cette approche statique :
– Il peut être assez difficile en pratique de posséder un modèle probabiliste de l’aléa. En effet, certains phénomènes aléatoires peuvent être relativement complexes, voire impossibles à modéliser. Nous pouvons parfois réussir à caler des modèles statistiques sur des historiques sans réelle garantie de qualité. L’hypothèse de connaissance parfaite de P est donc en fait une hypothèse assez forte ;
– D’un point de vue théorique, nous pouvons calculer, en tout point x par lequel cheminera l’algorithme d’optimisation choisi pour résoudre le problème, la valeur f(x) du critère et son sous-gradient ∂f(x), si bien que le problème d’optimisation stochastique (2.1) se ramène au problème déterministe minx∈X f(x) : les méthodes d’optimisation convexe générale (Faisceaux, ACCPM,…) s’y appliquent alors sans difficulté particulière. Cependant, d’un point de vue pratique, chaque évaluation de f(x) ou de ∂f(x) nécessite un calcul d’espérance, ce qui peut s’avérer très consommateur en temps de calcul sur un ordinateur si la variable aléatoire ω prend ses valeurs dans un espace multidimensionnel. Typiquement, pour une distribution continue, le calcul d’intégrales multiples nécessaire pour le calcul de l’espérance est impossible pour une bonne précision quand le nombre de dimensions excède 4 [70].

Le gradient stochastique 

Une approche mieux adaptée que les approches classiques de décomposition à ce type de problème est celle du gradient stochastique ([22, 35, 106]), dont le principe est de faire évoluer simultanément le calcul de l’espérance et la méthode de gradient. L’idée consiste à tirer une suite (ω1 , . . . , ωk , . . .) de réalisations indépendantes de la variable ω suivant sa loi de probabilité, et à faire évoluer la variable x à chaque fois qu’une nouvelle valeur de l’aléa est disponible en effectuant un pas de gradient sur la fonction F en fixant ω à cette valeur ; l’évolution de x doit être suffisamment lente pour que le phénomène de moyenne lié à l’espérance se fasse au cours des itérations. Le grand avantage de cette méthode est donc le calcul totalement implicite de l’espérance.

Cet algorithme, ainsi que ses variantes, est ancien. Nous pouvons citer les initiateurs Robbins et Monro [88], Kiefer et Wolfowitz [56]. Le premier résultat de complexité est dû à Nemirovski et Yudin [68]. Polyak ([78, 79]), Polyak et Tsypkin [80] donnent des résultats de convergence globale (sous des hypothèses de convexité) ainsi que des études de vitesse de convergence et diverses variantes de cet algorithme. Dans Kushner et Clark [58], nous trouverons la méthode de l’équation différentielle moyenne qui permet l’étude de la convergence locale de cet algorithme et de ses variantes. Cette approche est très utile dans le cas non convexe. Comme résultat majeur, nous pouvons citer les travaux de Nesterov et Vial [69] qui, en introduisant la notion de -optimalité avec un niveau de confiance, montrent l’existence d’une solution au problème général et donnent des bornes de complexité (sur le nombre d’itérations de calculs). L’article [54] compare notamment les approches par scénario et de gradient stochastique. Les auteurs montrent qu’avec des pas bien choisis, les résultats obtenus par gradient stochastique peuvent être aussi satisfaisants que pour des approches par scénarios, bien que nous utilisons des calculs de gradient. Enfin, nous pouvons citer quelques applications à la gestion de production électrique ([31, 43, 2]).

Table des matières

1 Introduction
1.1 Contexte
1.1.1 Introduction générale
1.1.2 Le Parc de Production
1.1.3 La gestion de la production électrique
1.1.4 Emergence d’une gestion hebdomadaire/mensuelle de la production
1.1.5 Sujet de thèse
1.2 Contexte : méthodes d’optimisation utilisées
1.2.1 L’optimisation robuste
1.2.2 La programmation stochastique avec règles de décision constantes par morceaux
1.3 Synthèse des résultats
1.3.1 La gestion robuste d’une vallée hydraulique
1.3.2 La gestion du risque physique
1.4 Pour résumer : Apports principaux de la thèse
1.4.1 Aspects méthodologiques de la thèse
1.4.2 Modélisation de problèmes industriels
1.4.3 La validation par simulation
1.5 Publications et communications orales
1.5.1 Communications orales
1.5.2 Articles et chapitres de livre
1.5.3 Notes internes
Bibliographie
2 L’optimisation dans l’incertain
2.1 Les modèles statiques
2.1.1 Le gradient stochastique
2.1.2 L’approche par scénarios
2.1.3 L’aléa dans les contraintes
2.2 Les problèmes à deux étapes
2.3 Les problèmes à plusieurs étapes
2.3.1 La programmation stochastique sur arbre
2.3.2 La programmation dynamique et ses extensions
2.3.3 Les autres approches
2.4 Conclusions
Bibliographie
3 Introduction à l’optimisation robuste linéaire
3.1 Introduction
3.2 Problème d’optimisation linéaire avec coefficients incertains
3.3 Satisfaction en probabilité d’une contrainte d’inégalité
3.3.1 Distribution normale
3.3.2 Distribution uniforme
3.3.3 Distribution générale
3.4 Solution robuste pour un ensemble d’incertitude
3.4.1 Contrainte robuste
3.4.2 Equivalent robuste d’une contrainte d’inégalité
3.5 Probabilité de satisfaction de la contrainte pour une solution robuste
3.5.1 Ensemble d’incertitude Ξ = B(0, k)2
3.5.2 Ensemble d’incertitude Ξ = B(0, 1)∞ ∩ B(0, k)1
3.6 Eléments pour définir l’ensemble d’incertitude
3.6.1 Une approche heuristique basée sur un aléa gaussien
3.6.2 Equivalent robuste
3.7 Problème général d’optimisation linéaire
3.7.1 Equivalent robuste d’une contrainte d’égalité
3.7.2 Performance moyenne et performance garantie
3.8 Problèmes dynamiques
3.8.1 Problèmes avec recours fixe
3.8.2 Règle de décision linéaire par morceaux avec coefficients de recours fixes
3.8.3 Problèmes avec coefficient de recours incertain
3.9 Extension du concept de robustesse : violation contrôlée des contraintes
3.9.1 Définition formelle de la robustesse étendue
3.9.2 Robustesse étendue dans le cadre de la programmation linéaire
3.10 Conclusion
Bibliographie
4 L’optimisation robuste appliquée à la gestion court-terme d’une vallée hydraulique
4.1 Introduction
4.2 Modèle déterministe de gestion d’une vallée hydraulique
4.2.1 Modélisation choisie
4.2.2 Modèle déterministe
4.3 Incertitude
4.3.1 Incertitude sur les apports d’eau
4.3.2 Les recours
4.3.3 Optimisation, incertitude et validation
4.4 Politique de gestion Robuste à Révisions Périodiques (RRP) du problème hydraulique
4.5 Politique de gestion Robuste à Ajustements Linéaires (RAL) du problème hydraulique
4.5.1 Contraintes de turbinage
4.5.2 Contraintes de volume
4.5.3 Fonction-objectif
4.6 Tailles des modèles
4.7 Etude expérimentale
4.7.1 Implémentation
4.7.2 Jeu d’essais
4.7.3 Simulation
4.8 Expérimentations numériques
4.8.1 Comparaison entre DF et DRP
4.8.2 Comparaison entre DRP et RRP
4.8.3 Comparaison entre RRP et RAL
4.9 Expérimentations numériques : débit minimum
4.10 Conclusion
Bibliographie
5 Conclusion

Télécharger le rapport complet