Numerical Methods for Convex Multistage Stochastic Optimization

Traditionally different communities of researchers dealt with optimization problems involving uncertainty, modelled in stochastic terms, using different terminology and modeling frameworks. In this respect we can point to the fields of Stochastic Programming (SP), Stochastic Optimal Control (SOC) and Markov Decision Processes (MDP). Historically the developments in SP on one hand and SOC and MDP on the other, went along different directions with different modeling frameworks and solution methods. In this paper we mainly concentrate on SP and SOC approaches. In these frameworks there are natural situations when the considered problems are convex. In continuous optimization convexity is the main consideration allowing development of efficient numerical algorithms, [30].

The main goal of this paper is to present some recent developments in numerical approaches to solving convex optimization problems involving sequential decision making. We do not try to give a comprehensive review of the subject with a complete list of references, etc. Rather the aim is to present a certain point of view about some recent developments in solving convex multistage stochastic problems.

The SOC modeling is convenient for demonstration of some basic ideas since on one hand it can be naturally written in the MDP terms, and on the other hand it can be formulated in the Stochastic Programming framework. Stochastic Programming (SP) has a long history. Two stage stochastic programming (with recourse) was introduced in Dantzig [8] and Beale [2], and was intrinsically connected with linear programming. From the beginning SP was aimed at numerical solutions. Until about twenty years ago, the modeling approach to two and multistage SP was predominately based on construction of scenarios represented by scenario trees. This approach allows to formulate the so-called deterministic equivalent optimization problem with the number of decision variables more or less proportional to the number of scenarios. When the deterministic equivalent could be represented as a linear program, such problems were considered to be numerically solvable. Because of that, the topic of SP was often viewed as a large scale linear programming. We can refer for presentation of these developments to Birge [6] and references there in.

From the point of view of the scenarios construction approach there is no much difference between two stage and multistage SP. In both cases the numerical effort in solving the deterministic equivalent is more or less proportional to the number of generated scenarios. This view on SP started to change with developments of randomization methods and the sample complexity theory. From the point of view of solving deterministic equivalent, even two stage linear stochastic programs are computationally intractable; their computational complexity is #P-hard for a sufficiently high accuracy (cf., [10],[16]). On the other hand, under reasonable assumptions, the number of randomly generated scenarios (by Monte Carlo sampling techniques), which are required to solve two stage SP problems with accuracy $\varepsilon>0$ and high probability is of order $O(\varepsilon^{-2})$, [47, Section 5.3]. While randomization methods were reasonably successful in solving two stage problems, as far as multistage SP is concerned the situation is different. Number of scenarios needed to solve multistage SP problems grows exponentially with increase of the number of stages, [50],[47, Section 5.8.2].

Classical approach to sequential optimization is based on dynamic programming, [3]. Dynamic programming also has a long history and is in the heart of the SOC and MDP modeling. It has the problem of the so-called “Curse of Dimensionality”, the term coined by Bellman. Its computational complexity increases exponentially with increase of dimension of state variables. There is a large literature trying to deal with this problem by using various approximations of dynamic programming equations (e.g., [37]). Most of these methods are heuristics and do not give verifiable guarantees for the accuracy of obtained solutions.

Recent progress in solving convex multistage SP problems is based on cutting planes approximations of the cost-to-go (value) functions of dynamic programming equations. These methods allow to give an estimate of the error of the computed solution. Cutting planes type algorithms in dynamical settings is one of the main topics of this paper. We discuss such algorithms in the frameworks of SP and SOC. Moreover, we will also present extensions of stochastic approximation (a.k.a. stochastic gradient descent) type methods [38, 29, 28, 21] for multistage stochastic optimization, referred to as dynamic stochastic approximation in [24]. From the computational complexity point of view, these two types of methods seem to be complimentary to each other in the following sense. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables. On the other hand, stochastic approximation type methods can only deal with a small number of stages, but a large number of decision variables. These methods share the following common features: (a) both methods utilize the convex structure of the cost-to-go (value) functions of dynamic programming equations, (b) both methods do not require explicit discretization of state space, (c) both methods guarantee the convergence to the global optimality, (d) rates of convergence for both methods have been established.

