Analysis of stochastic dual dynamic programming method

Abstract

In this paper we discuss statistical properties and convergence of the Stochastic Dual Dynamic Programming (SDDP) method applied to multistage linear stochastic programming problems. We assume that the underline data process is stagewise independent and consider the framework where at first a random sample from the original (true) distribution is generated and consequently the SDDP algorithm is applied to the constructed Sample Average Approximation (SAA) problem. Then we proceed to analysis of the SDDP solutions of the SAA problem and their relations to solutions of the “true” problem. Finally we discuss an extension of the SDDP method to a risk averse formulation of multistage stochastic programs. We argue that the computational complexity of the corresponding SDDP algorithm is almost the same as in the risk neutral case.

Introduction

The goal of this paper is to analyze convergence properties of the Stochastic Dual Dynamic Programming (SDDP) approach to solve linear multistage stochastic programming problems of the form

$$\underset{{\displaystyle \genfrac{}{}{0ex}{}{A_1{x}_1=b_1}{x_1⩾0}}}{\text{Min}}{c}_1^{\mathsf{T}}{x}_1+\mathbb{E}\left[\underset{{\displaystyle \genfrac{}{}{0ex}{}{B_2{x}_1+A_2{x}_2=b_2}{x_2⩾0}}}{\min }{c}_2^{\mathsf{T}}{x}_2+\mathbb{E}\left[\cdots +\mathbb{E}\left[\underset{{\displaystyle \genfrac{}{}{0ex}{}{B_T{x}_{T-1}+A_T{x}_T=b_T}{x_T⩾0}}}{\min }{c}_T^{\mathsf{T}}{x}_T\right]\right]\right]\text{.}$$

Components of vectors c_t, b_t and matrices A_t, B_t are modeled as random variables forming the stochastic data process¹ ξ_t = (c_t, A_t, B_t, b_t), t = 2, … , T, with ξ₁ = (c₁, A₁, b₁) being deterministic (not random). By ξ_[t] = (ξ₁, … , ξ_t) we denote history of the data process up to time t. The SDDP method originated in Pereira and Pinto [11], and was extended and analyzed in several publications (e.g., [2], [4], [7], [12]). It was assumed in those publications that the number of realizations (scenarios) of the data process is finite, and this assumption was essential in the implementations and analysis of the SDDP type algorithms. In many applications, however, this assumption is quite unrealistic. In forecasting models (such as ARIMA) the errors are typically modeled as having continuous (say normal or log-normal) distributions. So one of the relevant questions is what is the meaning of the introduced discretizations of the corresponding stochastic process. Related questions are convergence properties and error analysis of the method.

We make the basic assumption that the random data process is stagewise independent, i.e., random vector ξ_t+1 is independent of ξ_[t] = (ξ₁, … , ξ_t) for t = 1, … , T − 1. In some cases across stages dependence can be dealt with by adding state variables to the model. For example, suppose that parameters of the data process ξ_t other than b_t are stagewise independent (in particular are deterministic) and random vectors b_t, t = 2, … , T, form a first order autoregressive process, i.e., b_t = Φb_t−1 + ε_t, with appropriate matrix Φ and error vectors ε₂, … , ε_T being independent of each other. Then the feasibility equations of problem (1.1) can be written as

$$b_t-\Phi b_{t-1}={\epsilon }_t\text{,}{B}_t{x}_{t-1}-\Phi b_{t-1}+A_t{x}_t={\epsilon }_t\text{,}{x}_t⩾0\text{,}t=2\text{,}\dots \text{,}T\text{.}$$

Therefore by replacing x_t with (x_t, b_t) and data process with (c_t, A_t, B_t, ε_t), t = 2, … , T, we transform the problem to the stagewise independent case. Of course, in this new formulation we do not need to enforce nonnegativity of the state variables b_t.

We also assume that the implementation is performed in two steps. First, a (finite) scenario tree is generated by randomly sampling from the original distribution and then the constructed problem is solved by the SDDP algorithm. A current opinion is that the approach of random generation of scenarios (the so-called Sample Average Approximation (SAA) method) is computationally intractable for solving multistage stochastic programs because of the exponential growth of the number of scenarios with increase of the number of stages (cf., [18], [19]). An interesting property of the SDDP method is that the computational complexity of one run of the involved backward and forward step procedures is proportional to the sum of sampled data points at every stage and not to the total number of scenarios given by their product. This makes it computationally feasible to run several such backward and forward steps. Of course, this still does not give a proof of computational tractability of the true multistage problem. It also should be remembered that this nice property holds because of the stagewise independence assumption.

We also discuss an extension of the SDDP method to a risk averse formulation of multistage stochastic programs. We argue that the computational complexity of the corresponding SDDP algorithm is almost the same as in the risk neutral case.

In order to present some basic ideas we start our analysis in the next section with two-stage linear stochastic programming problems. For a discussion of basic theoretical properties of two and multi-stage stochastic programs we may refer to [21]. In Section 3 we describe the SDDP approach, based on approximation of the dynamic programming equations, applied to the SAA problem. A risk averse extension of this approach is discussed in Section 4. Finally, Section 5 is devoted to a somewhat informal discussion of this methodology.

We use the following notations and terminology throughout the paper. The notation “≔” means “equal by definition”. For $a\in \mathbb{R}$, [a]₊≔max{0, a}. By ∣J∣ we denote cardinality of a finite set J. By A^T we denote transpose of matrix (vector) A. For a random variable Z, $\mathbb{E}[Z]$ and Var[Z] denote its expectation and variance, respectively. Pr(·) denotes probability of the corresponding event. Given a convex function Q(x) we denote by ∂Q(x) its subdifferential, i.e., the set of all its subgradients, at point $x\in {\mathbb{R}}^n$. It is said that an affine function ℓ(x) = a + b^Tx is a cutting plane, of Q(x), if Q(x) ⩾ ℓ(x) for all $x\in {\mathbb{R}}^n$. Note that cutting plane ℓ(x) can be strictly smaller than Q(x) for all $x\in {\mathbb{R}}^n$. If, moreover, $Q(\overline{x})=\ell (\overline{x})$ for some $\overline{x}\in {\mathbb{R}}^n$, it is said that ℓ(x) is a supporting plane of Q(x). This supporting plane is given by $\ell (x)=Q(\overline{x})+g^{\mathsf{T}}(x-\overline{x})$ for some subgradient $g\in \partial Q(\overline{x})$.