Inexact Stochastic Mirror Descent for two-stage nonlinear stochastic programs

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

Multistage stochastic programs with a random number of stages: dynamic programming equations, solution methods, and application to portfolio selection

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

Inexact cuts in Deterministic and Stochastic Dual Dynamic Programming applied to linear optimization problems

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

DASC: a Decomposition Algorithm for multistage stochastic programs with Strongly Convex cost functions

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

Inexact cuts for Deterministic and Stochastic Dual Dynamic Programming applied to convex nonlinear optimization problems

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

Multicut decomposition methods with cut selection for multistage stochastic programs

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

Dual Dynamic Programming with cut selection: convergence proof and numerical experiments

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

Regularized Stochastic Dual Dynamic Programming for convex nonlinear optimization problems

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

Statistical inference and hypotheses testing of risk averse stochastic programs

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

Statistical inference and hypotheses testing of risk averse stochastic programs

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