Résolution de grands problèmes en optimisation stochastique dynamique et synthèse de lois de commande

Scenario-tree-based numerical methods are poorly suited to stochastic optimal control problems with several time steps.

“Des développements récents, tant théoriques que numériques, montrent que cette méthodologie est mal adaptée aux problèmes à plusieurs pas de temps.”

Under existence of measurable h and C such that Y equals h(W) and Γ equals C(W) almost surely, the stochastic optimization problem (1.1) is equivalent to a functional optimization problem over φ.

“Alors le problème (1.1) est équivalent au problème : min φ∈Φ ad J (φ) := E (j (φ (W ) , W )) , où Φ ad := Φ ps ∩ Φ mes”

For a broad class of stochastic optimization models that are not a priori dynamically consistent, dynamic consistency can be recovered by extending the state structure.

“Nous montrons que, pour une large classe de modèles d'optimisation stochastique n'étant pas a priori consistants dynamiquement, on peut retrouver la consistance dynamique quitte à étendre la structure d'état du système.”

Particle methods, which also use scenarios, perform better than scenario-tree methods even with many time steps, as shown on numerical examples.

“En effet, nous montrons sur des exemples numériques que les méthodes particulaires, plus récemment développées et utilisant également des scénarios, ont un meilleur comportement même avec un grand nombre de pas de temps.”

In the numerical results, the dominant term of the EQM is the variance, which decreases as the inverse of the branching factor n_b, regardless of the time step.

“On observe clairement que le terme dominant de l'EQM est la variance, qui décroît comme l'inverse du taux de branchement n b , et ce quel que soit le pas de temps.”

• AssumptionThe authors state this as an assumption: The number of Monte-Carlo repetitions used is sufficient to neglect the estimation error in the expectations.

Averaged over many experiments, this edge effect produces a larger bias at the interval boundaries.

“Moyenné sur un grand nombre d'expériences, cela se traduit par un biais plus important sur les bords de l'intervalle.”

• AssumptionThe authors state this as an assumption: The number of Monte-Carlo repetitions used is sufficient to neglect the estimation error in the expectations.

For the filtering example, the optimal control has the form U*_t = gamma*_t(X*_t) with gamma*_t(x) = minus x divided by (T minus t plus epsilon).

“On montre facilement que la solution de ce problème s'écrit U * t = γ * t (X * t ) avec : γ * t (x) = - x T -t + ε . (2.8)”

• AssumptionThe authors state this as an assumption: In the filtering example, the random variables W0 through WT are independent and identically distributed uniform on the interval from minus 1 to 1.

The scenario-tree error is larger at the edges of the interval because a point on the left edge is more likely to have its nearest neighbor on the right than on the left.

“l'erreur commise par la méthode d'arbres est plus importante sur les bords de l'intervalle car la probabilité qu'un point situé sur le bord gauche, par exemple, ait le plus proche voisin à sa droite est supérieure à la probabilité que le plus proche voisin soit sur sa gauche.”

The system of equations is not explicit: one cannot directly extract U^i_t as a function of X^i_t because of coupling between command particles at time t.

“le système d'équations n'est pas explicite : on ne peut pas tirer directement de l'équation (2.12) une expression de U i t en fonction de l'état X i t , car on a un couplage entre les différentes particules de commande à l'instant t”

In the example, bias and variance for the last time-step strategies could not be computed when the branching factor exceeded 10 because the number of nodes became too large.

“nous ne sommes ainsi pas capables de calculer biais et variance pour les stratégies des derniers pas de temps dès lors que le taux de branchement dépasse 10, car le nombre de nœuds impliqués devient trop important.”

• AssumptionThe authors state this as an assumption: The scenario tree is built with a constant branching factor n_b from independent draws.

Scenario tree methods require the number of scenarios to grow exponentially with the time horizon to achieve a given precision.