We use the following notation and terminology throughout the paper. For $a\in{\mathbb{R}}$ we denote $[a]_{+}:=\max\{0,a\}$. Unless stated otherwise $\|\cdot\|$ denotes Euclidean norm in ${\mathbb{R}}^{n}$. By $\mathop{\rm dist}(x,S):=\inf_{y\in S}\|x-y\|$ we denote the distance from a point $x\in{\mathbb{R}}^{n}$ to a set $S\subset{\mathbb{R}}^{n}$. We write $x^{\top}y$ or $\langle x,y\rangle$ for the scalar product $\sum_{i=1}^{n}x_{i}y_{i}$ of vectors $x,y\in{\mathbb{R}}^{n}$. It is said that a set $S\subset{\mathbb{R}}^{n}$ is polyhedral if it can be represented by a finite number of affine constraints, it is said that a function $f:{\mathbb{R}}^{n}\to{\mathbb{R}}$ is polyhedral if it can be represented as maximum of a finite number of affine functions. For a process $\xi_{1},\xi_{2},...$, we denote by $\xi_{[t]}=(\xi_{1},...,\xi_{t})$ its history up to time $t$. By ${\mathbb{E}}_{|X}[\,\cdot\,]$ we denote the conditional expectation, conditional on random variable (random vector) $X$. We use the same notation $\xi_{t}$ viewed as a random vector or as a vector variable, the particular meaning will be clear from the context. For a probability space $(\Omega,{\cal F},{\mathbb{P}})$, by $L_{p}(\Omega,{\cal F},{\mathbb{P}})$, $p\in[1,\infty)$, we denote the space of random variables $Z:\Omega\to{\mathbb{R}}$ having finite $p$-th order moment, i.e., such that $\int|Z|^{p}d{\mathbb{P}}<\infty$. Equipped with norm $\|Z\|_{p}:=\left(\int|Z|^{p}d{\mathbb{P}}\right)^{1/p}$, $L_{p}(\Omega,{\cal F},{\mathbb{P}})$ becomes a Banach space. The dual of ${\cal Z}:=L_{p}(\Omega,{\cal F},{\mathbb{P}})$ is the space ${\cal Z}^{*}=L_{q}(\Omega,{\cal F},{\mathbb{P}})$ with $q\in(1,\infty]$ such that $1/p+1/q=1$.

In Stochastic Programming (SP) the $T$-stage optimization problem can be written as

		$\displaystyle\min\limits_{x_{t}\in{\cal X}_{t}}$	$\displaystyle{\mathbb{E}}\Big{[}\sum_{t=1}^{T}f_{t}(x_{t},\xi_{t})\Big{]}$		(2.1)
		$\displaystyle{\rm s.t}$	$\displaystyle B_{t}x_{t-1}+A_{t}x_{t}=b_{t},\;t=1,...,T.$		(2.2)

Here $f_{t}:{\mathbb{R}}^{n_{t}}\times{\mathbb{R}}^{d_{t}}\to{\mathbb{R}}$ are objective functions, $\xi_{t}\in{\mathbb{R}}^{d_{t}}$ are random vectors, ${\cal X}_{t}\subset{\mathbb{R}}^{n_{t}}$ are nonempty closed sets, $B_{t}=B_{t}(\xi_{t})$, $A_{t}=A_{t}(\xi_{t})$ and $b_{t}=b_{t}(\xi_{t})$ are matrix and vector functions of $\xi_{t}$, $t=1,...,T$, with $B_{1}=0$.

Constraints (2.2) often represent some type of balance equations between successive stages, while the set ${\cal X}_{t}$ can be viewed as representing local constraints at time $t$. It is possible to consider balance equations in a more general form, nevertheless formulation (2.2) will be sufficient for our purpose of discussing convex problems. In particular, if the objective functions $f_{t}(x_{t},\xi_{t}):=c_{t}^{\top}x_{t}$ are linear, with $c_{t}=c_{t}(\xi_{t})$, and the sets ${\cal X}_{t}$ are polyhedral, then problem (2.1) - (2.2) becomes a linear multistage stochastic program.

