Combining stochastic programming and optimal control to decompose multistage stochastic optimization problems

Abstract

The paper suggests a possible cooperation between stochastic programming and optimal control for the solution of multistage stochastic optimization problems. We propose a decomposition approach for a class of multistage stochastic programming problems in arborescent form (i.e. formulated with implicit non-anticipativity constraints on a scenario tree). The objective function of the problem can be either linear or nonlinear, while we require that the constraints are linear and involve only variables from two adjacent periods (current and lag 1). The approach is built on the following steps. First, reformulate the stochastic programming problem into an optimal control one. Second, apply a discrete version of Pontryagin maximum principle to obtain optimality conditions. Third, discuss and rearrange these conditions to obtain a decomposition that acts both at a time stage level and at a nodal level. To obtain the solution of the original problem we aggregate the solutions of subproblems through an enhanced mean valued fixed point iterative scheme.

Appendix

This “Appendix‘’ provides proofs to the results not proven in the paper.

1.1 Proposition 3.1

Proof

Assumptions A1-1 and A1-2 define the state and control variables for each node in the tree. The state variables, x(t), and control variables, u(t), at time t in the OC problem, are defined as the collections of all states and control variables related to nodes at time t in the scenario tree as follows:

$$\begin{aligned} x(0)= & {} ( \begin{array}{c} x_{k_0} \\ \end{array} ) \quad x(t)=\left( \begin{array}{c} x_{K_{t-1}+1} \\ \vdots \\ x_{K_t}\\ \end{array} \right) \ \ t=1,\ldots ,T \quad x(T+1)=\left( \begin{array}{c} x_{K_{T}+1} \\ \vdots \\ x_{K_{T+1}}\\ \end{array} \right) \\ u(0)= & {} ( \begin{array}{c} u_{k_0} \\ \end{array} ) \quad u(t)=\left( \begin{array}{c} u_{K_{t-1}+1} \\ \vdots \\ u_{K_t}\\ \end{array} \right) \quad t=1,\ldots ,T. \end{aligned}$$

Assumption A1-4 defines the objective function (7a) for the OC problem. In what follows we provide the construction of the matrices and vectors of coefficients in the constraints of the OC problem.

For each node $k_t$ we define a matrix $B^*_{k_t}$ as the collection of all matrices $B_{i}$, where $i=1,\ldots ,D(k_t)$ denotes the descendant nodes from node $k_t$:

$$\begin{aligned}&B^*_{k_t}=\left( \begin{array}{c} B_{1} \\ \vdots \\ B_{D(k_t)} \\ \end{array} \right) . \end{aligned}$$

(27)

The matrices and vector of coefficients in (7b) are defined as follows

$$\begin{aligned} A(t)\equiv & {} 0 \quad q(t) \equiv 0 \quad \forall t=0,1,\ldots ,T-1 \end{aligned}$$

(28a)

$$\begin{aligned} B(0)= & {} \left( \begin{array}{c} B_{k_1} \\ \vdots \\ B_{K_1} \\ \end{array} \right) \end{aligned}$$

(28b)

$$\begin{aligned} B(t)= & {} \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} B^*_{K_{t-1}+1} &{} 0 &{} \ldots &{} 0\\ 0 &{} B^*_{K_{t-1}+2} &{} \ldots &{} 0 \\ 0 &{} 0 &{} \ddots &{} 0 \\ 0 &{} 0 &{} \ldots &{} B^*_{K_t} \end{array} \right) \quad t=1,\ldots ,T-1 \end{aligned}$$

(28c)

$$\begin{aligned} B(T)= & {} \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} A_{K_{T-1}+1} &{} 0 &{}\ldots &{} 0\\ 0 &{} A_{K_{T-1}+2} &{} \ldots &{} 0 \\ 0 &{} 0 &{} \ddots &{} 0 \\ 0 &{} 0 &{} \ldots &{} A_{K_T} \end{array} \right) . \end{aligned}$$

(28d)

