Vincent Guigues We introduce an inexact variant of Stochastic Mirror Descent (SMD), called Inexact Stochastic Mirror Descent (ISMD), to solve nonlinear two-stage stochastic programs where the second stage problem has linear and nonlinear coupling constraints and a nonlinear objective function which depends on both first and second stage decisions. Given a candidate first stage solution and a … Read more
We introduce the class of multistage stochastic optimization problems with a random number of stages. For such problems, we show how to write dynamic programming equations and detail the Stochastic Dual Dynamic Programming algorithm to solve these equations. Finally, we consider a portfolio selection problem over an optimization period of random duration. For several instances … Read more
We introduce an extension of Dual Dynamic Programming (DDP) to solve linear dynamic programming equations. We call this extension IDDP-LP which applies to situations where some or all primal and dual subproblems to be solved along the iterations of the method are solved with a bounded error (inexactly). We provide convergence theorems both in the … Read more
We introduce DASC, a decomposition method akin to Stochastic Dual Dynamic Programming (SDDP) which solves some multistage stochastic optimization problems having strongly convex cost functions. Similarly to SDDP, DASC approximates cost-to-go functions by a maximum of lower bounding functions called cuts. However, contrary to SDDP, the cuts computed with DASC are quadratic functions. We also … Read more
We introduce an extension of Dual Dynamic Programming (DDP) to solve convex nonlinear dynamic programming equations. We call Inexact DDP (IDDP) this extension which applies to situations where some or all primal and dual subproblems to be solved along the iterations of the method are solved with a bounded error. We show that any accumulation … Read more
We consider convex optimization problems formulated using dynamic programming equations. Such problems can be solved using the Dual Dynamic Programming algorithm combined with the Level 1 cut selection strategy or the Territory algorithm to select the most relevant Benders cuts. We propose a limited memory variant of Level 1 and show the convergence of DDP … Read more
We introduce a variant of Multicut Decomposition Algorithms (MuDA), called CuSMuDA (Cut Selection for Multicut Decomposition Algorithms), for solving multistage stochastic linear programs that incorporates strategies to select the most relevant cuts of the approximate recourse functions. We prove the convergence of the method in a finite number of iterations and use it to solve … Read more
We define a regularized variant of the Dual Dynamic Programming algorithm called REDDP (REgularized Dual Dynamic Programming) to solve nonlinear dynamic programming equations. We extend the algorithm to solve nonlinear stochastic dynamic programming equations. The corresponding algorithm, called SDDP-REG, can be seen as an extension of a regularization of the Stochastic Dual Dynamic Programming (SDDP) … Read more
We study statistical properties of the optimal value and optimal solutions of the Sample Average Approximation of risk averse stochastic problems. Central Limit Theorem type results are derived for the optimal value when the stochastic program is expressed in terms of a law invariant coherent risk measure having a discrete Kusuoka representation. The obtained results … Read more
We study statistical properties of the optimal value and optimal solutions of the Sample Average Approximation of risk averse stochastic problems. Central Limit Theorem type results are derived for the optimal value and optimal solutions when the stochastic program is expressed in terms of a law invariant coherent risk measure. The obtained results are applied … Read more