The sequence of random vectors $\xi_{1},...$, is viewed as a data process. Unless stated otherwise we make the following assumption throughout the paper.

At every time period $t=1,...,$ we have information about (observed) realization $\xi_{[t]}=(\xi_{1},...,\xi_{t})$ of the data process. Naturally our decisions should be based on the information available at time of the decision and should not depend on the future unknown values $\xi_{t+1},...,\xi_{T}$; this is the so-called principle of nonantisipativity. That is, the decision variables $x_{t}=x_{t}(\xi_{[t]})$ are functions of the data process, and a sequence of such functions for every stage $t=1,...,T$, is called a policy or a decision rule. The optimization in (2.1) - (2.2) is performed over policies satisfying the feasibility constraints. The feasibility constraints of problem (2.1) - (2.2) should be satisfied with probability one, and the expectation is taken with respect to the probability distribution of the random vector $\xi_{[T]}=(\xi_{1},...,\xi_{T})$. It could be noted that the dependence of decision variables $x_{t}$, as well as parameters $(B_{t}$,$A_{t}$,$b_{t})$, on the data process is often suppressed in the notation. It is worthwhile to emphasize that it suffices to consider policies depending only on the history of the data process without history of the decisions, because of Assumption 2.1.

The first stage decision $x_{1}$ is of the main interest and assumed to be deterministic, i.e., made before observing future realization of the data process. In that framework vector $\xi_{1}$ and the corresponding parameters $(A_{1},b_{1})$ are deterministic, i.e., their values are known at the time of first stage decision. Also the first stage objective function $f_{1}(x_{1})=f_{1}(x_{1},\xi_{1})$ is a function of $x_{1}$ alone.

We can write the following dynamic programming equations for problem (2.1) - (2.2) (e.g., [47, Section 3.1]). At the last stage the cost-to-go (value) function is

$$Q_{T}(x_{T-1},\xi_{T})=\inf_{x_{T}\in{\cal X}_{T}}\left\{f_{T}(x_{T},\xi_{T}):B_{T}x_{T-1}+A_{T}x_{T}=b_{T}\right\}$$

(2.3)

and then going backward in time for $t=T-1,...,2$, the cost-to-go function is

$$Q_{t}(x_{t-1},\xi_{[t]})=\inf_{x_{t}\in{\cal X}_{t}}\left\{f_{t}(x_{t},\xi_{t})+{\mathbb{E}}_{|\xi_{[t]}}[Q_{t+1}(x_{t},\xi_{[t+1]})]:B_{t}x_{t-1}+A_{t}x_{t}=b_{t}\right\}.$$

(2.4)

The optimal value of problem (2.1) - (2.2) is given by the optimal value of the first stage problem

$$\min\limits_{x_{1}\in{\cal X}_{1}}f_{1}(x_{1})+{\mathbb{E}}\left[Q_{2}(x_{1},\xi_{2})\right]\;{\rm s.t.}\;A_{1}x_{1}=b_{1}.$$

(2.5)

The optimization in (2.3) - (2.4) is over (nonrandom) variables $x_{t}\in{\mathbb{R}}^{n_{t}}$ (recall that $B_{t}=B_{t}(\xi_{t})$, $A_{t}=A_{t}(\xi_{t})$ and $b_{t}=b_{t}(\xi_{t})$ are functions of $\xi_{t}$). The corresponding optimal policy is defined by $\bar{x}_{t}=\bar{x}_{t}(\xi_{[t]})$, $t=2,...,T$, where

$$\bar{x}_{t}\in\mathop{\rm arg\,min}_{x_{t}\in{\cal X}_{t}}\left\{f_{t}(x_{t},\xi_{t})+{\mathbb{E}}_{|\xi_{[t]}}[Q_{t+1}(x_{t},\xi_{[t+1]})]:B_{t}\bar{x}_{t-1}+A_{t}x_{t}=b_{t}\right\},$$

(2.6)

with the expectation term of $Q_{T+1}(\cdot,\cdot)$ at the last stage omitted. Of the main interest is the first stage solution given by the optimal solution $\bar{x}_{1}$ of the first stage problem (2.5).