“Cependant, on constate en pratique que les méthodes basées sur les arbres de scénarios nécessitent, pour atteindre une précision donnée, un nombre de scénarios (pour construire l'arbre) croissant de manière exponentielle avec l'horizon de temps.”

The scenario-tree solution for the filtering example gives U-sharp_i equal to minus (X-sharp_i plus the subtree average of W-sharp_j) divided by (T minus theta(i) plus epsilon).

“U ♯ i = - X ♯ i + j∈F * (i) W ♯ j n T -θ(i) b T -θ(i) + ε , (2.9)”

• AssumptionThe authors state this as an assumption: In the filtering example, the random variables W0 through WT are independent and identically distributed uniform on the interval from minus 1 to 1.

For particle methods, the number of scenarios needed for a given error does not depend on the time horizon.

“Ainsi, si nous opérons la même étude d'erreur sur les méthodes particulaires introduites dans la thèse de Dallagi (2007), nous observons que le nombre de scénarios nécessaires à l'obtention d'une erreur donnée ne dépend pas de l'horizon de temps.”

• cites Dallagi (2007)Not checked yet

  Not checked in the free run.

The variance decreases clearly as N to the minus 1 regardless of the time step considered.

“la variance décroît clairement en N -1 quel que soit le pas de temps considéré.”

• AssumptionThe authors state this as an assumption: The number of Monte-Carlo repetitions used is sufficient to neglect the estimation error in the expectations.

In an example with state dimension 2, the convergence speed of the particle method decreases substantially compared with the one-dimensional case.

“En revanche, cette technique de résolution ne fournit pas une réponse à la malédiction de la dimension : on observe sur un exemple où la dimension de l'espace d'état est de 2 que la vitesse de convergence diminue de manière importante par rapport au cas en dimension 1.”

In the particle-method numerical results, the biases vary at the same speed regardless of the time step.

“On observe que les biais associés aux stratégies particulaires varient à la même vitesse quel que soit le pas de temps.”

• AssumptionThe authors state this as an assumption: The number of Monte-Carlo repetitions used is sufficient to neglect the estimation error in the expectations.

In the particle method experiment, the convergence speed of the bias is clearly lower than in the one-dimensional state case.

“On observe une nette diminution de la vitesse de convergence du biais par rapport au cas de l'espace d'état de dimension 1 considéré précédemment.”

On the example considered, the particle method achieves much better accuracy than scenario trees for the same number of scenarios.

“Sur l'exemple considéré, on montre que l'on est capable d'obtenir une précision bien supérieure à celle obtenue par arbres de scénarios, à nombre de scénarios égal.”

In Figure 2.7, dividing the RMSE by 10 requires multiplying the number of particles by 100.

“Pour la méthode particulaire, on observe dans la figure 2.7 que pour diviser l'EQM par 10, il convient de multiplier le nombre de particules par 100.”

In the scenario-tree numerical experiment, the squared bias is negligible compared with the variance, as in the one-dimensional state case.

“On observe alors que le carré du biais est, comme c'était le cas en dimension 1 d'état, négligeable devant la variance.”

The approximate conditions (2.18) are strictly the same as conditions (2.11).

“On remarque alors que les conditions (2.18) sont strictement les mêmes que les conditions (2.11).”

In the scenario-tree experiment, the squared bias decreases much more slowly than in the one-dimensional state case.

“Cependant, il faut noter qu'il décroît de manière beaucoup plus lente qu'auparavant.”

On the same example, the EQM decay rate observed for scenario trees was of order n_b to the minus 1, where n_b is the branching factor.

“le taux de décroissance de l'EQM observé pour les arbres de scénarios sur le même exemple était de l'ordre de n -1 b , n b étant le taux de branchement de l'arbre.”

• AssumptionThe authors state this as an assumption: The scenario tree is built with a constant branching factor n_b from independent draws.
• AssumptionThe authors state this as an assumption: The number of Monte-Carlo repetitions used is sufficient to neglect the estimation error in the expectations.

In the scenario-tree experiment, the variance also decreases slightly more slowly than in the one-dimensional state case.

“On observe le même phénomène sur la variance : elle décroît légèrement plus lentement qu'auparavant.”

The squared bias decreases at least as N to the minus 2 near 100 particles.

“il apparaît ainsi que le carré du biais décroît au moins comme N -2 au voisinage de 100 particules.”

• AssumptionThe authors state this as an assumption: The number of Monte-Carlo repetitions used is sufficient to neglect the estimation error in the expectations.

The particle method proposed by Dallagi (2007) does not suffer from the same defect as scenario trees.

“Nous procédons ensuite à la même étude d'erreur sur la méthode particulaire proposée par Dallagi (2007) et observons que celle-ci ne souffre pas du même défaut.”

• cites Dallagi (2007)Not checked yet

  Not checked in the free run.

In the particle method experiment, the squared bias becomes predominant over the variance.

“De plus, on observe que celui-ci devient maintenant prépondérant devant la variance.”

In Figure 2.6, dividing the RMSE by 10 requires multiplying the tree branching rate by 10.

“Plus précisément, on observe dans la figure 2.6 que pour diviser l'EQM par 10, il convient de multiplier par 10 le taux de branchement de l'arbre.”

On this example, the EQM of the particle method decreases as N to the minus 1, where N is the number of scenarios used.

“Pour résumer, sur cet exemple, l'EQM associée à la méthode particulaire décroît comme N -1 , N étant le nombre de scénarios utilisés.”

• AssumptionThe authors state this as an assumption: The number of Monte-Carlo repetitions used is sufficient to neglect the estimation error in the expectations.

They observed that the algorithm's behavior is strongly degraded when the thermal subproblem criterion is only piecewise linear.

“Nous avons observé que le comportement de l'algorithme est fortement dégradé lorsque nous considérons un critère pour le sous-problème thermique qui est seulement linéaire par morceaux.”

On the problem with state dimension 7, they cannot implement resolution of the dynamic programming equation by state-space discretization.

“Sur ce problème dont l'état est de dimension 7, nous ne sommes pas capables de mettre en œuvre une résolution de l'équation de programmation dynamique par discrétisation de l'espace d'état.”

The results indicate that the optimal cost of the problem is approximately between 2 and 2.4.

“Les résultats nous indiquent que le coût optimal du problème se situe approximativement entre 2 et 2.4.”

The deviance increases as the method is refined.

“ainsi que l'augmentation de la déviance.”

On the problem studied, the method's behavior appears stabilized after 10 iterations.

“Sur le problème qui nous intéresse, il semble pour autant que le comportement de la méthode soit stabilisé à l'issue de 10 itérations.”

The optimal cost decreases as the method is refined.

“On observe bien la diminution du coût optimal avec le raffinement de la méthode”

Time has a non-negligible influence on the marginal cost.

“On garde, finalement, une influence non négligeable du temps sur le coût marginal.”

The results obtained are of the same order of magnitude, though slightly inferior to the aggregation decomposition method.

“nous obtenons des résultats du même ordre de grandeur, bien que légèrement inférieurs à la méthode de décomposition par agrégation.”

The marginal cost is an increasing function of demand.

“On observe clairement que le coût marginal est une fonction croissante de la demande”

The distribution of the production-demand gap shifts to center around 0 as iterations progress.

“On observe bien que la distribution de l'écart se déplace pour se centrer autour de 0 au fur et à mesure des itérations.”

The primal cost decreases over iterations.

“le coût primal décroît.”

In Example 5.1, for a later date, the value of x_ti has no influence on the optimal control if the dynamics keep the stock positive.

“alors la valeur de x t i n'a pas d'influence sur le contrôle optimal, si on suppose que les dynamiques sont telles que le stock x t reste positif”

The aggregation decomposition method obtains a strategy that is still significantly better than DADP.

“la méthode de décomposition par agrégation obtient une stratégie encore sensiblement meilleure.”

The last two experiments are quasi-indistinguishable.

“les deux dernières expériences sont en fait quasi-indistingables.”

After a few iterations, the primal and dual values stabilize, notably the primal value.

“Au bout de quelques itérations, ces valeurs se stabilisent, notamment la valeur primale.”

A joint probability constraint over multiple times can be modeled via an additional binary random variable Y with dynamics Y_{t0}=1 and Y_{t+1}=Y_t×1_{h_{t+1}(X_{t+1})≥b_{t+1}}, and then written as E(Y_T)≤a.

“Cette dernière peut en fait être modélisée comme la précédente, via l'introduction d'une variable aléatoire supplémentaire à valeurs binaires, dont la dynamique s'écrit : Y t 0 = 1, Y t+1 = Y t × 1 {h t+1 (X t+1 )≥b t+1 } , ∀t = t 0 , . . . , T -1. Elle s'écrit alors : E (Y T ) ≤ a.”

The dual cost increases over iterations.

“le coût dual croît au cours des itérations”

The greater the thermal availability, the lower the system marginal cost.

“plus la disponibilité thermique est grande, moins on risque d'avoir besoin de moyens onéreux, plus le coût marginal du système est faible.”

This allows significantly lower computation times than the aggregation method.

“Cela nous permet en particulier d'avoir des temps de calcul sensiblement inférieurs à la méthode d'agrégation.”

In the case studied, the expectation of the production-demand gap tends to 0 at each time over iterations.

“au moins E D t -n i=1 U i t tend, à chaque instant t, vers 0. C'est en effet ce que nous observons sur la figure 4.7.”

The marginal cost is higher in winter than in summer.

“On retrouve la saisonnalité annuelle qui fait que le coût marginal est plus élevé en hiver qu'en été.”

For any feedback Φ_t, the operator A^Φ_t that maps a cost function to its conditional expectation is linear.

“Remarquons que l'opérateur A Φt t est linéaire.”

The estimation of the coordination variable improves.

“et l'estimation de la variable de coordination s'améliore.”

An almost-sure constraint can be incorporated into the criterion of problem (5.3) as an expectation on the final state added to the final cost K.

“La contrainte presque-sûre peut donc être incorporée dans le critère du problème (5.3) comme une espérance portant sur l'état final qui s'ajoute au coût final K(X T ).”

In Example 5.1, if x_t0 takes only positive values, its value has no influence on the argmin of the criterion.

“Supposons que x t 0 ne prenne que des valeurs positives.Alors sa valeur n'a aucune influence sur l'arg min de ce critère”

In the distributed problem, the probability laws μ_t appear only multiplicatively.

“Remarquons que les lois de probabilité µ t , qui sont par définition positives, n'apparaissent que de manière multiplicative dans le problème.”

The probability law of the state under a feedback Φ_t evolves according to the Fokker-Planck equation μ_{t+1}=A^Φ_t* μ_t, where A^Φ_t* is the adjoint of A^Φ_t.

“µ t+1 = A Φt t ⋆ µ t , avec (A Φt t ) ⋆ l'adjoint de l'opérateur A Φt t .”

Theorem 5.6: There exists a solution U^♯ of problem (5.9) such that U^♯ is measurable with respect to (X,W).

“Théorème 5.6.Il existe une solution U ♯ du problème (5.9) telle que U ♯ soit mesurable par rapport au couple (X, W ).”

• AssumptionThe authors state this as an assumption: In the setup for theorem 5.6, X is measurable with respect to Y and W is independent of Y.

The approximate strategies are piecewise constant functions with 81 pieces.

“Même s'il est difficile de les distinguer, on a bien affaire à des fonctions constantes par morceaux, ces derniers étant au nombre de 81.”

On an example, discretizing problem (2.1) with a scenario tree produced a solution error that decreases as the inverse of the tree's branching factor, independently of the time horizon.

“Nous venons de constater sur un exemple que la discrétisation du problème (2.1) sous la forme d'un arbre de scénarios entraînait une erreur sur la solution qui décroît comme l'inverse du taux de branchement de l'arbre, indépendamment de l'horizon de temps.”

Particle methods have a much better asymptotic behavior, even when the time horizon grows.

“nous montrons que les méthodes particulaires ont un bien meilleur comportement asymptotique, même lorsque l'horizon de temps grandit.”

The difference between the optimal strategy and the average approximate strategy (the bias) is very small compared with what was observed in Figure 2.2.

“entre les stratégies optimale et approchée moyenne (qui n'est autre que le biais) est très faible par rapport à celle que l'on observait dans la figure 2.2.”

Except when noises are identically zero, the optimal Fokker-Planck distribution μ^♯ is always different from a Dirac distribution.

“Cependant, à l'exception de problèmes où les bruits seraient en fait identiquement nuls, une telle distribution µ ♯ t 0 ,t i est toujours différente d'une distribution de Dirac”

Under certain hypotheses, the particle methods introduced in Dallagi's thesis avoid the explosion of complexity as a function of the time horizon.

“Nous montrons dans cette partie que, sous certaines hypothèses, les méthodes particulaires introduites dans la thèse de Dallagi (2007) permettent d'éviter cette explosion de la complexité en fonction de l'horizon de temps.”

• cites Dallagi (2007)Not checked yet

  Not checked in the free run.

Theorem 5.5: Problems (5.3) and (5.7) are equivalent.

“Théorème 5.5.Les problèmes (5.3) et (5.7) sont équivalents.”

The number of scenarios needed to obtain a given precision grows exponentially with the time horizon of the problem.

“nous observons que le nombre de scénarios nécessaire à l'obtention d'une précision donnée croît de manière exponentielle avec l'horizon de temps du problème.”

In the Hasard-Décision case, the minimization in U_{T-1} under expectation is parametric in X_{T-1} and W_T and yields an optimal feedback Φ^♯_{T-1}(X_{T-1}, W_T).

“La minimisation en U T -1 sous l'espérance s'effectue paramétriquement par rapport aux valeurs prises par X T -1 et W T et conduit à une stratégie optimale sous la forme d'un feedback Φ ♯ T -1 (X T -1 , W T ).”

The complexity of representing the Bellman function on a grid depends exponentially on the dimension of the state space, a phenomenon known as the curse of dimensionality.

“Or, la complexité d'une telle procédure dépend clairement de manière exponentielle de la dimension de l'espace d'état.Cette propriété est connue sous le nom de malédiction de la dimension (curse of dimensionality en anglais).”

For decomposable systems, deterministic decomposition results for large systems can be adapted to the stochastic case.

“Pour une classe de systèmes, dits décomposables, nous adaptons des résultats bien connus dans le cas déterministe, portant sur la décomposition de grands systèmes, au cas stochastique.”

The optimality condition can be rewritten as a projection: there exists ε>0 such that U = Π_Ups(U - εE(∇J(U)|Y)).

“∃ε > 0, U = Π U ps (U -εE (∇J (U ) | Y )) ,”

The functional interpretation shows that the optimization problems considered are infinite-dimensional.

“Nous comprenons mieux, à l'aide de cette interprétation, que nous sommes face à des problèmes d'optimisation en dimension infinie.”

Stochastic gradient methods can often be used to treat open-loop problems.

“De plus, on peut souvent utiliser des outils proches de ceux de l'optimisation déterministe, tels que le gradient stochastique (voir Robbins et Monro, 1951, Bertsekas et Tsitsiklis, 2000, ou encore Quadrat, Gousat, Hertz, et Viot, 1981, pour l'utilisation du gradient stochastique sur un problème d'investissement optimal) pour traiter les problèmes en boucle ouverte.”

• cites Robbins et Monro, 1951Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Bertsekas et Tsitsiklis, 2000Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Quadrat, Gousat, Hertz, et Viot, 1981Not checked yet

  Not checked in the free run.

Under the stated conditions, if U* solves problem (1.1), then E(j'(U*,W)|Y) belongs to -∂χ_Ups(U*).

“Si U * est solution de (1.1), alors : E (j ′ (U * , W ) | Y ) ∈ -∂χ U ps (U * ) .”

• cites Dallagi, 2007Not checked yet

  Not checked in the free run.

For large open-loop problems, deterministic decomposition methods can be adapted.

“Quand de tels problèmes sont de grande taille, on peut également adapter les méthodes de décomposition connues dans le cas déterministe (voir Cohen et Culioli, 1990).”

• cites Cohen et Culioli, 1990Not checked yet

  Not checked in the free run.

It is generally impossible to numerically treat problems whose state dimension exceeds about 5.

“Bien qu'il soit difficile de donner une barrière absolue, il est généralement impossible de traiter numériquement des problèmes dont la dimension de l'état dépasse 5, environ.”

Problems with dual effect are significantly more complex than problems with static information.

“Ce type de problèmes est sensiblement plus complexe que les problèmes en information statique.”

Interpolating the control values obtained at each node leads to poor-quality controls.

“On peut bien sûr chercher à interpoler les valeurs de commande obtenues en chaque nœud, mais cela amène, comme nous le montrerons dans le chapitre 2, à des contrôles de mauvaise qualité.”

The poor behavior of scenario-tree methods on multi-step problems is not caused by using scenarios as such but by the tree structure.

“Nous expliquons ici en détails d'où provient ce défaut et montrons qu'il ne peut être attribué à l'usage de scénarios en tant que tel, mais plutôt à la structure d'arbre.”

The scenario tree methodology does not directly provide a solution in the form of a strategy.

“elle ne fournit pas (directement) de solution sous forme de stratégie.”

Open-loop problems are generally less complex than closed-loop problems.

“Les problèmes en boucle ouverte sont généralement moins complexes que les problèmes en boucle fermée, notamment du fait de la nature des variables d'optimisation : dans le cas de la boucle ouverte, nous sommes à la recherche de décisions a priori, alors que dans le cas de la boucle fermée nous cherchons une décision pour chaque observation possible du système.”

This makes evaluating solution quality more delicate, often requiring many independent experiments to assess error.

“Cela rend l'évaluation de la qualité de la solution plus délicat (il faut souvent faire un grand nombre d'expériences indépendantes pour évaluer l'erreur).”

By whitening the noise process, one can assume that noises are independent across time.

“Ainsi, quitte à devoir préalablement blanchir le processus de bruit, on peut supposer l'indépendance en temps des bruits.”

Even with particle methods, the curse of dimensionality remains a challenge in optimal control.

“La deuxième contribution part du constat que, même à l'aide des méthodes particulaires, nous faisons toujours face à ce qui est couramment appelé, en commande optimale, la malédiction de la dimension.”

The dynamic programming equation cannot be directly combined with deterministic large-system decomposition techniques.

“Il faut également noter que l'équation de programmation dynamique ne peut être directement mariée aux techniques de décomposition de grands systèmes bien connues dans le cadre déterministe (voir le cours de Cohen, 2004, et le §3.1).”

• cites Cohen, 2004Not checked yet

  Not checked in the free run.

If U_ps is a closed convex subset and U_mes a closed subspace with Π_Ups(U_mes) ⊂ U_mes, then projection onto U_ps ∩ U_mes equals the composition of projections.

“Lemme 1.6 (Dallagi, 2007, Lemme A.6). Soit U ps un convexe fermé de U et U mes un sous-espace fermé de U tels que Π U ps (U mes ) ⊂ U mes .Alors : Π U ps ∩U mes = Π U ps • Π U mes .”

• cites Dallagi, 2007Not checked yet

  Not checked in the free run.

Analytical calculation of the EQM quantities is difficult, notably because of the interpolations needed to synthesize feedback from decisions at tree nodes.

“Le calcul analytique de ces quantités apparaît difficile, notamment du fait des interpolations nécessaires à la synthèse de feedback à partir des décisions obtenues en les nœuds de l'arbre.”

The solution of the discretized scenario-tree problem depends on the particular random draws used to construct the tree.

“la solution du problème discrétisé dépend par construction des tirages effectués lors de la construction de l'arbre.”

• AssumptionThe authors state this as an assumption: The scenario tree is built with a constant branching factor n_b from independent draws.

Under the stated conditions, there exists an adjoint process Λ satisfying equations (1.6).

“Alors il existe un processus aléatoire Λ, où Λ t est élément de L 2 (Ω, A, P ; X t ), tel que :”

• cites Dallagi, 2007Not checked yet

  Not checked in the free run.

The size of the discretized problem required for a given precision grows exponentially with the time horizon.

“la taille du problème discrétisé nécessaire à l'obtention d'une précision donnée évolue de manière exponentielle en fonction de l'horizon de temps.”

• AssumptionThe authors state this as an assumption: The scenario tree is built with a constant branching factor n_b from independent draws.

After scenario-tree discretization, the problem is no longer stochastic because samples of the random variables have been drawn.

“Insistons à nouveau sur le fait que le problème ainsi discrétisé n'est plus stochastique : on a tiré des échantillons des variables aléatoires W 0 , . . ., W T .”

• AssumptionThe authors state this as an assumption: The scenario tree is built with a constant branching factor n_b from independent draws.

With a constant branching factor and maximum constants, the branching factor required for precision epsilon with probability 1 minus alpha satisfies n_b greater than or equal to O(1) sigma squared over epsilon squared times (n1+n2) times the sum of log(DL/epsilon) and log(O(1)/alpha).

“ce qui revient à n b ≥ O(1)σ 2 ε 2 (n 1 + n 2 ) log DL ε + log O(1) α .”

• AssumptionThe authors state this as an assumption: Hypotheses 2.3 through 2.9 of Shapiro's theorem hold.

The adjoint state represents the sensitivity of the optimal cost to an infinitesimal variation of the state.

“L'état adjoint représente la sensibilité du coût optimal à une variation infinitésimale de l'état.”

If the particle method converges, it yields a strategy satisfying conditions (1.8).

“Ainsi, si la méthode particulaire converge, on a trouvé une stratégie qui vérifie les conditions (1.8).”

The approximate strategy Γ♯ is a random variable, unlike the optimal γ*.

“À la différence de γ * , la stratégie approchée Γ ♯ est une variable aléatoire.”

For multistage problems, it is generally numerically difficult to obtain satisfactory precision from scenario-tree discretization because the required number of nodes grows exponentially with the time horizon and quickly becomes unmanageable.

“il semble qu'il soit en général numériquement difficile, pour des problèmes à plusieurs pas de temps, d'obtenir une précision satisfaisante à l'issue de la discrétisation par arbres de scénarios, du fait que le nombre de nœuds requis croît exponentiellement avec l'horizon de temps, atteignant rapidement une taille que nous ne saurions gérer numériquement.”

• AssumptionThe authors state this as an assumption: The scenario tree is built with a constant branching factor n_b from independent draws.

At the optimum, conditioning on the optimal state X_t is equivalent to conditioning on the past noise.

“On a donc qu'à l'optimum, conditionner par rapport à l'état optimal X t , tel que c'est le cas dans les équations (1.7d) et (1.7e), revient à conditionner par rapport au passé du bruit.”

• AssumptionThe authors state this as an assumption: The random variables W0,...,WT are independent over time.

Therefore, analytical error analysis is difficult even in a particular case.

“De ce fait, il sera difficile d'analyser l'erreur de manière analytique, même dans un cas particulier.”

The optimal state density can be obtained from the optimal strategy by integrating the Fokker-Planck equation.

“On peut l'obtenir à partir de la stratégie solution γ * en intégrant l'équation de Fokker-Planck (voir Quadrat, 2007, Section 1.2).”

• cites Quadrat, 2007Not checked yet

  Not checked in the free run.

Under hypotheses 2.3 to 2.9, if the branching factors satisfy a specified inequality, every epsilon-squared-optimal solution of the scenario-tree discretized problem is epsilon-optimal for the original problem with probability at least 1 minus alpha.

“Alors on a que toute solution ε 2 -optimale pour le problème discrétisé par arbres de scénarios est une solution ε-optimale pour (2.5) avec probabilité au moins égale à 1α.”

• cites Shapiro, 2006Not checked yet

  Not checked in the free run.

• AssumptionThe authors state this as an assumption: Hypotheses 2.3 through 2.9 of Shapiro's theorem hold.

The approximate strategy Gamma-sharp_t is a random variable because it depends on the draws used to build the tree.

“La fonction Γ ♯ t est une variable aléatoire, car elle dépend des tirages effectués pour construire l'arbre.”

Particle methods seem better adapted to multi-stage problems.

“Ces méthodes particulaires constituent une manière différente d'aborder la résolution numérique du problème de commande optimale stochastique qui semble, au vu des résultats présentés ici, mieux s'adapter aux problèmes multi-étapes.”

If the target function is sufficiently smooth, two nearby state points will often fall in the same cell when the experiment is repeated many times, and thus receive the same control value.

“Si la fonction à approcher est suffisamment lisse, soient deux points proches dans l'espace d'état, ceux-ci se retrouveront, si on répète un grand nombre de fois l'expérience, un grand nombre de fois dans la même cellule, et donc avec la même valeur de commande.”

Shapiro's large-deviations result shows that the number of scenarios, or leaves, needed for a given precision grows exponentially with the time horizon.

“il montre que le nombre de scénarios (soit le nombre de feuilles dans l'arbre) nécessaire à l'obtention d'une précision donnée augmente de façon exponentielle avec l'horizon de temps”

• cites Shapiro (2006)Not checked yet

  Not checked in the free run.

The adjoint state Lambda_t is a function of the system state X_t.

“Autrement dit, l'état adjoint est fonction de l'état du système.”

The error is expected to be linked not to the total number of scenarios but to the branching rate.

“On s'attend donc à ce que l'erreur soit liée non pas au nombre total de scénarios échantillonnés afin de construire l'arbre, mais au taux de bifurcation.”

For a fairly important class of stochastic dynamic optimization problems, one can always benefit from dynamic consistency by changing the state variable.

“Cela nous permet de montrer, pour une classe assez importante de problèmes d'optimisation stochastique dynamique, que l'on peut toujours bénéficier de cette propriété, quitte à changer la variable d'état du système.”

The main error source in scenario-tree methods is the evaluation of conditional cost expectations from one time step to the next, which is performed using noise draws.

“la principale source d'erreur 6 provient de l'évaluation des espérances conditionnelles du coût d'un pas de temps sur l'autre”

Under assumptions similar to Proposition 1.8, the optimality conditions (1.6) can be rewritten as (1.7) in the Markovian framework.

“On peut alors, sous des hypothèses essentiellement similaires à celles de la proposition 1.8 (voir Carpentier et al., 2009b, Théorème 2.6), réécrire les conditions d'optimalité (1.6) de la façon suivante.”

• cites Carpentier et al., 2009bNot checked yet

  Not checked in the free run.

• AssumptionThe authors state this as an assumption: The random variables W0,...,WT are independent over time.

Under the independence assumption, the optimal control is a feedback on state X_t.

“Sous l'hypothèse 2.1, on sait, par le principe de programmation dynamique énoncé au §1.2.1, que la commande optimale est en feedback sur l'état X t .Autrement dit, il existe des fonctions γ * t telles que U * t = γ * t (X * t ), où X * 0 = W 0 et X * t+1 = f t (X * t , U * t , W t+1”

• AssumptionThe authors state this as an assumption: The random variables W0,...,WT are independent over time.

For stochastic algorithms, the computed control depends on the state and on the draws used to discretize the random structure.

“Pour ces algorithmes, la commande calculée dépend naturellement de l'état X t , mais dépend également des tirages effectués pour discrétiser la structure aléatoire.”

Because the tree has more nodes at later time steps while the state-space dimension is fixed, the approximate strategies at later time steps naturally have better bias.

“la structure d'arbre fait que le nombre de nœuds à un pas de temps donné augmente avec le temps.On a ainsi, avec le temps, de plus en plus de points pour représenter la stratégie, dont la dimension de l'espace de départ (l'espace d'état) ne varie pas avec le temps.Il est donc naturel d'observer un biais de meilleure qualité pour les stratégies approchées aux derniers pas de temps.”

For deterministic algorithms such as dynamic programming, the solution does not vary from one experiment to another.

“Ce n'est pas le cas pour des algorithmes déterministes tels que la programmation dynamique, dont la solution ne varie pas d'une expérience à l'autre.”

Using the implicit function theorem with sufficient hypotheses, one can extract an expression for U_t as a function of state X_t and the statistical characteristics of noise W_{t+1}.

“En utilisant le théorème des fonctions implicites, avec les hypothèses suffisantes, on pourra donc extraire une expression de U t en fonction de l'état X t et des caractéristiques statistiques du bruit W t+1 .”

The exponential scenario growth property is not linked to the original problem but to the discretization method.

“Par la suite, nous montrons que cette propriété n'est pas liée au problème original mais à la manière dont il est discrétisé.”

Monte-Carlo evaluation of the conditional expectation at a node depends on the number of children, i.e., the branching rate.

“Or, l'évaluation par Monte-Carlo de l'espérance conditionnelle d'une variable aléatoire définie sur le pas de temps directement consécutif au nœud courant dépendra du nombre de tirages utilisés, soit en l'occurrence du nombre de fils de ce nœud, autrement dit du taux de bifurcation.”

Iterating this reasoning, the number of scenarios required for a given precision grows exponentially with the time horizon, on the order of n_b to the T.

“le nombre de scénarios nécessaire à l'obtention d'une certaine précision croît de manière exponentielle avec l'horizon de temps, à la manière de n T b !”

• AssumptionThe authors state this as an assumption: The scenario tree is built with a constant branching factor n_b from independent draws.

In scenario-tree discretization, the attainable precision is tied to the branching factor.

“la précision associée au schéma de discrétisation par arbres de scénarios est ici reliée au taux de branchement.”

The optimality conditions used for the particle method contain only expectations, not conditional expectations.

“Celles-ci ont la propriété de ne plus comporter d'espérances conditionnelles, mais seulement des espérances.”

• cites Dallagi, 2007Not checked yet

  Not checked in the free run.

For a four-time-step problem, one needs n_b times more scenarios than for a three-time-step problem to reach the same precision.

“pour un problème à quatre pas de temps, nous aurons besoin de n b fois plus de scénarios pour construire l'arbre nécessaire à l'obtention de la même précision que pour le problème à trois pas de temps.”

• AssumptionThe authors state this as an assumption: The scenario tree is built with a constant branching factor n_b from independent draws.

The main interest of scenario tree methodology is that it reduces to a deterministic problem solvable by classical methods.

“L'intérêt principal d'une méthodologie telle que les arbres de scénarios est qu'elle permet de se ramener à un problème déterministe, que l'on peut résoudre par les méthodes classiques.”

Dynamic programming suffers from the curse of dimensionality: its complexity grows exponentially with the state-space dimension.

“Cette méthode, que l'on a présenté au §1.2.1, souffre de la malédiction de la dimension : sa complexité varie de manière exponentielle en fonction de la dimension de l'espace d'état !”

• Also stated in: § 2.4 Question de la dimension · plain

  “L'exemple canonique est celui de la programmation dynamique (Bellman, 1957, Bertsekas, 2000).”

• cites Bellman, 1957Not checked yet

  Not checked in the free run.

• cites Bertsekas, 2000Not checked yet

  Not checked in the free run.

The particle method does not provide an answer to the curse of dimensionality.

“En revanche, cette technique de résolution ne fournit pas une réponse à la malédiction de la dimension : on observe sur un exemple où la dimension de l'espace d'état est de 2 que la vitesse de convergence diminue de manière importante par rapport au cas en dimension 1.”

In the absence of the coupling constraint (3.1d), the problem decomposes naturally into n subproblems, one per unit.

“En l'absence de la contrainte (3.1d) le problème se décompose naturellement en n sous-problèmes, chacun portant sur l'une des unités 3 .”

• AssumptionThe authors state this as an assumption: The dynamics of the subsystems are independent of one another.

The optimality conditions (2.17) introduce a coupling between each node and all its children, making it impossible to rewrite them on a subtree.

“Les conditions (2.17) introduisent nettement un couplage entre chaque noeud et l'ensemble de ses fils, rendant impossible une réécriture de ces conditions sur un sous-arbre.”

The smaller the supports of the optimal state and control laws, the better the particle methods perform, even in high-dimensional state spaces.

“Ainsi, plus ces supports seront petits, plus les méthodes présentées ici seront performantes, même dans des espaces d'état de grande dimension.”

The proposed framework and approximate way to proceed encompass the case treated by Strugarek (2006).

“Nous proposons ici un cadre et une manière d'y parvenir de manière approchée, qui englobe le cas traité par Strugarek (2006).”

• cites Strugarek (2006)Not checked yet

  Not checked in the free run.

The convergence speed of both discretization schemes decreases substantially as the state-space dimension increases.

“En conclusion, la vitesse de convergence des deux schémas diminue de manière importante lorsque la dimension de l'espace d'état augmente.”

To reach the same precision as a particle method using N scenarios, a scenario-tree method would need a branching factor of order N, yielding a tree with N to the T nodes.

“pour obtenir la même précision qu'une méthode particulaire utilisant N scénarios, il faudrait, avec une méthode d'arbres de scénarios, utiliser un taux de branchement de l'ordre de N .On obtiendrait ainsi un arbre contenant N T nœuds !”

• AssumptionThe authors state this as an assumption: The scenario tree is built with a constant branching factor n_b from independent draws.

It is generally not obvious how to solve the subproblems directly because the measurability of this random variable is not known a priori.

“Ainsi, il n'est généralement pas évident de résoudre directement les sous-problèmes, étant donné que nous ne connaissons rien a priori sur la mesurabilité de cette variable aléatoire.”

To satisfy a coupling constraint that involves the current noise, it is necessary to know the value of that noise when making the decision.

“Afin de pouvoir satisfaire une telle contrainte, il est évidemment nécessaire de connaître la valeur de ce bruit au moment de prendre la décision.”

Because of its good behavior in small dimension, the particle method is a good candidate within a decomposition method for solving subproblems with small state dimension.

“Son bon comportement en petite dimension en fait en revanche une bonne candidate dans le contexte d'une méthode de décomposition, pour la résolution des sous-problèmes où la dimension de l'état est de petite taille.”

It is not surprising that the scenario-tree variance decreases more slowly than n_b^{-1}, the Monte Carlo rate.

“Il n'est donc pas surprenant que la variance décroisse plus lentement que n -1 b , qui est la vitesse associée aux estimateurs de Monte-Carlo pour le calcul numérique de l'espérance.”

For reasons independent of the resolution method used on the tree, tree-based techniques require a number of scenarios exponential in the time horizon for a given accuracy.

“Cependant, comme il a été discuté au chapitre 2, pour des raisons indépendantes de la méthode de résolution mise en œuvre sur l'arbre, les techniques arborescentes ont le défaut de nécessiter, à précision donnée, un nombre de scénarios exponentiel en l'horizon de temps du problème.”

In closed-loop context, the Lagrange multiplier (price) used to coordinate subsystems is itself a random variable.

“En effet, le multiplicateur de Lagrange (ou prix) qui nous permet de coordonner les sous-systèmes entre eux est, dans le contexte de la boucle fermée, lui aussi une variable aléatoire.”

With a coupling constraint, the optimal management strategy will generally not be independent unit by unit.

“Il est clair que la stratégie optimale de gestion du système n'aura pas, en général, la propriété d'être indépendante unité par unité.”

Scenario trees are inefficient for problems with a large number of time steps.

“Cependant, nous montrons dans cette partie que les arbres de scénarios souffrent d'un défaut important : le nombre de nœuds dans l'arbre nécessaire à l'obtention d'une précision donnée varie de manière exponentielle avec l'horizon de temps, ce qui rend cette technique inefficace pour des problèmes comprenant un grand nombre de pas de temps.”

The observation that particle method performance depends on problem structure is because particles tend to concentrate in the support of the optimal state law, so results are better when the optimal state is not dispersed.

“Il faut noter que ce constat est très dépendant de la structure du problème étudié : puisque les particules ont tendance à se concentrer dans la région support de la loi de l'état optimal, on aura de bien meilleurs résultats dans les cas où l'état optimal est peu dispersé que dans les cas où il visite tout l'espace.”

The convergence speed observed for the particle method is very specific to the problem studied and to the structure of its solution.

“Cette vitesse de convergence est très spécifique au problème étudié et à la structure de sa solution.”

Scenario trees suffer from an important defect: the number of nodes needed for a given accuracy grows exponentially with the time horizon.

“Cependant, nous montrons dans cette partie que les arbres de scénarios souffrent d'un défaut important : le nombre de nœuds dans l'arbre nécessaire à l'obtention d'une précision donnée varie de manière exponentielle avec l'horizon de temps, ce qui rend cette technique inefficace pour des problèmes comprenant un grand nombre de pas de temps.”

Implementing local strategies based only on local information would be clearly suboptimal from the global economic criterion.

“Ainsi, mettre en œuvre des stratégies locales, où la gestion de chaque unité ne se ferait que sur la base de l'information locale à l'unité, serait clairement sous-optimal du point de vue du critère économique global.”

In the deterministic setting, decomposition methods can replace a large problem by successive smaller problems while guaranteeing, under certain hypotheses, that the resulting control is optimal for the original system.

“Dans le cadre déterministe, les méthodes de décomposition permettent de remplacer la résolution d'un problème de grande taille par des résolutions successives de problèmes de plus petite taille tout en garantissant, sous certaines hypothèses, que la commande ainsi trouvée correspond bien à la commande optimale du système de départ.”

• cites Cohen (1978)Not checked yet

  Not checked in the free run.

The particle method behaves better than the scenario-tree method with respect to the number of time steps of the problem.

“La méthode particulaire, qui a un meilleur comportement que la méthode d'arbre de scénarios vis-à-vis du nombre de pas de temps du problème, n'est pas une réponse à la malédiction de la dimension.”

From a certain state dimension onward, the particle method will require too many particles to achieve a reasonable error, whatever regression operator is used.

“Il faut cependant rester conscient qu'à partir d'une certaine dimension, la méthode particulaire demandera d'utiliser un trop grand nombre de particules afin d'obtenir une erreur raisonnable, ce quel que soit l'opérateur de régression utilisé.”

The particle method can be seen as a technique that drastically reduces the number of branches of a scenario tree by using regression operators.

“On peut donc voir la méthode particulaire comme une technique réduisant drastiquement le nombre de branches d'un arbre de scénarios en utilisant des opérateurs de régression.”

Even considerable improvements in computing power have not pushed the barrier of dynamic programming beyond small dimensions.

“Ceci est une barrière que même l'amélioration considérable des moyens de calculs n'a pas réussi à repousser au-delà de petites dimensions.”

The particle method is not a solution to the curse of dimensionality.

“La méthode particulaire, qui a un meilleur comportement que la méthode d'arbre de scénarios vis-à-vis du nombre de pas de temps du problème, n'est pas une réponse à la malédiction de la dimension.”

The discretized optimality conditions (2.11) can be obtained from the optimality conditions of the problem discretized on a scenario tree.

“Nous montrons qu'en fait les conditions (2.11) peuvent être obtenues à partir des conditions d'optimalité du problème que l'on aurait discrétisées sur un arbre de scénarios.”

In the simulation phase, feasible strategies can be built by adjusting thermal production.

“nous sommes capables de construire, en phase de simulation des stratégies réalisables en jouant sur la production thermique.”

• AssumptionThe authors state this as an assumption: In the model used, thermal production is not subject to stock constraints, which makes it much easier to place.

This requirement implies a model with several thousand time steps.

“Cela implique a priori un modèle comportant plusieurs milliers de pas de temps.”

Because a weekly time step was used, the daily and weekly seasonalities of demand cannot be observed.

“Ayant considéré un pas de temps hebdomadaire, nous ne pouvons observer les deux autres saisonnalités importantes de la demande”

The hydraulic subproblem cannot be decoupled in time because of the dynamic constraints.

“Ce problème ne peut être découplé en temps du fait des contraintes de dynamique.”

Proposition 3.1 (Strugarek, 2006): if the random variables (D_t,A_t) are independent over time and there exists α>0 such that γ_j=α c_j for all j, then the optimal multiplier λ associated with the coupling constraints (3.4c) is given by a specific dynamic equation.

“Proposition 3.1 (Strugarek, 2006).Si les variables aléatoires (D t , A t ) t=1,...,T sont indépendantes pas de temps par pas de temps, et si il existe α > 0 tel que γ j = αc j , pour tout j = 1, . . ., n, alors le multiplicateur optimal λ associé à l'ensemble des contraintes couplantes (3.4c) est donné par l'équation dynamique”

• cites Strugarek, 2006Not checked yet

  Not checked in the free run.

They do not know how to compute exactly the criterion J(U)=E(j(U,W)).

“nous ne savons pas calculer de manière exacte le critère J(U ) := E (j (U , W )).”

For the model considered, it is always possible to make thermal production exactly complement stock production.

“Pour notre modèle, cela est toujours possible.”

• AssumptionThe authors state this as an assumption: In the model used, thermal production is not subject to stock constraints, which makes it much easier to place.

The heterogeneity of stock characteristics prevents direct aggregation.

“L'hétérogénéité des caractéristiques de ces stocks nous empêche de les agréger directement.”

This strict convexity is necessary to guarantee convergence of a resolution algorithm to the optimal solution, at least in the deterministic case.

“Cette propriété est nécessaire pour garantir que, du moins dans le cas déterministe, un algorithme de résolution tel que celui que nous décrivons par la suite converge vers la solution optimale du problème.”

The confidence intervals obtained are too wide to detect a cost improvement once more than a few iterations are used.

“Il faut noter que les intervalles de confiance que nous obtenons sont trop grands pour nous permettre d'observer une amétendu ou non de l'état du parc de production à chaque instant et pour chaque scénario.”

• Also stated in: § 4.5.2 Comparaison · plain

  “lioration du coût dès lors que l'on dépasse quelques itérations.”

Under classical convexity and continuity assumptions, the DADP stochastic decomposition algorithm generates a sequence of strategies converging to the optimal strategy of problem (3.7).

“sous les hypothèses classiques de convexité et de continuité qui sont précisées dans ce théorème, on a que l'algorithme de décomposition stochastique génère une suite de stratégies qui converge vers la stratégie optimale du problème (3.7).”

• cites Ekeland et Temam (1999)Not checked yet

  Not checked in the free run.

• cites Cohen (2004)Not checked yet

  Not checked in the free run.

• AssumptionThe authors state this as an assumption: The objective is convex with Lipschitz gradient and the dynamics are linear for convergence of the price decomposition algorithm.

For a hydro plant, the relationship between turbined water and electricity production depends non-convexly on lake stock through the head effect: more water above the turbine yields greater power.

“le lien entre turbiné et production électrique pour une centrale hydraulique fait également intervenir le stock du lac, ceci de manière non-convexe : c'est le phénomène physique de hauteur de chute qui fait que la puissance produite est d'autant plus importante qu'il y a d'eau au-dessus de la turbine.”

Because the state dimension is relatively large, the dynamic programming equation cannot be solved in practice by brute discretization of the state space.

“Du fait de la relative grande dimension de l'état, il n'est pas possible de résoudre cette équation en pratique à l'aide d'une discrétisation brutale de l'espace d'état.”

The general electricity portfolio management problem is usually set over a multi-year horizon because some decisions, such as nuclear refueling, must be made several years in advance.

“Le problème se pose généralement sur un horizon pluri-annuel, du fait que certaines décisions, telles que le rechargement en combustible des centrales nucléaires, doit être décidé plusieurs années à l'avance.”

The absence of price dynamics prevents writing a dynamic programming equation in a reasonable dimension.

“De plus, le fait que nous n'ayons pas à notre disposition de dynamique sur le prix nous empêche d'écrire une équation de programmation dynamique en dimension raisonnable”

The paper shows how to implement DADP for systems composed of small subsystems that do not directly influence each other but are coupled by a global constraint such as production-demand balance.

“Nous montrons comment mettre en œuvre cette méthodologie pour des systèmes composés de sous-systèmes de petite taille ne s'influençant pas directement les uns et les autres, mais couplés entre eux par une contrainte globale, telle que la satisfaction d'un équilibre entre productions et demande.”

Lemma 5.2: if the model is exact, meaning the perturbations are identically zero, then problems (5.2) with initial conditions x_ti = x^#_ti are dynamically consistent.

“Dans le cas où le modèle est exact, c'est-à-dire si les perturbations ε t i introduites plus haut sont identiquement nulles, les problèmes (5.2) avec comme conditions initiales x t i = x ♯ t i := f t i (x ♯ t i-1 , u ♯ t 0 ,t i-1 ) sont consistants dynamiquement.”

Lemma 5.1: if the solutions of problems (5.1) and (5.2) for t_i = t_1,...,T-1 are independent of initial conditions, then the sequence of problems is dynamically consistent.

“Dans le cas très particulier où les solutions des problèmes (5.1) et (5.2) pour t i = t 1 , . . ., T -1 sont indépendantes des conditions initiales, la suite de problèmes est consistante dynamiquement.”

In many cases, the sequence of optimization problems is dynamically consistent provided decisions are based on sufficient information.

“dans nombre de cas, la suite de problèmes d'optimisation est dynamiquement consistante pourvu qu'on base les décisions sur une information suffisante.”

The present stochastic case is closer to the framework of Lemma 5.1 than to that of Lemma 5.3.

“le cas présent est plus proche du cadre du lemme 5.1 que de celui du lemme 5.3.”

Dynamic consistency is preserved if strategies depend on sufficient information.

“la consistance dynamique est préservée si on prend soin de considérer des stratégies dépendant d'une information suffisante.”

The solutions of the problem with an expectation constraint depend on the initial condition X_{t0} as a random variable.

“Il faut être conscient du fait que les solutions dépendent maintenant de la condition initiale X t 0 en tant que variable aléatoire.”

• AssumptionThe authors state this as an assumption: There exists a solution to the problem at the first instant.

Unforeseen perturbations affecting the system introduce inconsistency into the sequence of decision problems: optimal decisions from the first time step are no longer optimal when the problem is reposed later.

“il semble que les perturbations (imprévues) qui affectent le système apportent de l'inconsistance à la suite de problèmes de décisions : les décisions optimales vues du premier pas de temps ne le sont plus lorsque l'on pose à nouveau le problème à un instant ultérieur.”

Lemma 5.1 does not apply in general.

“le Lemme 5.1 ne s'applique pas en général.”

By lemma 5.1, problems (5.4) are dynamically consistent when controls are sought as feedbacks on X_t.

“Ainsi, de par le lemme 5.1, les problèmes (5.4) sont naturellement consistants dynamiquement lorsque les commandes sont cherchées en feedback sur X t .”

• cites lemme 5.1Not checked yet

  Not checked in the free run.

Lemma 5.3: if problem (5.1) is solved by dynamic programming, yielding optimal feedback strategies on x, then problems (5.2) are dynamically consistent for t = t0,...,T-1.

“Supposons que nous résolvions le problème (5.1) par programmation dynamique, obtenant ainsi une suite de stratégies optimales Φ ♯ t 0 ,t 0 , . . ., Φ ♯ t 0 ,T -1 en feedback sur la variable x.Alors les problèmes (5.2) sont consistants dynamiquement pour t = t 0 , . . ., T -1.”

Under Hypothesis 5.4, optimal strategies can be obtained by solving the dynamic programming equation.

“les stratégies optimales Φ ♯ t 0 ,t 0 , . . ., Φ ♯ t 0 ,T -1 peuvent être obtenues par résolution de l'équation de programmation dynamique.”

• cites Bertsekas, 2000Not checked yet

  Not checked in the free run.

• AssumptionThe authors state this as an assumption: The random variables X_t0, W_t1, ..., W_T are independent of one another.

The whitening procedure preserves the perfect information property for the problem considered.

“cette procédure conserve, pour notre problème, la propriété d'information parfaite.”

Optimal strategies from the dynamic programming equation remain optimal for later problems.

“les stratégies optimales Φ ♯ t 0 ,t 0 , . . ., Φ ♯ t 0 ,T -1 issues de la résolution de l'équation de programmation dynamique restent optimales pour les problèmes aux instants ultérieurs”

• AssumptionThe authors state this as an assumption: The random variables X_t0, W_t1, ..., W_T are independent of one another.

Unlike the no-risk-constraint case, there is no reason that the feedbacks do not depend on the initial condition.

“Il n'y a donc aucune raison que les feedbacks ne dépendent pas de la condition initiale, comme c'était le cas au §5.2.2.”

With almost-sure constraints, dynamic consistency is preserved.

“Il y a donc consistance dynamique.”

The whitening procedure at most requires including all past noise in variable X.

“Cette procédure de blanchiment fait qu'au plus, c'est-à-dire si W t+1 dépend de tout la passé du bruit, on devra inclure tout le passé du bruit dans la variable X.”

Under Hypothesis 5.4, there is no loss of optimality in seeking the control at time t as a feedback function on X_t.

“il n'y pas de perte d'optimalité à rechercher la commande U t à l'instant t sous la forme d'une fonction en feedback sur la variable X t”

• cites Bertsekas, 2000Not checked yet

  Not checked in the free run.

• AssumptionThe authors state this as an assumption: The random variables X_t0, W_t1, ..., W_T are independent of one another.

The main difficulty of the electricity production stock management problem in dynamic programming is the number of reserves, here 7, which prevents direct numerical resolution of the dynamic programming equation.

“La difficulté principale de ce problème, dans le contexte de la programmation dynamique, est le nombre de réserves, ici 7, qui empêche la résolution numérique directe de l'équation de programmation dynamique.”

The dualized constraint is satisfied only conditionally on the chosen information variable.

“la contrainte que nous dualisons ne serait satisfaite, à l'issue de la mise en œuvre de l'algorithme, que conditionnellement à la variable d'information choisie.”

Almost-sure constraints do not change the nature of the optimization problem.

“Les contraintes presque-sûres sont bien étudiées et on sait qu'elles ne modifient pas la nature du problème d'optimisation.”

The class of problems that can be formulated as problem (5.3) is a relatively particular case of stochastic optimal control.

“Il semble donc que la classe de problèmes (assez générale) pouvant être formulés à la manière du problème (5.3) est en fait un cas relativement particulier de problème de commande optimale stochastique.”

Applying the dynamic programming principle to problem (5.7) is not direct, mainly because of the added constraints (5.7h).

“L'application du principe de programmation dynamique à ce problème n'est pas directe ; la raison principale est l'ajout des contraintes (5.7h).”

• AssumptionThe authors state this as an assumption: The quantities defined in the paper exist.

Bouchard, Elie, and Touzi (2009) propose to replace the expectation constraint (5.6) by an almost-sure constraint by adding an extra control and state.

“Nous reprenons dans la cadre du temps discret les résultats de Bouchard, Elie, et Touzi (2009), qui proposent de remplacer, via l'ajout d'une commande et d'un état supplémentaires, la contrainte en espérance (5.6) par une contrainte presque-sûre.”

• cites Bouchard, Elie, et Touzi (2009)Not checked yet

  Not checked in the free run.

There exists a smaller, even finite-dimensional, state for the problem.

“nous montrons maintenant qu'il existe un état de plus petite taille (et même de dimension finie) pour le problème.”

The defect of scenario trees is not due to the use of scenarios but to discretization as trees of randomness, which does not seem to be the right way to approximate conditional expectations.

“le défaut des arbres de scénarios n'est pas à imputer à l'usage de scénarios mais plutôt à la discrétisation sous forme d'arbres d'aléas, qui ne semble pas être la bonne manière d'approcher des espérances conditionnelles.”

The family of problems under an expectation constraint is dynamically consistent when strategies are sought as functions of X_t and the probability law of X_t.

“la famille de problèmes sous contrainte en espérance est consistante dynamiquement dès lors que l'on cherche les stratégies comme des fonctions de la variable X t et de la loi de probabilité de X t .”

• AssumptionThe authors state this as an assumption: The initial condition of each problem is given by a Dirac distribution.

If Z_T is chosen large for difficult scenarios, one must compensate by imposing a small Z_T for another set of scenarios.

“Autrement dit, si on choisit effectivement une valeur de Z T grande pour les scénarios”

• AssumptionThe authors state this as an assumption: The quantities defined in the paper exist.

Constraints (5.7e) and (5.7h), through the control variable V_t, ensure that the expectation constraint (5.6) of the original problem is satisfied.

“Les contraintes (5.7e) et (5.7h), à l'aide de la variable de commande V t , permettent d'assurer que l'équilibre, c'est-à-dire la contrainte en espérance (5.6) du problème de départ, soit satisfaite.”

• AssumptionThe authors state this as an assumption: The quantities defined in the paper exist.

The DADP algorithm generalizes the works of Strugarek (2006, Chapter 5) and Barty and Roy (2007).

“L'algorithme Dual Approximate Dynamic Programming (DADP) que nous introduisons ici généralise en quelque sorte ces travaux.”

• cites Strugarek (2006, Chapitre 5)Not checked yet

  Not checked in the free run.

• cites Barty et Roy (2007)Not checked yet

  Not checked in the free run.

The optimal control obtained for problem (5.7) satisfies dynamic consistency for the family of problems formulated from (5.7) at different t0 because it is independent of the probability law of the state.

“le contrôle optimal ainsi obtenu satisfait naturellement la propriété de consistance dynamique pour la famille des problèmes formulés à partir de (5.7) pour les différents instants t 0 , car ce contrôle est indépendant de la loi de probabilité de l'état.”

It is often possible to recover dynamic consistency at the cost of increasing the state and the control.

“Cependant, nous avons montré qu'il était souvent possible de retrouver la propriété de consistance dynamique au prix d'une augmentation de l'état et de la commande.”

In the convex case, duality arguments show that the optimal feedback depends only on (X,W), not on W.

“Par contre, dans le cas convexe, on montre facilement par des arguments de type dualité que le feedback optimal ne dépend que du couple (X, W ), et pas de W .”

For a large class of stochastic optimal control problems, dynamic consistency can be obtained by modifying the state structure of the system.

“pour une large classe de problèmes de commande optimale stochastique, la propriété de consistance dynamique peut être obtenue quitte à modifier la structure d'état du système.”

Under lemma 5.2, optimization problems at later times are dynamically consistent if their initial condition is given by the law from the optimal Fokker-Planck equation.

“Selon le lemme 5.2, les problèmes d'optimisation formulés aux pas de temps ultérieurs, disons t i , sont consistants dynamiquement si leur condition initiale est donnée par la loi provenant de l'équation de Fokker-Planck optimale”

• cites lemme 5.2Not checked yet

  Not checked in the free run.

Therefore, the sequence of problems is not dynamically consistent if feedbacks Φ_t depend only on X_t.

“Ainsi, la suite de problèmes n'est pas consistante dynamiquement si on considère des feedbacks Φ t dépendant uniquement de X t .”

• AssumptionThe authors state this as an assumption: The initial condition of each problem is given by a Dirac distribution.

In the non-convex case, examples can be constructed where the feedback's dependence on W is effective.

“On peut construire, dans le cas non convexe, des exemples où la dépendance du feedback en W est effective.”