Skip to Main content Skip to Navigation

Contributions to decomposition methods in stochastic optimization

Abstract : Stochastic optimal control addresses sequential decision-making under uncertainty. As applications leads to large-size optimization problems, we count on decomposition methods to tackle their mathematical analysis and their numerical resolution. We distinguish two forms of decomposition. In chained decomposition, like Dynamic Programming, the original problemis solved by means of successive smaller subproblems, solved one after theother. In parallel decomposition, like Progressive Hedging, the original problemis solved by means of parallel smaller subproblems, coordinated and updated by amaster algorithm. In the first part of this manuscript, Dynamic Programming: Risk and Convexity, we focus on chained decomposition; we address the well known time decomposition that constitutes Dynamic Programming with two questions. In Chapter 2, we extend the traditional additive in time and risk neutral setting to more general ones for which we establish time-consistency. In Chapter 3, we prove a convergence result for the Stochastic Dual Dynamic Programming Algorithm in the case where (convex) cost functions are no longer polyhedral. Then, we turn to parallel decomposition, especially decomposition methods obtained by dualizing constraints (spatial or non-anticipative). In the second part of this manuscript, Duality in Stochastic Optimization, we first point out that such constraints lead to delicate duality issues (Chapter 4).We establish a duality result in the pairing Bp{L∞,L¹} in Chapter 5. Finally, in Chapter 6, we prove the convergence of the Uzawa Algorithm in L∞(Ω,F,ℙ;ℝ^n). The third part of this manuscript, Stochastic Spatial Decomposition Methods, is devoted to the so-called Dual Approximate Dynamic Programming Algorithm. In Chapter 7, we prove that a sequence of relaxed optimization problems epiconverges to the original one, where almost sure constraints are replaced by weaker conditional expectation ones and that corresponding σ-fields converge. In Chapter 8, we give theoretical foundations and interpretations to the Dual Approximate Dynamic Programming Algorithm
Document type :
Complete list of metadata

Cited literature [119 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Monday, May 4, 2015 - 4:22:09 PM
Last modification on : Thursday, June 3, 2021 - 3:16:18 AM
Long-term archiving on: : Wednesday, April 19, 2017 - 3:19:34 PM


Version validated by the jury (STAR)


  • HAL Id : tel-01148466, version 1



Vincent Leclere. Contributions to decomposition methods in stochastic optimization. General Mathematics [math.GM]. Université Paris-Est, 2014. English. ⟨NNT : 2014PEST1092⟩. ⟨tel-01148466⟩



Record views


Files downloads