Since $\bar{x}_{t-1}$ is a function of $\xi_{[t-1]}$, the cost-to-go function $Q_{t}(\bar{x}_{t-1},\xi_{[t]})$ can be considered as a function of $\xi_{[t]}$. It represents the optimal value of problem

$$\min\limits_{x_{\tau}\in{\cal X}_{\tau}}{\mathbb{E}}\Big{[}\sum_{\tau=t+1}^{T}f_{\tau}(x_{\tau},\xi_{\tau})\Big{]}\;\;{\rm s.t.}\;B_{\tau}x_{\tau-1}+A_{\tau}x_{\tau}=b_{\tau},\;\tau=t+1,...,T,$$

(2.7)

conditional on realization $\xi_{[t]}$ of the data process. This is the dynamic programming (Bellman) principle of optimality. This is also the motivation for the name “cost-to-go” function. Another name for the cost-to-go functions is “value functions”.

The dynamic programming equations reduce the problem from optimization over policies, i.e., over infinite dimensional functional spaces, to evaluation of the cost-to-go functions $Q_{t}(x_{t-1},\xi_{[t]})$ of finite dimensional vectors. However, dependence of the cost-to-go functions on the whole history of the data process makes it numerically unmanageable with increase of the number of stages. The situation is simplified dramatically if we make the following assumption of stagewise independence.

Under Assumption 2.2 of stagewise independence, the conditional expectations in dynamic equations (2.4) become the corresponding unconditional expectations. It is straightforward to show then by induction, going backward in time, that the dynamic equations (2.4) can be written as

$$Q_{t}(x_{t-1},\xi_{t})=\inf_{x_{t}\in{\cal X}_{t}}\left\{f_{t}(x_{t},\xi_{t})+{\cal Q}_{t+1}(x_{t}):B_{t}x_{t-1}+A_{t}x_{t}=b_{t}\right\},$$

(2.8)

where

$${\cal Q}_{t+1}(x_{t}):={\mathbb{E}}[Q_{t+1}(x_{t},\xi_{t+1})],$$

(2.9)

with the expectation taken with respect to the marginal distribution of $\xi_{t+1}$. In that setting one needs to keep track of the (expectation) cost-to-go functions ${\cal Q}_{t+1}(x_{t})$ only. The optimal policy is defined by the equations

$$\bar{x}_{t}\in\mathop{\rm arg\,min}_{x_{t}\in{\cal X}_{t}}\left\{f_{t}(x_{t},\xi_{t})+{\cal Q}_{t+1}(x_{t}):B_{t}\bar{x}_{t-1}+A_{t}x_{t}=b_{t}\right\}.$$

(2.10)

Note that here the optimal policy values can be computed iteratively, starting from optimal solution $\bar{x}_{1}$ of the first stage problem, and then by sequentially computing a minimizer in the right hand side of (2.10) going forward in time for $t=2,...,T$. Of course, this procedure requires availability of the cost-to-go functions ${\cal Q}_{t+1}(x_{t})$.

It is worthwhile to note that here the optimal policy decision $\bar{x}_{t}$ can be viewed as a function of $\bar{x}_{t-1}$ and $\xi_{t}$, for $t=2,...,T$. Of course, $\bar{x}_{t-1}$ is a function of $\bar{x}_{t-2}$ and $\xi_{t-1}$, and so on. So eventually $\bar{x}_{t}$ can be represented as a function of the history $\xi_{[t]}$ of the data process. Assumption 2.1 was crucial for this conclusion, since then we need to consider only the history of the data process rather than also the history of our decisions. This is an important point, we will discuss this later.

Consider the classical Stochastic Optimal Control (SOC) (discrete time, finite horizon) model (e.g. , Bertsekas and Shreve [4]):

		$\displaystyle\min\limits_{u_{t}\in{\cal U}_{t}(x_{t})}$	$\displaystyle{\mathbb{E}}^{\pi}\Big{[}\sum_{t=1}^{T}c_{t}(x_{t},u_{t},\xi_{t})+c_{T+1}(x_{T+1})\Big{]},$		(3.1)
		$\displaystyle{\rm s.t.}$	$\displaystyle x_{t+1}=F_{t}(x_{t},u_{t},\xi_{t}),\;t=1,...,T.$		(3.2)