The initial condition on the state variables, Eq. (7c), does not affect subsequent stages and can be defined in an arbitrary way.

Let us define, for each node $k_t$, the matrices $C_{k_t}$ and $D_{k_t}$

$$\begin{aligned}&C_{k_t}=\left( \begin{array}{c@{\quad }c} I &{} 0 \\ 0 &{} -I \end{array} \right) \quad \text {and} \quad D_{k_t}=\left( \begin{array}{c@{\quad }c} A_{k_t} &{} 0 \\ 0 &{} -A_{k_t} \end{array} \right) \end{aligned}$$

(29)

where I denotes the identity matrix with dimension determined by the dimension of the vector $x_{k_t}$, and $A_{k_t}$ are the matrices from constraints (2d).

Using assumption A1-3 and the position in (29), the matrices C(t) and D(t) in (7d), for all t, are defined as: s

$$\begin{aligned} C(t)= & {} \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} C_{K_{t-1}+1} &{} 0 &{} \ldots &{} 0\\ 0 &{} C_{K_{t-1}+2} &{} \ldots &{} 0 \\ 0 &{} 0 &{}\ddots &{} 0 \\ 0 &{} 0 &{} 0 &{} C_{K_{t}} \end{array} \right) \end{aligned}$$

(30a)

$$\begin{aligned} D(t)= & {} \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} D_{K_{t-1}+1} &{} 0 &{} \ldots &{} 0\\ 0 &{} D_{K_{t-1}+2} &{} \ldots &{} 0 \\ 0 &{} 0 &{}\ddots &{} 0 \\ 0 &{} 0 &{} 0 &{} D_{K_{t}} \end{array} \right) \end{aligned}$$

(30b)

while the vectors r(t), for all t, are

$$\begin{aligned}&r(t)= \left( \begin{array}{c} c_{K_{t-1}+1} \\ -c_{K_{t-1}+1} \\ \vdots \\ c_{K_{t}} \\ -c_{K_{t}} \end{array} \right) . \end{aligned}$$

(31)

Non-negativity conditions on u(t), Eq. (7e), are a direct consequence of (2f) and assumption A1-1. $\square$

1.2 Proposition 3.2

Proof

Assumptions A2-1 and A2-2 define the state and control variables for each node in the tree. The state variables, x(t), and control variables, u(t), at time t in the OC problem, are defined as the collections of all states and control variables related to nodes at time t in the scenario tree as follows:

$$\begin{aligned} x(0)= & {} \left( \begin{array}{c} x_{k_0} \\ \end{array} \right) \quad x(t)=\left( \begin{array}{c} x_{K_{t-1}+1} \\ \vdots \\ x_{K_t}\\ \end{array} \right) \quad t=1,\ldots ,T \\ u(0)= & {} \left( \begin{array}{c} u_{k_0} \\ \end{array} \right) \quad u(t)=\left( \begin{array}{c} u_{K_{t-1}+1} \\ \vdots \\ u_{K_t}\\ \end{array} \right) \quad t=1,\ldots ,T-1. \end{aligned}$$

Assumption A2-4 defines the objective function (3a) for the OC problem. In what follows we provide the construction of the matrices and vectors of coefficients in the constraints of the OC problem.

Under assumptions A2-1–A2-2, the general constraints for node $k_t$ of the stochastic programming problem

$$\begin{aligned}&B_{k_t}z_{b(k_t)}+A_{k_t}z_{k_t}=c_{k_t} \end{aligned}$$

(32)

can be rewritten as

$$\begin{aligned}&x_{k_t}= (A^s_{k_t})^{-1}[-B^s_{k_t}x_{b(k_t)}-B^c_{k_t}u_{b(k_t)}+c_{k_t}] \end{aligned}$$

(33)

which represents the dynamics of the state variables in the optimal control framework.

Recall that $d_i(k_t), i=1,\ldots ,D(k_t)$ denotes the descendant nodes from node $k_t$. We define, for all $k_t=k_0,k_1,\ldots , K_{T-1}$, the matrices $A^*_{k_t}$, $B^*_{k_t}$ and the vector $q^*_{k_t}$, as follows

