## Convergence of Trajectory Following Dynamic Programming algorithms for multistage stochastic problems without finite support assumptions

We introduce a class of algorithms, called Trajectory Following Dynamic Programming (TFDP) algorithms, that iteratively refines approximation of cost-to-go functions of multistage stochastic problems with independent random variables. This framework encompasses most variants of the Stochastic Dual Dynamic Programming algorithm. Leveraging a Lipschitz assumption on the expected cost-to-go functions, we provide a new convergence and … Read more

## Risk-Averse Stochastic Optimal Control: an efficiently computable statistical upper bound

In this paper, we discuss an application of the SDDP type algorithm to nested risk-averse formulations of Stochastic Optimal Control (SOC) problems. We propose a construction of a statistical upper bound for the optimal value of risk-averse SOC problems. This outlines an approach to a solution of a long standing problem in that area of … Read more

## Dual SDDP for risk-averse multistage stochastic programs

Risk-averse multistage stochastic programs appear in multiple areas and are challenging to solve. Stochastic Dual Dynamic Programming (SDDP) is a well known tool to address such problems under time-independence assumptions. We show how to derive a dual formulation for these problems and apply an SDDP algorithm, leading to converging and deterministic upper bounds for risk-averse … Read more

## Batch Learning in Stochastic Dual Dynamic Programming

We consider the stochastic dual dynamic programming (SDDP) algorithm, which is a widely employed algorithm applied to multistage stochastic programming, and propose a variant using batch learning, a technique used with success in the reinforcement learning framework. We cast SDDP as a type of Q-learning algorithm and describe its application in both risk neutral and … Read more

## Stochastic Dual Dynamic Programming for Multistage Stochastic Mixed-Integer Nonlinear Optimization

In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with \emph{non-Lipschitz-continuous} value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient … Read more

## Inexact cuts in Stochastic Dual Dynamic Programming

We introduce an extension of Stochastic Dual Dynamic Programming (SDDP) to solve stochastic convex dynamic programming equations. This extension applies when some or all primal and dual subproblems to be solved along the forward and backward passes of the method are solved with bounded errors (inexactly). This inexact variant of SDDP is described both for … Read more

## Stochastic dual dynamic programming with stagewise dependent objective uncertainty

We present a new algorithm for solving linear multistage stochastic programming problems with objective function coefficients modeled as a stochastic process. This algorithm overcomes the difficulties of existing methods which require discretization. Using an argument based on the finiteness of the set of possible cuts, we prove that the algorithm converges almost surely. Finally, we … Read more

## A deterministic algorithm for solving stochastic minimax dynamic programmes

In this paper, we present an algorithm for solving stochastic minimax dynamic programmes where state and action sets are convex and compact. A feature of the formulations studied is the simultaneous non-rectangularity of both min’ and max’ feasibility sets. We begin by presenting convex programming upper and lower bound representations of saddle functions — extending … Read more

## A deterministic algorithm for solving multistage stochastic programming problems

Multistage stochastic programming problems are an important class of optimisation problems, especially in energy planning and scheduling. These problems and their solution methods have been of particular interest to researchers in stochastic programming recently. Because of the large scenario trees that these problems induce, current solution methods require random sampling of the tree in order … Read more

## A note on the convergence of the SDDP algorithm

In this paper we are interested in the convergence analysis of the Stochastic Dual Dynamic Algorithm (SDDP) algorithm in a general framework, and regardless of whether the underlying probability space is discrete or not. We consider a convex stochastic control program not necessarily linear and the resulting dynamic programming equation. We prove under mild assumptions … Read more