Variables $x_{t}\in{\mathbb{R}}^{n_{t}}$, $t=1,...,T+1$, represent the state of the system, $u_{t}\in{\mathbb{R}}^{m_{t}}$, $t=1,...,T$, are controls, $\xi_{t}\in{\mathbb{R}}^{d_{t}}$, $t=1,...,T$, are random vectors, $c_{t}:{\mathbb{R}}^{n_{t}}\times{\mathbb{R}}^{m_{t}}\times{\mathbb{R}}^{d_{t}}\to{\mathbb{R}}$, $t=1,...,T$, are cost functions, $c_{T+1}(x_{T+1})$ is a final cost function, $F_{t}:{\mathbb{R}}^{n_{t}}\times{\mathbb{R}}^{m_{t}}\times{\mathbb{R}}^{d_{t}}\to{\mathbb{R}}^{n_{t+1}}$ are (measurable) mappings and ${\cal U}_{t}(x_{t})$ is a (measurable) multifunction mapping $x_{t}\in{\mathbb{R}}^{n_{t}}$ to a subset of ${\mathbb{R}}^{m_{t}}$. Values $x_{1}$ and $\xi_{0}$ are deterministic (initial conditions); it is also possible to view $x_{1}$ as random with a given distribution, this is not essential for the following discussion. The optimization in (3.1) - (3.2) is performed over policies $\pi$ determined by decisions $u_{t}$ and state variables $x_{t}$. This is emphasized in the notation ${\mathbb{E}}^{\pi}$, we are going to discuss this below.

Unless stated otherwise we assume that probability distribution of the random process $\xi_{t}$ does not depend on our decisions (Assumption 2.1). We can consider problem (3.1)-(3.2) in the framework of SP if we view $y_{t}=(x_{t},u_{t})$, $t=1,...,T$, as decision variables. Suppose that the mapping $F_{t}(x_{t},u_{t},\xi_{t})$ is affine, i.e.,

$$F_{t}(x_{t},u_{t},\xi_{t}):=A_{t}x_{t}+B_{t}u_{t}+b_{t},\;t=1,...,T,$$

(3.3)

where $A_{t}=A_{t}(\xi_{t})$, $B_{t}=B_{t}(\xi_{t})$ and $b_{t}=b_{t}(\xi_{t})$ are matrix and vector valued functions of $\xi_{t}$. The constraints $u_{t}\in{\cal U}_{t}(x_{t})$ can be viewed as local constraints in the SP framework; in particular if ${\cal U}_{t}(x_{t})\equiv{\cal U}_{t}$ are independent of $x_{t}$, then ${\cal U}_{t}$ can be viewed as a counterpart of the set ${\cal X}_{t}$ in problem (2.1) - (2.2). For the affine mapping of the form (3.3), the state equations (3.2) become

$$x_{t+1}-A_{t}x_{t}-B_{t}u_{t}=b_{t},\;t=1,...,T.$$

(3.4)

These state equations are linear in $y_{t}=(x_{t},u_{t})$ and can be viewed as a particular case of the balance equations (2.2) of the stochastic program (2.1) - (2.2). Note, however, that here decision $u_{t}$ should be made before realization of $\xi_{t}$ becomes known, and $x_{t}$ and $u_{t}$ are functions of $\xi_{[t-1]}$ rather than $\xi_{[t]}$. We emphasize that $x_{t}$ and $u_{t}$ can be considered as functions of the history $\xi_{[t-1]}$ of the random process $\xi_{t}$, without dependence on the history of the decisions. As in the SP framework, this follows from the dynamic programming equations discussed below, and Assumption 2.1 is essential for that conclusion.

There is a time shift in equations (3.4) as compared with the SP equations (2.2). We emphasize that in both the SOC and SP approaches, the decisions are made based on information available at time of the decision; this is the principle of nonanticipativity. Because of the time shift, the dynamic programming equations for the SOC problem are slightly different from the respective equations in SP. More important is that in the SOC framework there is a clear separation between the state and control variables. This will have an important consequence for the respective dynamic programming equations which we consider next.