$$\begin{aligned} A^*_{k_t}= & {} \left( \begin{array}{c} -(A_{1}^s)^{-1}B_{1}^{s} \\ \vdots \\ -(A_{D(k_t)}^s)^{-1}B_{D(k_t)}^{s} \\ \end{array} \right) \end{aligned}$$

(34a)

$$\begin{aligned} B^*_{k_t}= & {} \left( \begin{array}{c} -(A_{1}^s)^{-1}B_{1}^{c} \\ \vdots \\ -(A_{D(k_t)}^s)^{-1}B_{D(k_t)}^{c} \\ \end{array} \right) \end{aligned}$$

(34b)

$$\begin{aligned} q^*_{k_t}= & {} \left( \begin{array}{c} (A_{1}^s)^{-1}c_{1} \\ \vdots \\ (A_{D(k_t)}^s)^{-1}c_{D(k_t)} \\ \end{array} \right) . \end{aligned}$$

(34c)

The matrices and vector of coefficients in (3b) are defined as follows

$$\begin{aligned} A(0)= & {} A^*_{k_0}\quad \ B(0)=B^*_{k_0} \quad q(0)=q^*_{k_0} \end{aligned}$$

(35a)

$$\begin{aligned} A(t)= & {} \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} A^*_{K_{t-1}+1} &{} 0 &{} \ldots &{} 0\\ 0 &{} A^*_{K_{t-1}+2} &{} \ldots &{} 0 \\ 0 &{} 0 &{} \ddots &{} 0 \\ 0 &{} 0 &{} \ldots &{} A^*_{K_t} \end{array} \right) \quad t=1,\ldots , T-1 \end{aligned}$$

(35b)

$$\begin{aligned} B(t)= & {} \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} B^*_{K_{t-1}+1} &{} 0 &{}\ldots &{} 0\\ 0 &{} B^*_{K_{t-1}+2} &{} \ldots &{} 0 \\ 0 &{} 0 &{} \ddots &{} 0 \\ 0 &{} 0 &{} \ldots &{} B^*_{K_t} \end{array} \right) \quad t=1,\ldots , T-1\end{aligned}$$

(35c)

$$\begin{aligned} q(t)= & {} \left( \begin{array}{c} q^*_{K_{t-1}+1} \\ \vdots \\ q^*_{K_t} \end{array} \right) \quad t=1,\ldots , T-1. \end{aligned}$$

(35d)

The initial condition on the state variables, Eq. (3c), are obtained from (2b) using assumption A2-1.

Using assumption A2-3, the matrices C(t), D(t) and the vector r(t) of coefficients in the constraints (3d) are defined as

$$\begin{aligned} C(0)= & {} A^*_{k_0}\quad \ D(0)=B^*_{k_0} \quad r(0)=q^*_{k_0} \end{aligned}$$

(36a)

$$\begin{aligned} C(t)= & {} \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} A^*_{K_{t-1}+1} &{} 0 &{} \ldots &{} 0\\ 0 &{} A^*_{K_{t-1}+2} &{} \ldots &{} 0 \\ 0 &{} 0 &{} \ddots &{} 0 \\ 0 &{} 0 &{} \ldots &{} A^*_{K_t} \end{array} \right) \quad t=1,\ldots , T-1 \end{aligned}$$

(36b)

$$\begin{aligned} D(t)= & {} \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} B^*_{K_{t-1}+1} &{} 0 &{}\ldots &{} 0\\ 0 &{} B^*_{K_{t-1}+2} &{} \ldots &{} 0 \\ 0 &{} 0 &{} \ddots &{} 0 \\ 0 &{} 0 &{} \ldots &{} B^*_{K_t} \end{array} \right) \quad t=1,\ldots , T-1 \end{aligned}$$

(36c)

