Henri Gerard - PhD Student

At the cross of Stochastic Optimization,
Machine Learning and Game Theory
Resume Linkedin

Contributions

Papers

Presentations

French contributions

Posters

Package development

PhD topic

Decomposition and coordination
of large scale stochastic optimization problems
with risk measures

English version

Stochastic dynamic optimizations problems are usually large scaled, since solutions are naturally indexed by time (discrete), scenari of hazards, and even space (production units, graph nodes). To solve them, we can decompose the original problem into subproblems, suitably coordinated. For example, decomposition-coordination methods exploit spacial structure, where dynamic systems are attached to graph nodes and statistically coupled (case of transport network, with flows and conservation law).

Significant advances have recently taken place on spatial decomposition methods, in the risk-neutral case, where optimization criterion is obtained by a mathematical expectation under a given probability distribution. In this case, there are theoretical methods for decomposing the system, but application leads to subproblems that are difficult to solve in practice. This difficulty is related to the (information) measurability constraint. The object of the thesis is precisely to advance in the resolution of problems of stochastic optimization with risk measurement by decomposition-coordination methods. First, the student can examine the case where the space of the scenarios is finite, which considerably limits the difficulty of the questions of measurability. He will study the case with risk measures, by "decomposing" them when they are coherent or convex --- by a Fenchel transformation, or on a "base" of CVaR. For example, two-step stochastic programming leads, under appropriate assumptions, to a reformulation as a linear program when the risk measure is coherent (and its dual representation is used).

Since the problems involve successive decision-making steps, the student will have to consider dynamic risk measures. In this case, the decomposition temporal sequence of such measurements corresponds to so-called dynamic coherence properties. The student will systematically study how the three main families of methods of decomposition-coordination --- price, quantities, prediction --- are "well" or not with the possible decompositions of the measure of risk. He will have to analyze under what assumptions about the structure of the problem, including risk measures, such resolution approaches can be made compatible. If possible, the original problem will then be decomposed into optimization sub-problems, each carrying its share of the overall risk, suitably coordinated. This "distribution of risk" is now an important issue in the management of electricity transmission to safety and reliability constraints.

The PhD student will devote particular attention to developing the corresponding algorithms, studying their theoretical convergence (speed) properties and their effectiveness. The parallel / distributed character of these algorithms will be an essential aspect in the applications that will be considered smarts electric grids).

In the case where the space of the scenarios is not finished, difficulties arise with the measurability of the solutions, as well as topological difficulties and analysis functional. Depending on the progress of the work and its aspirations, the student will be able to deepen these theoretical questions.

French version

Les problèmes d'optimisation dynamique stochastique sont généralement de grande taille, puisque les solutions sont naturellement indicées par le temps (discret), les scénarios d'aléas, voire l'espace (unités de production, noeuds d'un graphe). Pour les résoudre, on peut alors chercher à décomposer le problème original en sous- problèmes d'optimisation, convenablement coordonnés. Par exemple, les méthodes de décomposition-coordination peuvent exploiter une structure spatiale, où des systèmes dynamiques sont attachés aux noeuds d'un graphe et sont couplés statiquement (cas d'un réseau de transport, avec des flux entrants et sortants et des lois de conservation).

Des avancées importantes ont eu lieu récemment sur les méthodes de décomposition spatiale, dans le cas dit risque-neutre où le critère d'optimisation est obtenu par une espérance mathématique sous une loi de probabilité donnée. Dans ce cas, on dispose des méthodes théoriques permettant de décomposer le système, mais leur application conduit à des sous-problèmes difficiles à résoudre en pratique. Cette difficulté est liée à la contrainte de mesurabilité (d'information). L'objet de la thèse est précisément d'avancer dans la résolution de problèmes d'optimisation stochastique avec mesure de risque par des méthodes de décomposition-coordination. Dans un premier temps, l'étudiant pourra examiner le cas où l'espace des scénarios est fini, ce qui limite considérablement la difficulté des questions de mesurabilité. Il étudiera le cas avec des mesures de risque, en les "décomposant" lorsqu'elles sont cohérentes ou convexes --- par une transformation de Fenchel, ou sur une "base" de CVaR. Par exemple, la programmation stochastique à deux étapes conduit, sous des hypothèses idoines, à une reformulation comme un programme linéaire lorsque la mesure de risque est cohérente (et qu'on utilise sa représentation duale).

Puisque les problèmes comportent des étapes successives de décision, l'étudiant devra considérer des mesures de risque dynamique. Dans ce cas, la décomposition temporelle de telles mesures correspond à des propriétés dites de cohérence dynamique. L'étudiant étudiera systématiquement comment les trois grandes familles de méthodes de décomposition-coordination --- prix, quantités, prédiction --- se "marient" bien ou non avec les possibles décompositions de la mesure de risque. Il devra analyser sous quelles hypothèses sur la structure du problème, notamment sur les mesures de risque, de telles approches de résolution peuvent être rendues compatibles. Si c'est possible, le problème original se verra alors décomposé en sous-problèmes d'optimisation, chacun portant sa part du risque global, convenablement coordonnés. Cette "répartition du risque" est aujourd'hui un sujet important dans la gestion des réseaux de production-transport d'électricité, soumis à des contraintes de sûreté et de fiabilité.

Le doctorant attachera un soin tout particulier à développer les algorithmes correspondants, à étudier leurs propriétés théoriques de convergence (vitesse) et leur efficacité numérique. Le caractère parallèle/distribué de ces algorithmes constituera un aspect essentiel dans les applications qui seront considérées (notamment celui des smarts grids électriques).

Dans le cas où l'espace des scénarios n'est pas fini, surgissent des difficultés avec la mesurabilité des solutions, ainsi que des difficultés topologiques et d'analyse fonctionnelle. Selon l'avancement des travaux et selon ses aspirations, l'étudiant pourra approfondir ces questions théoriques.

Supervision

This PhD is supervised by two French researchers
as part of collaboration between two labs

Contact

6-8 avenue Blaise Pascal 77420 Champs-sur-Marne

Send mail