Similar to SP, the dynamic programming equations for the SOC problem (3.1) - (3.2) can be written as follows. At the last stage, the value function $V_{T+1}(x_{T+1})=c_{T+1}(x_{T+1})$ and, going backward in time for $t=T,...,1$, the value functions

$$V_{t}(x_{t},\xi_{[t-1]})=\inf\limits_{{u_{t}\in{\cal U}_{t}(x_{t})}\atop{x_{t+1}=F_{t}(x_{t},u_{t},\xi_{t})}}{\mathbb{E}}_{|\xi_{[t-1]}}\left[c_{t}(x_{t},u_{t},\xi_{t})+V_{t+1}\big{(}x_{t+1},\xi_{[t]}\big{)}\right].$$

(3.5)

The optimization in the right hand side of (3.5) is performed jointly in $u_{t}$ and $x_{t+1}$. The optimal value of the SOC problem (3.1)-(3.2) is given by the first stage value function $V_{1}(x_{1})$, and can be viewed as a function of the initial conditions $x_{1}$. Note that because of the state equation (3.2), equations (3.5) can be written in the following equivalent form

$$V_{t}(x_{t},\xi_{[t-1]})=\inf\limits_{u_{t}\in{\cal U}_{t}(x_{t})}{\mathbb{E}}_{|\xi_{[t-1]}}\left[c_{t}(x_{t},u_{t},\xi_{t})+V_{t+1}\big{(}F_{t}(x_{t},u_{t},\xi_{t}),\xi_{[t]}\big{)}\right].$$

(3.6)

The corresponding optimal policy is defined by

$$(\bar{u}_{t},\bar{x}_{t+1})\in\mathop{\rm arg\,min}\limits_{{u_{t}\in{\cal U}_{t}(\bar{x}_{t})}\atop{x_{t+1}=F_{t}(\bar{x}_{t},u_{t},\xi_{t})}}{\mathbb{E}}_{|\xi_{[t-1]}}\left[c_{t}(\bar{x}_{t},u_{t},\xi_{t})+V_{t+1}\big{(}x_{t+1},\xi_{[t]}\big{)}\right].$$

(3.7)

Similar to SP, it follows that $\bar{u}_{t}$ can be considered as a function of $\xi_{[t-1]}$, and $\bar{x}_{t+1}$ as a function of $\xi_{[t]}$. That is, $(\bar{u}_{t},\bar{x}_{t})$ is a function of $\xi_{[t-1]}$, this was already mentioned in the previous paragraphs. Again Assumption 2.1 is essential for the above derivations and conclusions.

In SOC framework the random process $\xi_{1},...,$ is often viewed as a noise or disturbances (note that here $\xi_{1}$ is also random). In such cases the assumption of stagewise independence (Assumption 2.2) is natural. In the stagewise independent case the dynamic programming equations (3.6) simplify with the value functions $V_{t}(x_{t})$, $t=1,...,T$, being functions of the state variables only, that is

$$V_{t}(x_{t})=\inf\limits_{u_{t}\in{\cal U}_{t}(x_{t})}{\mathbb{E}}\left[c_{t}(x_{t},u_{t},\xi_{t})+V_{t+1}\big{(}F_{t}(x_{t},u_{t},\xi_{t})\big{)}\right],$$

(3.10)

where the expectation is taken with respect to the marginal distribution of $\xi_{t}$. Consequently the optimal policy is defined by the optimal controls $\bar{u}_{t}=\pi_{t}(x_{t})$, where

$$\bar{u}_{t}\in\mathop{\rm arg\,min}_{u_{t}\in{\cal U}_{t}(x_{t})}{\mathbb{E}}\left[c_{t}(x_{t},u_{t},\xi_{t})+V_{t+1}\big{(}F_{t}(x_{t},u_{t},\xi_{t})\big{)}\right].$$

(3.11)

That is, in the stagewise independent case it is suffices to consider policies with controls of the form $u_{t}=\pi_{t}(x_{t})$.

As an example let us consider the classical inventory problem.