$$\begin{aligned} r(t)= & {} \left( \begin{array}{c} q^*_{K_{t-1}+1} \\ \vdots \\ q^*_{K_t} \end{array} \right) \quad t=1,\ldots , T-1 \end{aligned}$$

(36d)

where the quantities $A^*_{k_t}$, $B^*_{k_t}$ and $q^*_{k_t}$ are the ones defined in (34a)–(34c).

Non-negativity conditions on the control variables, Eq. (3e), are a direct consequence of constraints (2f) and of assumption A2-3. $\square$

1.3 Proposition 4.4

Proof

For each $t,\ t=0,\ldots ,T-1$, conditions (16a)–(16f) are equivalent to the optimality conditions of the following pair of optimization problems

$$\begin{aligned} \max _{u(t)}&{\tilde{H}}(x(t),u(t),\psi (t+1),\lambda (t)) \end{aligned}$$

(37a)

$$\begin{aligned}&\frac{\partial {\tilde{H}}(x(t),u(t),\psi (t+1),\lambda (t))}{\partial \lambda (t)}\ge 0 \end{aligned}$$

(37b)

$$\begin{aligned}&u(t)\ge 0 \end{aligned}$$

(37c)

$$\begin{aligned} \min _{\lambda (t)}&{\tilde{H}}(x(t),u(t),\psi (t+1),\lambda (t)) \end{aligned}$$

(38a)

$$\begin{aligned}&\frac{\partial {\tilde{H}}(x(t),u(t),\psi (t+1),\lambda (t))}{\partial u(t)}\le 0 \end{aligned}$$

(38b)

$$\begin{aligned}&\lambda (t)\ge 0. \end{aligned}$$

(38c)

In more detail, optimality conditions for problem (37a)–(37c) are

$$\begin{aligned} \frac{\partial {\tilde{H}}(x(t),u(t),\psi (t+1),\lambda (t))}{\partial u(t)}\le & {} 0 \end{aligned}$$

(39a)

$$\begin{aligned} \frac{\partial {\tilde{H}}(x(t),u(t),\psi (t+1),\lambda (t))}{\partial \lambda (t)}\ge & {} 0 \end{aligned}$$

(39b)

$$\begin{aligned} u(t)'\left[ \frac{\partial {\tilde{H}}(x(t),u(t),\psi (t+1),\lambda (t))}{\partial u(t)}\right]= & {} 0 \end{aligned}$$

(39c)

$$\begin{aligned} u(t)\ge & {} 0. \end{aligned}$$

(39d)

While, optimality conditions for problem (38a)–(38c) are

$$\begin{aligned} \frac{\partial {\tilde{H}}(x(t),u(t),\psi (t+1),\lambda (t))}{\partial \lambda (t)}\ge & {} 0 \end{aligned}$$

(40a)

$$\begin{aligned} \frac{\partial {\tilde{H}}(x(t),u(t),\psi (t+1),\lambda (t))}{\partial u(t)}\le & {} 0\end{aligned}$$

(40b)

$$\begin{aligned} \lambda (t)'\left[ \frac{\partial {\tilde{H}}(x(t),u(t),\psi (t+1),\lambda (t))}{\partial \lambda (t)}\right]= & {} 0 \end{aligned}$$

(40c)

$$\begin{aligned} \lambda (t)\ge & {} 0. \end{aligned}$$

(40d)

Solving only one subproblem at time does not guarantee the satisfaction of all optimality conditions. The equivalence is preserved when the conditions are solved simultaneously and thus the two optimization problems have to be solved jointly.

Equation (39c) defines the complementarity conditions for problem (37a)–(37c). Taking into account (11) and (12), Eq. (39c) can be written as follows

$$\begin{aligned}&u(t)'\left[ \dfrac{\partial F_t(x(t),u(t))}{\partial u(t)}+B(t)'\psi (t+1)+D(t)'\lambda (t)\right] =0. \end{aligned}$$

Multiplying and rearranging the terms we have

