Théorie et algorithmes pour la résolution de problèmes numériques de grande taille : application à la gestion de production d’électricité
Institution:
Paris 6Disciplines:
Directors:
Abstract EN:
Au cours de cette thèse, nous nous sommes intéressés à la résolution de problèmes numériquesde grande taille, en particulier à ceux se rapportant à la gestion de production d’électricité. Nous y étudions, dans une première partie, l’algorithme du lagrangien augmenté et présentonsun résultat de convergence linéaire globale de cet algorithme appliqué à un problème quadratique convexe sous contraintes d’égalité et d’inégalité linéaires, éventuellement incompatibles. Ce résultatnous permet de suggérer une règle pour déterminer itérativement le paramètre d’augmentation de l’algorithme, de manière à en contrôler la vitesse de convergence. Nous démontrons également quel’algorithme fournit, à la convergence, la translation la plus petite - au sens de la norme euclidienne- rendant les contraintes réalisables. L’application industrielle de nos travaux consistant à résoudre des problèmes stochastiques formuléssur des arbres de scénarios, nous exposons, dans une deuxième partie, notre étude d’un algorithme proximal spécifiquement adapté à la décomposition scénario par scénario. Il s’agit de l’algorithme du« recouvrement progressif » (ou « progressive hedging ») introduit dans [Rockafellar et Wets, 1991]. D’une part, nous construisons un contre-exemple mettant en évidence que cet algorithme peut divergersi l’on fait varier itérativement son paramètre. D’autre part, nous fournissons un résultat de convergence des multiplicateurs associés à des contraintes non dualisées au cours de l’exécution de cette méthode. Dans une troisième partie, nous produisons les résultats numériques que nous avons obtenussuite à l’application de l’algorithme du recouvrement progressif à un problème réel de gestion de production d’électricité sur un horizon moyen-terme.
Abstract FR:
This manuscript deals with large-scale optimization problems, and more specifically with solvingthe electricity unit commitment problem arising at EDF. First, we focused on the augmented Lagrangian algorithm. The behavior of that algorithm on an infeasible convex quadratic optimization problem is analyzed. It is shown that the algorithm finds a point that satisfies the shifted constraints with the smallest possible shift in the sense of theEuclidean norm and that it minimizes the objective on the corresponding shifted constrained set. The convergence to such a point is realized at a global linear rate, which depends explicitely on theaugmentation parameter. This suggests us a rule for determining the augmentation parameter tocontrol the speed of convergence of the shifted constraint norm to zero. This rule has the advantage ofgenerating bounded augmentation parameters even when the problem is infeasible. As a by-product,the algorithm computes the smallest translation in the Euclidean norm that makes the constraintsfeasible. Furthermore, this work provides solution methods for stochastic optimization industrial problemsdecomposed on a scenario tree, based on the progressive hedging algorithm introduced by[Rockafellar et Wets, 1991]. We also focus on the convergence of that algorithm. On the one hand,we offer a counter-example showing that the algorithm could diverge if its augmentation parameter is iteratively updated. On the other hand, we show how to recover the multipliers associated with thenon-dualized constraints defined on the scenario tree from those associated with the corresponding constraints of the scenario subproblems. Their convergence is also analyzed for convex problems. The practical interest of theses solutions techniques is corroborated by numerical experimentsperformed on the electric production management problem. We apply the progressive hedging algorithmto a realistic industrial problem. More precisely, we solve the French medium-term electricityplanning problem that consists in minimizing the expected electricity production cost, consideringphysical constraints like the boundaries of 155 production units and the dynamic evolution of nuclearstocks, and imposing the equilibrium between production and demand. We also illustrate themultiplier convergence result on the problem that consists in determining the marginal cost of thesupply-demand equilibrium in the medium-term electricity planning at Électricité de France.