In the risk averse approach the expectation functional is replaced by a risk measure. Let $(\Omega,{\cal F},{\mathbb{P}})$ be a probability space and ${\cal Z}$ be a linear space of measurable functions (random variables) $Z:\Omega\to{\mathbb{R}}$. Risk measure ${\cal R}$ is a functional assigning a number to random variable $Z\in{\cal Z}$, that is ${\cal R}:{\cal Z}\to{\mathbb{R}}$. In the risk neutral case, ${\cal R}$ is the expectation operator, i.e., ${\cal R}(Z):={\mathbb{E}}[Z]=\int_{\Omega}Z(\omega)d{\mathbb{P}}(\omega)$. In order for this expectation to be well defined we have to restrict the space of considered random variables; for the expectation it is natural to take the space of integrable functions, i.e., ${\cal Z}:=L_{1}(\Omega,{\cal F},{\mathbb{P}})$.

It was suggested in Artzner et al [1] that reasonable risk measures should satisfy the following axioms: subadditivity, monotonicity, translation equivariance, positive homogeneity. Risk measures satisfying these axioms were called coherent. For a thorough discussion of coherent risk measures we can refer to [11],[47]. It is possible to show that if the space ${\cal Z}$ is a Banach lattice, in particular if ${\cal Z}=L_{p}(\Omega,{\cal F},{\mathbb{P}})$, then a (real valued) coherent risk measure ${\cal R}:{\cal Z}\to{\mathbb{R}}$ is continuous in the norm topology of ${\cal Z}$ (cf., [43, Proposition 3.1]). It follows then by the Fenchel - Moreau theorem that ${\cal R}$ has the following dual representation

$${\cal R}(Z)=\sup_{\zeta\in{\mathfrak{A}}}\int_{\Omega}Z(\omega)\zeta(\omega)d{\mathbb{P}}(\omega),\;\;Z\in{\cal Z},$$

(4.1)

where ${\mathfrak{A}}$ is a convex weakly^∗ compact subset of ${\cal Z}^{*}$. Moreover, the axioms of coherent risk measures imply that every $\zeta\in{\mathfrak{A}}$ is a density function, i.e., almost surely $\zeta(\omega)\geq 0$ and $\int_{\Omega}\zeta(\omega)d{\mathbb{P}}(\omega)=1$ (cf., [43, Theorem 2.2]).

An important example of coherent risk measure is the Average Value-at-Risk:

	$\displaystyle{\sf AV@R}_{\alpha}(Z)$	$\displaystyle:=$	$\displaystyle(1-\alpha)^{-1}\int_{\alpha}^{1}F^{-1}_{Z}(\tau)d\tau$		(4.2)
		$\displaystyle=$	$\displaystyle\inf_{\theta\in{\mathbb{R}}}\left\{\theta+(1-\alpha)^{-1}{\mathbb{E}}[Z-\theta]_{+}\right\},\;\;\alpha\in(0,1]$		(4.3)

where $F_{Z}(z):={\mathbb{P}}(Z\leq z)$ is the cumulative distribution function (cdf) of $Z$ and $F^{-1}_{Z}(\tau):=\inf\{z:F_{Z}(z)\geq\tau\}$ is the respective quantile. It is natural in this example to use the space ${\cal Z}=L_{1}(\Omega,{\cal F},{\mathbb{P}})$ and its dual ${\cal Z}^{*}=L_{\infty}(\Omega,{\cal F},{\mathbb{P}})$. In various equivalent forms this risk measure was introduced in different contexts by different authors under different names, such as Expected Shortfall, Expected Tail Loss, Conditional Value-at-Risk; variational form (4.3) was suggested in [32],[41]. In the dual form, it has representation (4.1) with

$$\begin{array}[]{l}{\mathfrak{A}}=\left\{\zeta\in{\cal Z}^{*}:0\leq\zeta\leq(1-\alpha)^{-1},\;\int_{\Omega}\zeta d{\mathbb{P}}=1\right\}.\end{array}$$

Representation (4.1) can be viewed from the distributionally robust point of view. Recall that if $P$ is a probability measure on $(\Omega,{\cal F})$ which is absolutely continuous with respect to ${\mathbb{P}}$, then by the Radon - Nikodym Theorem it has density $\zeta=dP/d{\mathbb{P}}$. Consider the set ${\mathfrak{M}}$ of probability measures $P$, absolutely continuous with respect to ${\mathbb{P}}$, defined as ${\mathfrak{M}}:=\{P:dP/d{\mathbb{P}}\in{\mathfrak{A}}\}.$ Then representation (4.1) of functional ${\cal R}$ can be written as¹¹1By writing ${\mathbb{E}}_{P}[Z]$ we emphasize that the expectation is taken with respect to the probability measure (probability distribution) $P$.