$$\begin{aligned}&u(t)'D(t)'\lambda (t)=-u(t)'\left[ \dfrac{\partial F_t(x(t),u(t))}{\partial u(t)}+B(t)'\psi (t+1)\right] . \end{aligned}$$

(41)

Using (11) and (12), substituting (41) into (38a), and discarding the terms that do not depend on the optimizing variables $\lambda (t)$, problem (38a)–(38c) can be rewritten as

$$\begin{aligned} \min _{\lambda (t)}&\{\left[ C(t)x(t) + r(t)\right] '\lambda (t)\} \end{aligned}$$

(42a)

$$\begin{aligned}&D(t)'\lambda (t)\le -\dfrac{\partial F_t(x(t),u(t))}{\partial u(t)}-B(t)'\psi (t+1) \end{aligned}$$

(42b)

$$\begin{aligned}&\lambda (t)\ge 0. \end{aligned}$$

(42c)

Analogous considerations can be applied to the first optimization problem. Equation (40c) defines the complementarity conditions for problem (38a)–(38c). Taking into account (11) and (12), Eq. (40c) can be written as follows

$$\begin{aligned}&\lambda (t)'\left[ C(t)x(t)+D(t)u(t)+r(t)\right] =0. \end{aligned}$$

Multiplying and rearranging the terms we obtain

$$\begin{aligned}&\lambda (t)'D(t)u(t)=-\lambda (t)'\left[ C(t)x(t)+r(t)\right] . \end{aligned}$$

(43)

Substituting (43) into (37a), and discarding the terms that do not depend on the optimizing variables u(t), problem (37a)–(37c) can be rewritten as

$$\begin{aligned} \max _{u(t)}&\{F_t(x(t),u(t))+\psi (t+1)'B(t)u(t) \} \end{aligned}$$

(44a)

$$\begin{aligned}&D(t)u(t)\ge -C(t)x(t)-r(t) \end{aligned}$$

(44b)

$$\begin{aligned}&u(t)\ge 0. \end{aligned}$$

(44c)

$\square$

1.4 Proposition 4.5

Proof

Recall that the state variables x(t), the control variables u(t), and the multipliers $\lambda (t)$ and $\psi (t+1)$, at time t, in the OC problem, are defined as the collections of all states, controls and multipliers related to nodes at time t in the scenario tree as follows:

$$\begin{aligned} x(0)= & {} \left( \begin{array}{c} x_{k_0} \\ \end{array} \right) \quad x(t)=\left( \begin{array}{c} x_{K_{t-1}+1} \\ \vdots \\ x_{K_t}\\ \end{array} \right) \quad t=1,\ldots ,T \nonumber \\ u(0)= & {} \left( \begin{array}{c} u_{k_0} \\ \end{array} \right) \quad u(t)=\left( \begin{array}{c} u_{K_{t-1}+1} \\ \vdots \\ u_{K_t}\\ \end{array} \right) \ \ t=1,\ldots ,T-1 \nonumber \\ \psi (0)= & {} \left( \begin{array}{c} \psi _{k_0} \\ \end{array} \right) \quad \psi (t)=\left( \begin{array}{c} \psi _{K_{t-1}+1} \\ \vdots \\ \psi _{K_t}\\ \end{array} \right) \quad t=1,\ldots ,T \nonumber \\ \lambda (0)= & {} \left( \begin{array}{c} \lambda _{k_0} \\ \end{array} \right) \quad \lambda (t)=\left( \begin{array}{c} \lambda _{K_{t-1}+1} \\ \vdots \\ \lambda _{K_t}\\ \end{array} \right) \quad t=1,\ldots ,T-1. \end{aligned}$$

Expanding conditions (20a)–(20j) we obtain the result. The matrices ${\tilde{A}}_{k_t}$, ${\tilde{B}}_{k_t}$, ${\tilde{C}}_{k_t}$, ${\tilde{D}}_{k_t}$ are obtained rearranging from the matrices A(t), B(t), C(t), D(t) and the vectors q(t) and r(t) defined either in Proposition 3.1 or in Proposition 3.2. $\square$