Principe de programmation dynamique sous contraintes en probabilités

Principe de programmation dynamique sous contraintes en probabilités

Problème d’optimisation stochastique séquentiel

Comme énoncé en avant-propos, un problème d’optimisation stochastique fait intervenir un décideur qui souhaite minimiser un coût. Avant d’énoncer le principe d’optimalité de Bellman, nous allons préciser le type de problèmes d’optimisation stochastique que nous considérons. Puis, nous énoncerons des résultats généraux en temps discret. Enfin, nous particulariserons nos énoncés dans le but de pouvoir faire le lien avec la Section 2.2. P

our une introduction plus détaillée sur la classification des problèmes d’optimisation stochas tique, nous invitons le lecteur à consulter l’introduction de la thèse de Girardeau [Gir10]. 18 2 Principe de programmation dynamique sous contraintes en probabilités 2.1.1 Cadre de travail et principe d’optimalité de Bellman Nous nous plaçons dans un cadre séquentiel. Ainsi, le temps est un ensemble ordonné discret noté T dont les éléments sont des dates notées génériquement t.

Dans toute la suite de cette introduction, une politique de décision est notée par U. En particulier la décision prise à la date t est notée par Ut. L’ensemble des décisions accessibles à la date t est noté Ut. De manière plus générale, une variable aléatoire Yt prend ses valeurs dans Yt. Nous notons (Ft)t∈T, la filtration accessible au décideur. Afin de simplifier les énoncés de cette introduction, nous ferons l’hypothèse que cette filtration est générée par une suite de variables aléa toires indépendantes (Wt)t∈T. Wt prend ses valeurs dans Wt, qui est muni d’une tribu naturelle.

Nous notons alors Pt la loi de Wt. De manière systématique, nous noterons Yt0:t1 le produit cartésien des espaces Ys pour s entre t0 et t1, i.e Yt0:t1 = Qt1 s=t0 Ys. Et de manière abusive, nous noterons Y au lieu de Y0:T. Puisque le décideur ne peut pas prévoir l’avenir, ses décisions doivent être adaptées à la filtration (Ft)t∈T. On notera Ua l’ensemble des politiques de décision adaptées.

Sauf quand nous le préciserons explicitement, pour une fonction h de Y1 dans Y2 et pour une variable aléatoire Y1, la notation h(Y1) est à comprendre comme la composition de h avec Y1 vu comme une fonction mesurable. Ainsi, si tout est compatible, h(Y1) est une variable aléatoire à valeurs dans Y2. Dans la suite, si nous ne précisons rien sur les espaces, c’est qu’il s’agit d’espaces topologiques séparés, leur tribu naturelle sera la tribu Borélienne. Afin de caractériser des situations inacceptables pour le décideur, ou qui briseraient des contraintes d’état imposées par le problème,

nous autorisons les fonctions réelles à prendre la va leur +∞, comme il est classique en optimisation avec la règle d’arithmétique étendue donnée par x ∈ R∪{+∞}, x+(+∞) = +∞. Ainsi le coût pour le décideur est une fonction ϕ de U×W dans R∪{+∞}. On note Ua l’ensemble des contrôles qui sont adaptés à la filtration (Ft)t∈T, et qui sont à valeurs dans Ut à la date t. Le problème formalisé est donc pour le décideur de trouver un contrôle U♯ ∈ Ua tel que : h E ϕU♯,W i = inf U∈Ua E[ϕ(U,W)] (2.1) N’importe quelle politique de décision U♯ qui satisfait l’Equation (2.1) est une politique optimale.

En se plaçant sur un espace fonctionnel adapté, on pourrait probablement résoudre ce problème en utilisant une approche variationnelle liée au principe du minimum de Pontryagin (voir les thèses de 2.1 Problème d’optimisation stochastique séquentiel 19 Girardeau [Gir10] et Barty [Bar04]). Cependant, nous allons préférer l’approche de Bellman [Bel54]. L’idée du principe d’optimalité de Bellman est la suivante :

Theorem 2.1.1 ([Bel54], Principe d’optimalité de Bellman) An optimal policy has the pro perty that no matter what the previous decisions (i.e controls) have been, the remaining decisions must constitute an optimal policy with regard to the state resulting from those previous decisions. Demanière plus intuitive, en reprenant l’exemple du début de la Section 1.3 de Bertsekas [Ber01],

le principe d’optimalité de Bellman dit que si le trajet optimal pour aller de Paris à Marseille passe par Lyon, alors arrivé à Lyon, le trajet optimal pour aller de Lyon à Marseille est de continuer sur le trajet initialement fixé. L’idée du principe d’optimalité de Bellman se traduit en un principe dit principe de program mation dynamique. Ce principe définit un algorithme qui permet peut-être de résoudre le problème d’optimisation (2.1).