$${\cal R}(Z)=\sup_{P\in{\mathfrak{M}}}{\mathbb{E}}_{P}[Z].$$

(4.4)

In the Distributionally Robust Optimization (DRO) it is argued that the “true” distribution is not known, and consequently a set ${\mathfrak{M}}$ of probability measures (distributions) is constructed in some way, and referred to as the ambiguity set. In that framework we can view (4.4) as the definition of the corresponding functional. It is straightforward to verify that the obtained functional ${\cal R}$, defined on an appropriate space of random variables, satisfies the axioms of coherent risk measures. So we have a certain duality relation between the risk averse and distributionally robust approaches to stochastic optimization. However, there is an essential difference in a way how the corresponding ambiguity set ${\mathfrak{M}}$ is constructed. In the risk averse approach the set ${\mathfrak{M}}$ consists of probability measures absolutely continuous with respect a specified (reference) measure ${\mathbb{P}}$. On the other hand, in the DRO such dominating measure may not be naturally defined. This happens, for instance, in popular settings where the ambiguity set is defined by moment constraints or is the set of probability measures with prescribed Wasserstein distance from the empirical distribution defined by the data.

In order to extend the risk averse and distributionally robust optimization to the dynamical setting of multistage stochastic optimization, we need to construct a conditional counterpart of the respective functional ${\cal R}$. In writing dynamic equations (2.4) and (3.6) we used conditional expectations in a somewhat informal manner. For the expectation operator there is a classical definition of conditional expectation. That is, let $P$ be a probability measure and ${\cal G}$ be a sigma subalgebra of ${\cal F}$. It is said that random variable, denoted ${\mathbb{E}}_{|{\cal G}}[Z]$, is the conditional expected value of random variable $Z$ given ${\cal G}$ if the following two properties hold: (i) ${\mathbb{E}}_{|{\cal G}}[Z]:\Omega\to{\mathbb{R}}$ is ${\cal G}$-measurable, (ii) $\int_{A}{\mathbb{E}}_{|{\cal G}}[Z](\omega)dP(\omega)=\int_{A}Z(\omega)dP(\omega)$ for any $A\in{\cal G}$. There are many versions of ${\mathbb{E}}_{|{\cal G}}[Z](\omega)$ which can differ from each other on sets of $P$-measure zero. The conditional expectation depends on measure $P$, therefore we sometimes write ${\mathbb{E}}_{P|{\cal G}}[Z]$ to emphasize this when various probability measures are considered.

It seems that it is natural to define the conditional counterpart of the distributionally robust functional, defined in (4.4), as $\sup_{P\in{\mathfrak{M}}}{\mathbb{E}}_{P|{\cal G}}[Z]$. However there are technical issues with a precise meaning of such definition since there are different versions of conditional expectations related to different probability measures $P\in{\mathfrak{M}}$. Even more important, there are conceptual problems with such definition, and in fact this is not how conditional risk measures are defined (cf., [34]). In the risk averse setting there is a natural concept of law invariance. For a random variable $Z$ its cumulative distribution function (cdf), with respect to the reference probability measure ${\mathbb{P}}$, is $F_{Z}(z):={\mathbb{P}}(Z\leq z)$, $z\in{\mathbb{R}}$. It is said that random variables $Z$ and $Z^{\prime}$ are distributionally equivalent if their cumulative distribution functions $F_{Z}(z)$ and $F_{Z^{\prime}}(z)$ do coincide for all $z\in{\mathbb{R}}$. It is said that risk measure ${\cal R}$ is law invariant if ${\cal R}(Z)={\cal R}(Z^{\prime})$ for any distributionally equivalent $Z$ and $Z^{\prime}$. For example the Average Value-at-Risk measure ${\cal R}={\sf AV@R}_{\alpha}$ is law invariant.