P Girardeau
email: pierre.girardeau@ensta.org

CERMICS V Leclere

A B Philpott
email: a.philpott@auckland.ac.nz

ON THE CONVERGENCE OF DECOMPOSITION METHODS FOR MULTISTAGE STOCHASTIC CONVEX PROGRAMS

Keywords: May 18, 2013. 2010 Mathematics Subject Classification. 90C14, 90C39 Stochastic Programming, Dynamic Programming, Stochastic Dual Dynamic Programming algorithm, Monte-Carlo sampling, Benders decomposition

We prove the almost-sure convergence of a class of samplingbased nested decomposition algorithms for multistage stochastic convex programs in which the stage costs are general convex functions of the decisions, and uncertainty is modelled by a scenario tree. As special cases, our results imply the almost-sure convergence of SDDP, CUPPS and DOASA when applied to problems with general convex cost functions.

Introduction

Multistage stochastic programs with recourse are well known in the stochastic programming community, and are becoming more common in applications. We are motivated in this paper by applications in which the stage costs are nonlinear convex functions of the decisions. Production functions are often modelled as nonlinear concave functions of allocated resources. For example Finardi and da Silva [START_REF] Finardi | Solving the hydro unit commitment problem via dual decomposition and sequential quadratic programming[END_REF] use this approach to model hydro electricity production as a concave function of water flow. Smooth nonlinear value functions also arise when one maximizes profit with linear demand functions (see e.g. [START_REF] Philpott | A multistage stochastic programming model for the New Zealand dairy industry[END_REF]) giving a concave quadratic objective or when coherent risk measures are defined by continuous distributions in multistage problems [START_REF] Shapiro | Analysis of stochastic dual dynamic programming method[END_REF].

Having general convex stage costs does not preclude the use of cutting plane algorithms for attacking these problems. The most well-known of these is the stochastic dual dynamic programming (SDDP) algorithm of Pereira and Pinto [START_REF] Pereira | Multi-stage stochastic optimization applied to energy planning[END_REF]. This algorithm constructs feasible dynamic programming policies using an outer approximation of a (convex) future cost function that is computed using Benders cuts. The policies defined by these cuts can be evaluated using simulation, and their performance measured against a lower bound on their expected cost. This provides a convergence criterion that may be applied to terminate the algorithm when the estimated cost of the candidate policy is close enough to its lower bound. The SDDP algorithm has led to a number of related methods [START_REF] Chen | A convergent cutting-plane and partialsampling algorithm for multistage linear programs with recourse[END_REF][START_REF] Donohue | Stochastic Network Programming and the Dynamic Vehicle Allocation Problem[END_REF][START_REF] Donohue | The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse[END_REF][START_REF] Hindsberger | ReSa: A method for solving multistage stochastic linear programs[END_REF][START_REF] Philpott | On the convergence of stochastic dual dynamic programming and related methods[END_REF] that are based on the same essential idea, but seek to improve the method by exploiting the structure of particular applications. We call these methods DOASA for Dynamic Outer-Approximation Sampling Algorithms but they are now generically named SDDP methods.

SDDP methods are known to converge almost surely on a finite scenario tree when the stage problems are linear programs. The first formal proof of such a result was published by Chen and Powell [START_REF] Chen | A convergent cutting-plane and partialsampling algorithm for multistage linear programs with recourse[END_REF] who derived this for their CUPPS algorithm. This proof was extended by Linowsky and Philpott [START_REF] Linowsky | On the convergence of sampling-based decomposition algorithms for multistage stochastic programs[END_REF] to cover other SDDP algorithms. The convergence proofs in [START_REF] Chen | A convergent cutting-plane and partialsampling algorithm for multistage linear programs with recourse[END_REF] and [START_REF] Linowsky | On the convergence of sampling-based decomposition algorithms for multistage stochastic programs[END_REF] make use of an unstated assumption regarding the independence of sampled random variables and convergent subsequences of algorithm iterates. This assumption was identified by Philpott and Guan [START_REF] Philpott | On the convergence of stochastic dual dynamic programming and related methods[END_REF], who gave a simpler proof of almost sure convergence of SDDP methods based on the finite convergence of the nested decomposition algorithm (see [START_REF] Donohue | Stochastic Network Programming and the Dynamic Vehicle Allocation Problem[END_REF]). This does not require the unstated assumption, but exploits the fact that the collection of subproblems to be solved has a finite number of dual extreme points. This begs the question of whether SDDP methods will converge almost surely for general convex stage problems, where the value functions may admit an infinite number of subgradients.

In this paper we propose a different approach from the one in [START_REF] Chen | A convergent cutting-plane and partialsampling algorithm for multistage linear programs with recourse[END_REF] and [START_REF] Linowsky | On the convergence of sampling-based decomposition algorithms for multistage stochastic programs[END_REF] and show how a proof of convergence for sampling-based nested decomposition algorithms on finite scenario trees can be established for models with convex subproblems (which may not have polyhedral value functions). Our result is proved for a general class of methods including all the variations discussed in the literature [START_REF] Chen | A convergent cutting-plane and partialsampling algorithm for multistage linear programs with recourse[END_REF][START_REF] Donohue | Stochastic Network Programming and the Dynamic Vehicle Allocation Problem[END_REF][START_REF] Donohue | The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse[END_REF][START_REF] Hindsberger | ReSa: A method for solving multistage stochastic linear programs[END_REF][START_REF] Pereira | Multi-stage stochastic optimization applied to energy planning[END_REF][START_REF] Philpott | On the convergence of stochastic dual dynamic programming and related methods[END_REF]. The proof establishes convergence with probability 1 as long as the sampling in the forward pass is independent of previous realisations. Our proof relies heavily on the independence assumption and makes use of the Strong Law of Large Numbers. In contrast to [START_REF] Philpott | On the convergence of stochastic dual dynamic programming and related methods[END_REF] we have not shown that convergence is guaranteed in all procedures for constructing a forward pass that visit every node of the scenario tree an infinite number of times.

The result we prove works in the space of state variables expressed as random variables adapted to the filtration defined by the scenario tree. Because this tree has a finite number of nodes, this space is compact, and so we may extract convergent subsequences for any infinite sequence of states. Unlike the arguments in [START_REF] Chen | A convergent cutting-plane and partialsampling algorithm for multistage linear programs with recourse[END_REF] and [START_REF] Linowsky | On the convergence of sampling-based decomposition algorithms for multistage stochastic programs[END_REF], these subsequences are not explicitly constructed, and so we can escape the need to assume properties of them that we wish to be inherited from independent sampling.

Although the value functions we construct admit an infinite number of subgradients, our results do require an assumption that serves to bound the norms of these. This assumption is an extension of relatively complete recourse that ensures that some infeasible candidate solutions to any stage problem can be forced to be feasible by a suitable control. Since we are working in the realm of nonlinear programming, some constraint qualification of this form will be needed to ensure that we can extract subgradients. In practice, SDDP models use penalties on constraint violations to ensure feasibility, which implicitly bounds the subgradients of the Bellman functions. Our recourse assumptions are arguably weaker, since we do not have a result that shows that they enable an equivalent formulation with an exact penalization of infeasibility.

The paper is laid out as follows. We first consider a deterministic multistage problem, in which the proof is easily understandable. This is then extended in §3 to a stochastic problem formulated in a scenario tree. We close with some remarks about the convergence of sampling algorithms.

The deterministic case

Our convergence proofs are based around showing that a sequence of outer approximations formed by cutting planes converges to the true Bellman function in the neighbourhood of the optimal state trajectories. We begin by providing a proof that Kelley's cutting plane method [START_REF] Kelley | The cutting-plane method for solving convex programs[END_REF] converges when applied to the optimization problem:

W * := min u∈U W (u) ,
where U is a convex subset of R m , and W is a convex function with uniformly bounded subgradients. The result we prove is not directly used in the more complex results that follow, but the main ideas on which the proofs rely are the same. We believe the reader will find it convenient to already have the scheme of the proof in mind when studying the more important results later on.

Kelley's method generates a sequence of iterates u j j∈N by solving, at each iteration, a piecewise linear model of the original problem. The model is then enhanced by adding a cutting plane based on the value W u j and subgradient g j of W at u j . The model at iteration k is denoted by

W k (u) := max 1≤j≤k W u j + g j , u -u j ,
and θ k := min u∈U W k (u) = W k u k+1 . We have the following result.

Lemma 2.1. If W is convex with uniformly bounded subgradients on U and U is compact then

lim k→+∞ W u k = W * .
Proof. This proof is taken from Ruszczynski [START_REF] Ruszczyński | Nonlinear Optimization[END_REF]Theorem 7.7]. Let K ε be the set of indices k such that

W * + ε < W u k < +∞. The proof consists in showing that K ε is finite. Suppose k 1 , k 2 ∈ K ε and k 1 is strictly smaller than k 2 . We have that W u k 1 > W * + ε and that W * ≥ θ k 1 .
Since a new cut will be generated at u k 1 , we will have

W u k 1 + g k 1 , u -u k 1 ≤ W k 1 (u) ≤ W k 2 -1 (u) , ∀u ∈ U, where g k 1 is an element of ∂W u k 1 . In particular, choosing u = u k 2 gives W u k 1 + g k 1 , u k 2 -u k 1 ≤ W k 1 u k 2 ≤ W k 2 -1 u k 2 = θ k 2 -1 ≤ W * . But ε < W u k 2 -W * , so ε < W u k 2 -W u k 1 -g k 1 , u k 2 -u k 1 ,
and as g k 2 ∈ ∂W (u k 2 ), the subgradient inequality for u = u k 1 yields

W u k 2 -W u k 1 ≤ g k 2 , u k 2 -u k 1 .
Therefore, since W has uniformly bounded subgradients, there exists κ > 0 such that

ε < 2κ u k 2 -u k 1 , ∀k 1 , k 2 ∈ K ε , k 1 = k 2 .
Because U is compact, K ε has to be finite. Otherwise there would exist a convergent subsequence of u k k∈Kε and this last inequality could not hold for sufficiently large indices within K ε . This proves the lemma.

Note that Lemma 2.1 does not imply that the sequence of iterates u k k∈N converges 1 . For instance, if the minimum of W is attained on a "flat" part (if W is not strictly convex), then the sequence of iterates may not converge. However, the lemma shows that the sequence of W values at these iterates will converge.

We now consider the multistage case. Let T be a positive integer. We first consider the following deterministic optimal control problem.

min x,u T -1 t=0 C t (x t , u t ) + V T (x T ) (1a) s.t. x t+1 = f t (x t , u t ) , ∀t = 0, . . . , T -1, (1b)
x 0 is given, (1c)

x t ∈ X t , ∀t = 0, . . . , T, (1d)
u t ∈ U t (x t ), ∀t = 0, . . . , T -1. (1e)
In what follows we let Aff(X ) denote the affine hull of X , and define

B t (δ) = {y ∈ Aff(X t ) | y < δ}.
We now make the following assumptions (H 1 ), for t = 0, . . . , T -1:

(1)

X t ⊂ R n , X T ⊂ R n , (2)
multifunctions U t : R n ⇒ R m are assumed to be convex 2 and convex compact valued, (3) functions C t and V T are assumed to be convex lower semicontinuous proper functions, (4) functions f t are linear, (5) final cost function V T is finite valued and Lipschitz-continuous on X T , (6) there exists δ t > 0, defining

X t :=X t + B t (δ t ) such that : (a) ∀x ∈ X t , ∀u ∈ U t (x), C t (x, u) < ∞, (b) for every x ∈ X t , f t (x, U t (x)) ∩ X t+1 = ∅.
1 even though because U is compact, there exists a convergent subsequence. 2 Recall that a multifunction U on convex set X is called convex if (1-λ)U(x)+λU(y) ⊆ U((1 -λ)x + λy) for every x, y ∈ X and λ ∈ (0, 1).

Assumptions (H 1 (1) -(5)) are made to guarantee that problem (1) is a convex optimization problem. Since this problem is in general nonlinear, it also requires a constraint qualification to ensure the existence of subgradients. This is the purpose of Assumption (H 1 [START_REF] Hindsberger | ReSa: A method for solving multistage stochastic linear programs[END_REF]). This assumption means that we can always move from X t a distance of δt 2 in any direction and stay in X t , which is a form of recourse assumption that we call extended relatively complete recourse (ERCR). We note that this is less stringent than imposing complete recourse, which would require X t = R n . Finally we note that we never need to evaluate C t (x, u) with x ∈ X t \X t , so we may assume that there exists a convex function, finite on X t , that coincides with C t on X t . Of course not all convex cost functions satisfy such a property e.g. x → x log(x) cannot be extended below x = 0 while maintaining convexity.

We are now in a position to describe an algorithm for the deterministic control problem [START_REF] Chen | A convergent cutting-plane and partialsampling algorithm for multistage linear programs with recourse[END_REF]. The Dynamic Programming (DP) equation associated with (1) is as follows. For all t = 0, . . . , T -1, let

(2) V t (x t ) =    min ut∈Ut(xt) C t (x t , u t ) + V t+1 (f t (x t , u t )) :=Wt(xt,ut) , x t ∈ X t +∞,
otherwise.

Here the quantity W t (x t , u t ) is the future optimal cost starting at time t from state x and choosing decision u t , so that V t (x) = min u∈Ut(xt) W t (x, u).

The cutting plane method works as follows. At iteration 0, define functions V 0 t , t = 0, . . . , T -1, to be identically equal to -∞. At time T , since we know exactly the end value function, we impose V k T = V T for all iterations k ∈ N. At each iteration k, the process is the following.

Starting with x k 0 = x 0 , at any time stage t, solve

θ k t = min ut∈R m x∈Aff Xt C t (x, u t ) + V k-1 t+1 • f t (x, u t ) , (3a) s.t. x = x k t [β k t ] (3b) f t (x, u t ) ∈ X t+1 (3c) u t ∈ U t (x) (3d)
Here β k t ∈Aff(X t ) is a vector of Lagrange multipliers for the constraint x = x k t . We denote a minimizer of (3) by u k t . Its existence is guaranteed by ERCR. Note that constraint (3a) can be seen as an induced constraint on u t . Thus we can define the multifunctions Ũt : R n ⇒ R m by, for all x ∈ R n ,

(4) Ũt (x) := {u ∈ U t (x)|f t (x, u t ) ∈ X t+1 }.
We can easily check that Ũt is convex (by linearity of f t and convexity of U t ) and convex compact valued (as the intersection of a compact convex set and a convex set). Thus (3) can be written as

θ k t = min ut∈ Ũt(x) x∈Aff Xt C t (x, u t ) + V k-1 t+1 • f t (x, u t ) , (5a) s.t. x = x k t . [β k t ] (5b) Now define, for any x ∈ R n : (6) V k t (x) := max V k-1 t (x) , θ k t + β k t , x -x k t ,
and move on to the next time stage t + 1 by defining

x k t+1 = f t x k t , u k t .
Remark 2.1. The assumption that β k t is in Aff(X t ) is made for technical reasons, and loses little generality. Indeed if β k t ∈ R n is an optimal Lagrange multiplier, then so is its projection on Aff(X t ). In practice we would expect Aff(X t ) to be the same dimension for every t. If this dimension happened to be d strictly less than n, then we might change the formulation (by a transformation of variables) so that Aff(X t ) = R d . Remark 2.2. Observe that our algorithm uses V k-1 t+1 when solving the twostage problem (3) at stage t, although most implementations of SDDP and related algorithms proceed backwards and are thus able to use the freshly updated V k t+1 (although see e.g. [START_REF] Chen | A convergent cutting-plane and partialsampling algorithm for multistage linear programs with recourse[END_REF] for a similar approach to the one proposed here). In the stochastic case we present a general framework that encompasses backward passes.

Note that only the last future cost function V T is known exactly at any iteration. All the other ones are lower approximations consisting of the maximum of k affine functions at iteration k. We naturally have the same lower approximation for function W t . Thus we define for any (x, u) in R n+m (7)

W k t (x, u) := C t (x, u) + V k t+1 • f t (x, u) , and recall (8) W t (x, u) := C t (x, u) + V t+1 • f t (x, u) .
Using this notation we have ( 9)

θ k t = min u∈ Ũt(x k t ) W k-1 t x k t , u = W k-1 t x k t , u k t Because for any x ∈ X t+1 and any k ≤ k we have that V k-1 t+1 (x) ≥ V k -1 t+1 (x), it follows that θ k t = min u∈ Ũt(x k t ) W k-1 t x k t , u ≥ min u∈ Ũt(x k t ) W k -1 t x k t , u , ∀k ≤ k, = min u∈ Ũt(x k t ) W k -1 t x k t + x k t -x k t , u , ∀k ≤ k,
which, using convexity of the optimal value function, and the definitions of θ k t and β k t , gives

θ k t ≥ θ k t + β k t , x k t -x k t , ∀k ≤ k.
Since by ( 6)

V k-1 t x k t = max k <k θ k t + β k t , x k t -x k t it follows that θ k t ≥ V k-1 t x k t
and so ( 6) implies (10)

V k t x k t = max V k-1 t x k t , θ k t = θ k t = W k-1 t x k t , u k t .
Figure 1 gives a view of the relations between all these values at a given iteration.

x value V t (x)

x k t W t x k t , u k t V t x k t θ k t = W k-1 t x k t , u k t V k-1 t (x) θ k t + β k t , x -x k t Figure 1.
Relations between notations in the multi-stage case 2.1. Proof of convergence in the deterministic case. We begin by showing some regularity and monotonicity results for the value functions and their approximations.

Under assumptions (H 1 ), we define for t = 0, . . . , T -1, and for all x ∈ R n , the extended value function [START_REF] Philpott | A multistage stochastic programming model for the New Zealand dairy industry[END_REF] Ṽt

(x) = inf u∈Ut(x) C t (x, u) + V t+1 • f t (x, u).
Note that the infimum could be taken on Ũt (x)

⊆ U t (x) as V t+1 = ∞ when f t (x, u) / ∈ X t+1 .
It is convenient to extend the definition to t = T by defining ṼT = V T . We also observe that Ṽt ≤ V t as these are identical on the domain of V t . Lemma 2.2. For t = 0, . . . , T -1, (i) the value function V t is convex and Lipschitz continuous on X t ;

(ii) V k t ≤ Ṽt ≤ V t , and β k t is defined;

(iii) the sequences (β k t ) k∈N are bounded. Proof. (i) We first show the convexity and Lipschitz continuity of V t on X t . We proceed by induction backward in time. By assumption V T is convex and Lipschitz continuous on X T . Assume the result is true for V t+1 . The function Ṽt (x) is convex by lemma 5.1. Now by ERCR, for any x ∈ X t , Ũt (x) = ∅.

This implies that, for x ∈ X t , for u ∈ Ũt (x), Ṽt (x) ≤ C t (x, u) + V t+1 • f t (x, u) < +∞.
By (H 1 (3)) and the induction hypothesis, for any x ∈ X t ,

u → C t (x, u) + V t+1 • f t (x, u)
is lower semi-continuous, and so the compactness of U t (x) ensures that the infimum in the definition of Ṽt (x) is attained, and therefore Ṽt (x) > -∞.

Ṽt is Lipschitz continuous on X t as X t is a compact subset of the relative interior of its domain. Finally remarking that V t (x) = Ṽt (x) if x ∈ X t gives the conclusion. (ii) As observed above the inequality Ṽt ≤ V t is immediate as the two functions are identical on the domain of V t .

To show V k t ≤ Ṽt let us proceed by induction forward in k. Assume that for all t = 0, . .

. , T -1, β k-1 t is defined and V k-1 t ≤ Ṽt . Note that -∞ = V 0 t ≤ Ṽt , so this is true for k = 1 (β 0
t is never used). We now define, for all t = 0, . . . , T -1 and all

x ∈ R n , V k t (x) = min u∈ Ũt(x) C t (x, u) + V k-1 t+1 • f t (x, u).
By hypothesis on Ũt , V k t is convex and finite on X t which strictly contains X t . Thus V k t restricted to Aff(X t ) is subdifferentiable at any point of X t . Moreover by definition of

β k t in (3) (12) β k t ∈ ∂ V k t | Aff(Xt) .
Thus β k t is defined. By the induction hypothesis and inequality Ṽt+1 ≤ V t+1 we have that

V k-1 t+1 • f t ≤ V t+1 • f t .
Thus the definitions of V k t and Ṽt yield [START_REF] Shapiro | Analysis of stochastic dual dynamic programming method[END_REF] V k t ≤ Ṽt . we have by ( 12) that ( 14)

θ k t + β k t , x -x k t ≤ V k t (x) ≤ Ṽt (x)
by [START_REF] Shapiro | Analysis of stochastic dual dynamic programming method[END_REF]. The definition of V k t in (6) gives 14) and the induction hypothesis. Thus (ii) follows for all k by induction.

V k t (x) = max V k-1 t (x) , θ k t + β k t , x -x k t which shows V k t (x) ≤ Ṽt (x) by (
(iii) Finally we show the boundedness of (β k t ) k∈N . By definition of β k t we have for all y ∈ R n , (15)

V k (y) ≥ V k (x k t ) + β k t , y -x k t .
Recall that X t = X t +B t (δ t ), so substituting y = x k t +

δtβ k t 2 β k t in (
15) whenever

β k t = 0 yields β k t ≤ 2 δ t V k t x k t + δ t 2 β k t β k t -V k t x k t .
We define the compact subset X t of dom Ṽt as

X t := X t +B t δt 2 . Now as x k t ∈ X t we have that x k t + δt 2 β k t β k t ∈ X t . Consequently, by (ii), V k t x k t + δ t 2 β k t β k t ≤ max x∈X t Ṽt < +∞.
Moreover by construction the sequence of functions (V k t ) k∈N is increasing, thus

V k t (x k t ) ≥ V 1 t (x k t ) ≥ min x∈Xt V 1 t (x) > -∞. Thus we have that, for all k ∈ N * and t = 0, . . . , T -1, (16) β k t ≤ 2 δ t max x∈X t Ṽt -min x∈Xt V 1 t (x) .
This completes the proof.

Corollary 2.1. Under assumptions (H 1 ), the functions V k t , t = 0, 1, . . . , T -1, are α -Lipschtiz for some constant α for all k ∈ N * . Proof. By ( 6) and (16) the subgradients of V k t are bounded by

α = max t=0,1,...,T -1 2 δ t max x∈X t Ṽt -min x∈Xt V 1 t (x) .
We now prove that both the upper and lower estimates of V t converge to the exact value function under assumptions (H 1 ). Theorem 2.1. Consider the sequence of decisions u k k∈N generated by ( 3) and ( 6), where each u k is itself a sequence of decisions in time

u k = u k 0 , . . . , u k T -1
, and consider the corresponding sequence x k k∈N of state values. Under assumptions (H 1 ), for any t = 0, . . . , T -1 we have that:

lim k→+∞ W t x k t , u k t -V t x k t = 0 and lim k→+∞ V t x k t -V k t x k t = 0.
Proof. The demonstration proceeds by induction backwards in time. At time t + 1, the induction hypothesis is the second statement of the theorem. That is, lim

k→+∞ V t+1 x k t+1 -V k t+1 x k t+1 = 0.
In other words the cuts for the future cost function tend to be exact at x k t+1 as k tends to ∞. The induction hypothesis is clearly true at the last time stage T for which we defined the approximate value function V k T to be equal to the (known) end value function V T . Now let us consider time t and choose K ε to be the set of indices k such that:

(1)

V t x k t + ε < W t x k t , u k t < +∞, (2) V t+1 x k t+1 -θ k t+1 < ε 2 . Note that the induction hypothesis states lim k→+∞ V t+1 x k t+1 -V k t+1 x k t+1 = 0
and [START_REF] Philpott | On the convergence of stochastic dual dynamic programming and related methods[END_REF] gives 2) is satisfied for every k large enough. Thus K ε is finite if and only if the number of indices satisfying condition (1) is finite.

V k t+1 x k t+1 = θ k t+1 so lim k→+∞ V t+1 x k t+1 -θ k t+1 = 0. Hence condition (
Let k 1 , k 2 be two indices in K ε , k 1 being smaller than k 2 . Suppose that a new cut has just been added to the approximate future cost function at time t + 1. Because of ( 6), we have that for any k ∈ N and any x ∈ X t+1

V k t+1 (x) ≥ θ k t+1 + β k t+1 , x -x k t+1 .
It follows that the approximate future cost evaluated at (x k 2 t , u k 2 t ) satisfies

C t x k 2 t , u k 2 t + θ k 1 t+1 + β k 1 t+1 , x k 2 t+1 -x k 1 t+1 ≤ C t x k 2 t , u k 2 t + V k 1 t+1 x k 2 t+1 , = W k 1 t x k 2 t , u k 2 t , by definition (7) of W k 1 t . Now, because k 1 < k 2 , W k 1 t x k 2 t , u k 2 t ≤ W k 2 -1 t x k 2 t , u k 2 t , so (3)
and [START_REF] Philpott | On the convergence of stochastic dual dynamic programming and related methods[END_REF] give

C t x k 2 t , u k 2 t + θ k 1 t+1 + β k 1 t+1 , x k 2 t+1 -x k 1 t+1 ≤ W k 2 -1 t x k 2 t , u k 2 t = min ut∈ Ũt x k 2 t W k 2 -1 t x k 2 t , u t ≤ min ut∈ Ũt x k 2 t W t x k 2 t , u t = V t x k 2 t .
Now, using the fact that k 2 ∈ K ε , we have

V t x k 2 t + ε < W t x k 2 t , u k 2 t which implies C t x k 2 t , u k 2 t + θ k 1 t+1 + β k 1 t+1 , x k 2 t+1 -x k 1 t+1 < W t x k 2 t , u k 2 t -ε. Now, the definition (8) of W t implies W t x k 2 t , u k 2 t = C t x k 2 t , u k 2 t + V t+1 x k 2 t+1 so ε < V t+1 x k 2 t+1 -θ k 1 t+1 -β k 1 t+1 , x k 2 t+1 -x k 1 t+1 , or (17) ε < V t+1 x k 1 t+1 -θ k 1 t+1 + V t+1 x k 2 t+1 -V t+1 x k 1 t+1 -β k 1 t+1 , x k 2 t+1 -x k 1 t+1 Now, k 1 ∈ K ε implies V t+1 x k 1 t+1 -θ k 1 t+1 < ε 2 ,
and by (i) of lemma (2.2) V t is Lipschitz continuous and thus there is some γ 1 such that:

V t+1 x k 2 t+1 -V t+1 x k 1 t+1 ≤ γ 1 x k 1 t+1 -x k 2 t+1 .
Furthermore (iii) of lemma 2.2 ensures that (β k t ) k∈N is bounded. So there exists a constant γ 2 > 0 such that:

-β k 1 t+1 , x k 2 t+1 -x k 1 t+1 ≤ γ 2 x k 1 t+1 -x k 2 t+1 . Finally, taking γ = γ 1 + γ 2 we obtain ε < ε 2 + γ x k 2 t+1 -x k 1 t+1 , giving (18) ε 2 < γ x k 2 t+1 -x k 1 t+1
. It follows that K ε has to be finite. Otherwise, since the state space X t+1 is compact, we could find a convergent subsequence of states satisfying (18), and passing to the limit would lead to ε 2 ≤ 0. This proves the first part of the theorem at time t.

We now have to show the induction hypothesis, namely

lim k→+∞ V t x k t -V k t x k t = 0
for time t. Recall [START_REF] Philpott | On the convergence of stochastic dual dynamic programming and related methods[END_REF] gives

V k t x k t = θ k t = W k-1 t x k t , u k t , = C t x k t , u k t + V k-1 t+1 x k t+1 .
Using the definition (8) of W t , we can replace C t x k t , u k t to get

V k t x k t = W t x k t , u k t + V k-1 t+1 x k t+1 -V t+1 x k t+1 .
We have just demonstrated above that

η k t = W t x k t , u k t -V t x k t k→∞ ---→ 0 so V k t x k t = V t x k t + η k t + V k-1 t+1 x k t+1 -V t+1 x k t+1 .
The induction hypothesis at time t + 1 gives

V k t+1 x k t+1 -V t+1 x k t+1 k→∞ ---→ 0,
which by virtue of Lemma 5.2 (with V t+1 replacing f ) implies

3 lim k→+∞ V t+1 x k t+1 -V k-1 t+1 x k t+1 = 0 so V k t x k t -V t x k t k→∞ ---→ 0.
which gives the result.

Theorem 2.1 indicates that the lower approximation at each iteration tends to be exact on the sequence of state trajectories generated throughout the algorithm. This does not mean that the future cost function will be approximated well everywhere in the state space. It only means that the approximation gets better and better in the neighbourhood of an optimal state trajectory.

3. The stochastic case with a finite distribution 3.1. Stochastic multistage problem formulation. Let us now consider that the cost function and dynamics at each time t are influenced by a random outcome that has a discrete and finite distribution. We write the problem on the complete tree induced by this distribution. The set of all nodes is denoted by N and {0} is the root node. We denote nodes by m and n. (We trust that the context will dispel any confusion from the use of m and n as dimensions of variables u and x.) A node n here represents a time interval and a state of the world (which has probability Φ n ) that pertains over this time interval. We say that a node n is an ascendent of m if it is on the path from the root node to node m (including m). We will denote a(m) the set of all ascendents of m, and the depth of node n is one less than the number of its ascendents. For simplicity we identify this with a time index t, although the results hold true for scenario trees for which this is not the case. For every node m ∈ N \{0}, p(m) represent its parent, and r(m) its set of children nodes. Finally L is the set of leaf nodes of the tree.

This gives the following stochastic program:

min x,u n∈N \{L} m∈r(n) Φ m C m (x n , u m ) + m∈L Φ m V m (x m ) (19a) s.t. x m = f m x p(m) , u m , ∀m ∈ N \{0}, ( 19b
)
x 0 is given, (19c) x m ∈ X m , ∀m ∈ N , (19d)
u m ∈ U m (x p(m) ), ∀m ∈ N \{0}. ( 19e
)
The reader should note that randomness (that appears in the cost and in the dynamics) is realized before the decision is taken in this model. Hence the control affecting the stock 4 x n is actually indexed by m, a child node that affect the system. Hence there is no reason why variable xn should be called a state variable and we prefer calling it a stock.

of n. Put differently, the control adapts to randomness: there are as many controls as there are children nodes of n.

We have a future cost function for each node n ∈ N which is defined by

(20) V n (x n ) = m∈r(n) Φ m Φ n min um∈Um(xn) C m (x n , u m ) + V m (f m (x n , u m ))
Wm(xn,um)

.

We make the following assumptions (H 2 ):

(1) for all n ∈ N , X n is convex compact;

(2) for all m ∈ N \{0}, the multifunction U m is convex and convex compact valued;

(3) all functions C n , n ∈ N \L, V m , m ∈ L, are convex lower semicontinuous proper functions; (4) for all m ∈ N \{0}, the functions f m are linear;

(5) for all m ∈ L, V m is Lipschitz-continuous on X m ; (6) There exists δ > 0 such that for all nodes n ∈ N \L, (a

) ∀x ∈ X n + B(δ), ∀m ∈ r(n), f m (x, U m (x)) ∩ X m = ∅, (b) ∀x ∈ X n + B(δ), ∀u ∈ U m (x), C n (x, u) < ∞.
In general the future cost function at each node can be different from those at other nodes at the same stage. In the special case where the stochastic process defined by the scenario tree is stagewise independent, the future cost function is identical at every node at stage t. Some form of stagewise independence is typically assumed in applications as it enables cuts to be shared across nodes at the same stage, however we do not require this for our proof.

The algorithm that we consider is an extension of the deterministic algorithm of the previous section applied, at each iteration, to a set of nodes chosen randomly in the tree at which we update estimates of the future cost function. We assume that all other nodes have null updates, in the sense that they just inherit the future cost function from the previous iteration.

We now describe the algorithm formally. We start the process with θ0 n = -∞, β0 n = 0, for each n ∈ N , and impose V k n = V n for all nodes n ∈ L and all k ∈ N. We then carry out a sequence of simulations and updates of the future cost functions as follows.

Simulation: Starting at the root node, generate stocks and decisions for all possible successors (in other words, visit the whole tree forward) by solving (20) with V k-1 instead of V . Denote the obtained stock variables by (x k n ) n∈N and the control variables by (u k n ) n∈N \{0} . Also, for each node n ∈ N , impose

θ k n = V k-1 n (x k n ) and β k n ∈ ∂V k-1 n (x k n )
. Update: Select non-leaf nodes n 1 , n 2 , . . . , n I in the tree. For each i,

x k n i is a random variable which is equal to one of the x k n . For each selected node n i , and for every child node m of node n i , solve: θk m = min

um∈R m x∈Aff Xn i C m (x, u m ) + V k-1 m • f m (x, u m ) , (21a) s.t. x = x k n i [ βk m ] (21b) u m ∈ U m (x) (21c) f m (x, u m ) ∈ X m (21d)
As before βk m is a Lagrange multiplier at optimality. We also define the multifunctions Ũm :

x → {u ∈ U m (x)|f m (x, u m ) ∈ X m }.
For each selected node n i , replace the values θ k n i and β k n i obtained during the simulation with:

θ k n i = m∈r(n i ) Φ m Φ n i θk m and β k n i = m∈r(n i ) Φ m Φ n i βm .
Finally, we update all future cost functions. For every node n

(22) V k n (x) := max V k-1 n (x) , θ k n + β k n , x -x k n , x ∈ X t .
Note that we actually only update future cost functions on the selected nodes. Since the cuts we add at all other nodes are binding on the current model (by construction in the simulation), there is no point in storing them. Therefore, in practice, one does not need to sample the whole scenario tree but just enough to attain all selected nodes. In our proof, we need to look at what happens even on the nodes that are not selected.

The way we select nodes at which to compute cuts varies with the particular algorithm implementation. For example DOASA uses a single forward pass to select nodes, and then computes cuts in a backward pass. We represent these selections of nodes using a selection random variable y k = (y k n ) n∈N that is equal to 1 if node n is selected at iteration k and 0 otherwise. This gives a selection stochastic process (y k ) k∈N , taking values in {0, 1} |N \L| , that describes a set of nodes in the tree at which we will compute new cuts in iteration k. We let (F k ) k∈N denote the filtration generated by (y k ) k∈N .

To encompass algorithms such as DOASA and SDDP the selection stochastic process can be viewed as consisting of infinitely many finite subsequences, each consisting of τ > 0 selections (consisting for example of a sequence of selections of nodes in a backward pass). This cannot be done arbitrarily, and the way that (y k ) k∈N is constructed must satisfy some independence conditions from one iteration to the next. m is independent of F kτ -1 ; (iii) ∀n ∈ N \L, P(ỹ k n = 1) > 0. Property (i) guarantees that when τ > 1, the updating of cutting planes is done backwards between steps kτ and (k + 1)τ . This means that if the linear approximation of the value function V n is updated at step kτ + κ then neither it or any approximation at any ascendant node has been updated since step kτ -1. This implies, as shown in lemma 5.3, that x kτ +κ has not changed since the step kτ , i.e., if y kτ +κ n = 1 then x kτ +κ = x kτ . Property (ii) provides the independence of the selections that we will use to prove convergence and property (iii) guarantees that all nodes are selected with positive probability. Without any independence assumption it would be easy to create a case in which the future cost function at a given node is updated only when the current stock variable on this node is in a given region, for instance. In such a case the future cost function could not gather any information about the other parts of the space that the stock variable might visit. In other words, this independence assumption ensures that the values that are optimal can be attained an infinite number of times. We remark that there is no independence assumption over the nodes n for (y k n ) n∈N \L at k fixed. Thus the selection process could be forced to select whole branches of the tree for example, as it would for the CUPPS algorithm. More generally, we have independence when for fixed τ , (y kτ ) k∈N is i.i.d and the next τ -1 selection values are determined deterministically from y kτ , more precisely if for all κ ∈ {0, . . . , τ -1}, there is a deterministic function φ κ such that y kτ +κ = φ κ (y kτ ). On the other hand we have independence when the selection subsequence (y kτ , y kτ +1 , . . . , y kτ +τ -1 ) k∈N is i.i.d.

We will make use of the following definitions, where m ∈ r(n):

(24) W m (x n , u m ) := C m (x n , u m ) + V m (f m (x n , u m )) (25) W k m (x n , u m ) := C m (x n , u m ) + V k m (f m (x n , u m ))
In the case where node n ∈ N is selected at iteration k, in other words n = n i , these definitions then give

θk m = min u∈ Ũm(x k n ) W k-1 m x k n , u = W k-1 m x k n , u k m .
Because for any x ∈ X m and any k ≤ k we have that

V k -1 m (x) ≤ V k-1 m (x), it follows that θk m = min u∈ Ũm(x k n ) W k-1 m x k n , u ≥ min u∈ Ũm(x k n ) W k -1 m x k n , u , ∀k ≤ k, = min u∈ Ũm(x k n ) W k -1 m x k n + x k n -x k n , u , ∀k ≤ k,
which, using convexity of the value function of this latter problem and the definitions of θk m and βk m , gives

θk m ≥ θk m + βk m , x k n -x k n , ∀k ≤ k.
and taking conditional expectations with probabilities Φm Φn , we obtain

θ k n ≥ θ k n + β k n , x k n -x k n , ∀k ≤ k.
Since by ( 22)

V k-1 n x k n = max k <k θ k n + β k n , x k n -x k n it follows that θ k n ≥ V k-1 n
x k t , and so ( 22) implies (once again, only in the case when

n = n i ) (26) V k n x k n = max V k-1 n x k n , θ k n = θ k n = m∈r(n) Φ m Φ n W k-1 m x k n , u k m .
Note that because of the way x k n and θ k n are defined during simulation for the non-selected nodes, we have

V k n x k n = max V k-1 n x k n , θ k n = θ k n , ∀n ∈ N .
3.2. Proof of convergence in the stochastic case. For every n ∈ N \ L we can define under assumptions (H 2 ) the extended value function

Ṽn (x) = m∈r(n) Φ m Φ n inf u∈ Ũm(x) C m (x, u) + V m • f m (x, u),
and we note that Ṽn is finite on X n . We now state a lemma analogous to lemma 2.2.

Lemma 3.1. For every n ∈ N , (i) the value function V n is convex and Lipschitz-continuous on

X t ; (ii) V k n ≤ Ṽn ≤ V n , and
β k n is defined; (iii) the sequences (β k n ) k∈N are bounded, thus there is α n such that V k n is α n -Lipschitz.
Proof. We give only a sketch of the proof as it follows exactly the proof of its deterministic counterpart lemma 2.2.

(i) By induction backward on the tree Ṽn , is convex and finite valued on X n as the positive sum of convex finite valued functions, and thus Lipschitz continuous on X n leading to the result as Ṽn = V n on X n . (ii) Assume that for all n ∈ N \L we have

V k-1 n ≤ Ṽn . We define, for a node n ∈ N \L x ∈ R n , V k n (x) = m∈r(n) Φ m Φ n min u∈ Ũn(x) C m (x, u) + V k-1 m • f m (x, u).
By hypothesis on Ũm , V k n is convex and finite on X t thus its restriction on Aff(X t ) is subdifferentiable on X t . By definition βk m ∈ ∂ V k n (x k m ), and thus βk m is defined. By the induction hypothesis and inequality Ṽm ≤ V m we have that

∀m ∈ r(n), V k-1 m • f m ≤ V m • f m .
Thus definitions of V k n and Ṽn yield V k n ≤ Ṽn . By definition of β k n and construction of V k n we have that V k n ≤ Ṽn . Induction leads to inequality (ii). (iii) Finally we show the boundedness of (

β k n ) k∈N . As β k n is an element of ∂V k (x k n ), we have V k (y) ≥ V k (x k n ) + β k n , y -x k n . so substituting, if β k n = 0, y = x k n + δβ k n 2 β k n in (15) yields β k n ≤ 2 δ V k n x k n + δ 2 β k n β k n -V k n x k n .
Thus we have that, for all k ∈ N and n ∈ N , (27)

β k n ≤ 2 δ max x∈Xn+B(δ/2) Ṽn -min x∈Xn V 1 n (x) .
Which ends the proof.

We also make use of the following lemma.

Lemma 3.2. Let n be a node in N \L. Suppose that there is some integer τ > 0 such that for all m ∈ r(n) we have

lim k→+∞ V m x kτ m -V kτ m x kτ m = 0.
Then

lim k→+∞ m∈r(n) Φ m Φ n W m x kτ n , u kτ m -V n x kτ n = 0.
Proof. Choose K ε to be the set of indices k, multiples of τ , such that:

(1)

V n x k n + ε < m∈r(n) Φm Φn W m x k n , u k m < +∞, (2)
m∈r(n) Φm Φn V m x k m -θ k m < ε 2 .
Note that because of the hypothesis and (26) the quantity on the left-hand side of condition (2) converges to 0 as k goes to infinity. Hence condition (2) is satisfied for all k large enough and if K ε is finite, then it is the number of indices satisfying condition (1) that has to be finite.

Because of (22), we have that for any k ∈ N, any child node m of n, and any x ∈ X m , (28)

V k m (x) ≥ θ k m + β k m , x -x k m .
Let k 1 , k 2 be two indices in K ε , k 1 being smaller than k 2 . It follows from (28) applied at k = k 1 , that the approximate future cost evaluated at (

x k 2 n , u k 2 m ) satisfies C m x k 2 n , u k 2 m + θ k 1 m + β k 1 m , x k 2 m -x k 1 m ≤ C m x k 2 n , u k 2 m + V k 1 m x k 2 m , = W k 1 m x k 2 n , u k 2 m . and k 1 < k 2 implies W k 1 m x k 2 n , u k 2 m ≤ W k 2 -1 m x k 2 n , u k 2 m .
Thus

m∈r(n) Φ m Φ n C m x k 2 n , u k 2 m +θ k 1 m + β k 1 m , x k 2 m -x k 1 m ≤ m∈r(n) Φ m Φ n W k 2 -1 m x k 2 n , u k 2 m , = m∈r(n) Φ m Φ n min um∈ Ũm x k 2 n W k 2 -1 m x k 2 n , u m , ≤ m∈r(n) Φ m Φ n min um∈ Ũm x k 2 n W m x k 2 n , u m , = V n x k 2 n . Now, since k 2 ∈ K ε , V n x k 2 n + ε < m∈r(n) Φ m Φ n W m x k 2 n , u k 2 m which gives m∈r(n) Φ m Φ n C m x k 2 n , u k 2 m + θ k 1 m + β k 1 m , x k 2 m -x k 1 m < m∈r(n) Φ m Φ n W m x k 2 n , u k 2 m -ε.
Now recall the definition (24) of W m which gives

m∈r(n) Φ m Φ n W m x k 2 n , u k 2 m = m∈r(n) Φ m Φ n C m x k 2 n , u k 2 m + m∈r(n) Φ m Φ n V m f m x k 2 n , u k 2 m .
Substituting and observing

x k 2 m = f m x k 2 n , u k 2 m gives ε < m∈r(n) Φ m Φ n V m x k 2 m -θ k 1 m -β k 1 m , x k 2 m -x k 1 m , yielding ε < m∈r(n) Φ m Φ n V m x k 1 m -θ k 1 m + m∈r(n) Φ m Φ n V m x k 2 m -V m x k 1 m (29)
-

m∈r(n) Φ m Φ n β k 1 m , x k 2 m -x k 1 m . Now, k 1 ∈ K ε implies m∈r(n) Φ m Φ n V m x k 1 m -θ k 1 m < ε 2 .
Furthermore by (i) of lemma 3.1 there exists a constant γ 1 > 0 such that

V m x k 2 m -V m x k 1 m ≤ γ 1 x k 1 m -x k 2 m ,
and by (iii) of lemma 3.1, there exists a constant γ 2 > 0 such that

-β k 1 m , x k 2 m -x k 1 m ≤ γ 2 x k 1 m -x k 2 m .
Collecting terms and taking γ = γ 1 + γ 2 we obtain

ε < ε 2 + γ m∈r(n) Φ m Φ n x k 2 m -x k 1 m , giving (30) ε 2 < γ m∈r(n) Φ m Φ n x k 2 m -x k 1 m .
Hence K ε has to be finite. Otherwise, because the space (X m ) is compact, we could find a convergent subsequence of states satisfying (30), and passing to the limit would lead to ε 2 ≤ 0. Theorem 3.1. Consider the sequence of decisions u k k∈N generated by the above described procedure under assumptions (H 2 ), where each u k is itself a set of decisions on the complete tree, and consider the corresponding sequence of state values x k k∈N . Assume that the selection process is τadmissible for some integer τ > 0. Then we have that, P-almost surely:

lim k→+∞ m∈r(n) Φ m Φ n W m x kτ n , u kτ m -V n x kτ n = 0. and lim k→+∞ V n x kτ n -V kτ n x kτ n = 0.
Proof. Because the selection process for nodes in the update step is stochastic, decision variables as well as approximate future cost functions are stochastic throughout the course of the algorithm. Thus, during the whole proof, all equalities or inequalities are taken P-almost surely.

The demonstration follows the same approach as the proof of Theorem 2.1. Let T be the maximum depth of the tree. We procede by backward induction on nodes of fixed depth. The induction hypothesis is

lim k→+∞ V m x kτ m -V kτ m x kτ m = 0
for each node m of depth t + 1. Since for every leaf of the tree those two quantities are equal, by definition, the induction hypothesis is true for every node n ∈ L. For any arbitrary node n of depth t that is not a leaf, lemma 3.2 gives the first statement of the theorem. We now have to show the induction hypothesis, namely

lim k→+∞ V n x kτ n -V kτ n x k n = 0
for every node n of depth t.

We start by proving the result for iterations kτ such that n is selected in the next τ -1 steps, i.e. such that ỹk n = 1. Define κ k ∈ {0, . . . , τ -1} such that y kτ +κ k = 1. Recall that by lemma 5.3 we have x kτ +κ k n = x kτ n . We have by ( 26)

V kτ +κ k n x kτ +κ k n = V kτ +κ k n x kτ n = m∈r(n) Φ m Φ n min um∈ Ũm(x kτ n ) W kτ +κ k -1 m x kτ n , u m ≥ m∈r(n) Φ m Φ n min um∈ Ũm(x kτ n ) W kτ -1 m x kτ n , u m = m∈r(n) Φ m Φ n W kτ -1 m x kτ n , u kτ m which implies V kτ +κ k n x kτ n ≥ m∈r(n) Φ m Φ n C m x kτ n , u kτ m + V kτ -1 m x kτ m , = m∈r(n) Φ m Φ n W m x kτ n , u kτ m + V kτ -1 m x kτ m -V m x kτ m .
We have just demonstrated above that

η kτ n = m∈r(n) Φ m Φ n W m x kτ n , u kτ m -V n x kτ n k→∞ ---→ 0.
Thus,

V kτ +κ k n x kτ n ≥ V n x kτ n + η kτ n + m∈r(n) Φ m Φ n V kτ -1 m x kτ m -V m x kτ
Φ m Φ n V kτ -1 m x kτ m -V m x kτ m k→∞ ---→ ỹk n =1 0. But V n (x kτ n ) ≥ V kτ +κ k n (x kτ n ) ≥ V n (x kτ n ) + ηkτ which gives (31) V n x kτ n -V kτ +κ k n x kτ n k→∞ ---→ ỹk n =1 0.
Thus lemma 5.2 applied with κ = τ gives

V n x kτ n -V kτ +κ k -τ n x kτ n k→∞ ---→ ỹk n =1 0,
and by monotonicity we have

V kτ +κ k -τ n ≤ V kτ n ≤ V n , which finally yields (32) V n x kτ n -V kτ n x kτ n k→∞ ---→ ỹk n =1
0.

Now we prove that the values also converge for the iterations k such that ỹk n = 0, i.e. the iterations for which node n is not selected between step kτ and step (k + 1)τ -1. By contradiction, suppose the values do not converge. Then by lemma 5.2 we have that V n (x kτ n ) -V kτ -1 n (x kτ n ) does not converge to 0. It follows that there is some ε > 0 such that K ε is infinite where

(33) K := {k ∈ N|V n x kτ n -V kτ -1 n x kτ n ≥ ε}.
Let z j denote the j-th element of the set {y kτ n |k ∈ K ε }. Note that the random variables V kτ -1 and x kτ n are measurable with respect to F kτ -1 := σ (y k ) k <kτ , and thus so is 1 k∈Kε from which ỹk n is independent. Moreover the σ-algebra generated by the past realisations of ỹk n is included in F kτ -1 . This implies by lemma 5.4 that random variables (z j ) j∈N are i.i.d. and share the same probability law as ỹ0 n . According to the Strong Law of Large Numbers [5, page 294] applied to the random sequence (z j ) j∈N , we should then have

1 N N j=1 z j N →+∞ -----→ E(z 1 ) = E(ỹ 0 n ) = P ỹ0 n = 1 > 0.
However, K ε ∩ {ỹ k n = 1} is finite because of (31) thus we know that there is only a finite number of indices j such that z j = 1, the rest being equal to 0. So 1

N N j=1 z j N →+∞ -----→ 0,
which is a contradiction. This shows that

V n x kτ n -V kτ -1 n x kτ n k→∞ ---→ ỹk n =0 0.
and monotonicity shows that,

V n x kτ n -V kτ n x kτ n k→∞ ---→ ỹk n =0 0.
which completes the induction.

3.3. Application to known algorithms. In order to illustrate on our result we will apply it to two well known algorithms. For simplicity we will assume that the tree represents a T -step stochastic decision problem in which every leaf of the tree is of depth T . We first define the CUPPS algorithm [START_REF] Chen | A convergent cutting-plane and partialsampling algorithm for multistage linear programs with recourse[END_REF] in this setting. Here at each major iteration we choose a T -1-step scenario and compute the optimal trajectory while at the same time updating the value function for each node of the branch. In our setting, this uses a 1-admissible selection process (y k ) k∈N defined by an i.i.d. sequence of random variables, with y 0 selecting a single branch of the tree. Theorem 3.1 shows that for every node n the upper and lower bound converges, that is

lim k→+∞ m∈r(n) Φ m Φ n W m x k n , u k m -V n x k n = 0 and lim k→+∞ V n x k n -V k n x k n = 0.
We now place the SDDP algorithm [START_REF] Pereira | Multi-stage stochastic optimization applied to energy planning[END_REF] and DOASA algorithm [START_REF] Philpott | On the convergence of stochastic dual dynamic programming and related methods[END_REF] in our framework. There are two phases in each major iteration of the SDDP algorithm, namely a forward pass, and a backward pass of T -1 steps. Given a current polyhedral outer approximation of the Bellman function (V k-1 n ) n∈N \L , a major iteration k of the SDDP algorithm consists in:

• selecting uniformly a number N of scenarios (N = 1 for DOASA); • simulating the optimal strategy for the problem, that is solving problem (21) to determine a trajectory (for each scenario) (x k nt ) t∈{0,...,T -1} where (n t ) t∈{0,...,T -1} defines one of the selected scenarios;

• For t = T -1 down to t = 0 for each scenario solving problem (21) with V k m instead of V k-1 m ,
and defining

V k nt (x) = max{V k-1 nt (x), θ k nt + β k nt , x -x k nt }.
SDDP fits into our framework as follows. Given N , we define the T -1admissible selection process, (y (T -1)k ) k∈N by an i.i.d. sequence of random variables with y 0 selecting uniformly a set of N pre-leaves (i.e. nodes whose children are leaves) of the tree. Then for κ ∈ {1, . . . , T -2}, k ∈ N, n ∈ N \L, we define

y k(T -1)+κ n := 1 if there exist m ∈ r(n) such that y k(T -1)+κ-1 m = 1 0 otherwise.
This algorithm defines an SDDP algorithm with N randomly sampled forward passes per stage. The cut sharing feature used in SDDP when random variables are stagewise independent can be easily incorporated. Since for every node n of the tree (excepting the leaves) there is a κ such that P(y k(T -1)+κ n = 1) > 0, theorem 3.1 guarantees the convergence of the lower bound of the SDDP algorithm for every node.

Discussion

The convergence result we have proved assumes that we compute new cuts at scenario-tree nodes that are selected independently from the history of the algorithm. This enables us to use the Strong Law of Large Numbers in the proof. Previous results for multistage stochastic linear programming [START_REF] Philpott | On the convergence of stochastic dual dynamic programming and related methods[END_REF] require a selection process that visits each node in the tree infinitely often, which is a weaker condition than independence, since it follows by the Borel-Cantelli Lemma [5, page 288]. An example would be a deterministic round-robin selection. We do not have a proof of convergence for such a process in the nonlinear case. It is important to observe that the polyhedral form of V t that was exploited in the proof [START_REF] Philpott | On the convergence of stochastic dual dynamic programming and related methods[END_REF] is absent in our problem, and this difference could prove to be critical.

The convergence result is proved for a general scenario tree. In SDDP algorithms, the random variables are usually assumed to be stagewise independent (or made so by adding state variables). This means that the future cost functions V m (x) are the same at each node m at depth t. This allows cutting planes in the approximations to be shared across these nodes. The convergence result we have shown here applies to this situation as a special case.

Observe that the class of algorithms covered by our result is larger than the examples presented in the literature. For example an algorithm where we select randomly a node on the whole tree, and then update backwards from there is proven to converge. One could also think of combining SDDP and CUPPS algorithms.

In the case where one would want to add cuts at different nodes in the tree in the update step of our procedure, the solving of the subproblems can be done in parallel. This is the case in CUPPS, where a whole branch of the tree is selected at each iteration. It also allows us to consider different selection strategies, where nodes at a given iteration could be selected throughout the tree depending on some criteria defined by the user. In the first few iterations, this could highly increase efficiency of the approximation and, because the solving of the subproblems can be parallelized, would not be very time-consuming. One should bear in mind however that, at some point, the algorithm has to come back to an appropriate selection procedure, i.e. one that satisfies the independence assumption, in order to ensure convergence of the algorithm. 5. Appendix: Technical lemmas Lemma 5.1. If J : R m → R ∪ {∞} is convex, U : R n ⇒ R m is convex then φ(x) := min u∈U (x) J(u) is convex. Moreover if J is lower-semicontinuous, and U compact non-empty valued, then the infimum exists and is attained.

Proof. We define I(u, x) := 0 if u ∈ U(x) +∞ otherwise Then φ(x) = min u∈R m J(u) + I(u, x). Fix u 1 ∈ U(x 1 ) and u 2 ∈ U(x 2 ), then for every λ ∈ [0, 1] λu 1 + (1 -λ)u 2 ∈ U(λx 1 + (1 -λ)x 2 ) by convexity of U. This shows that I(u, x) is convex, whereby φ is convex as the marginal function of a jointly convex function. The second part of the lemma follows immediately from the compactness U and lower-semicontinuity of J. Lemma 5.2. Suppose f is convex and X is compact, and suppose for any integer κ, the sequence of α-Lipschitz convex functions f k , k ∈ N satisfies f k-κ (x) ≤ f k (x) ≤ f (x) , for all x ∈ X .

Then for any infinite sequence x k ∈ X

lim k→+∞ f x k -f k x k = 0 ⇐⇒ lim k→+∞ f x k -f k-κ x k = 0.
Proof. If lim k→+∞ f x k -f k-κ x k = 0 then pointwise monotonicity of f k shows that lim k→+∞ f x k -f k x k = 0. For the converse, suppose that the result is not true. Then there is some subsequence f k(l) l∈N and x k(l) ∈ X with (34) lim k→+∞ f x k(l) -f k(l) x k(l) = 0 and ε > 0, L ∈ N with f x k(l) -f k(l)-κ x k(l) > ε for every l > L. Since X is compact, we may assume (by taking a further subsequence) that x k(l) l∈N converges to x * ∈ X . For sufficiently large l, the Lipschitz continuity of f k(l) and f k(l)-κ gives f k(l) (x * ) -f k(l) x k(l) ≤ α x k(l) -x * < ε 4 , f k(l)-κ x k(l) -f k(l)-κ (x * ) ≤ α x k(l) -x * < ε 4 , and (34) implies that for sufficiently large l f x k(l) -f k(l) x k(l) < ε 4 .

We have which shows that z m+1 is independent of z and equal in law to y 0 . Induction over m completes the proof.

P

Definition 1 .

 1 Let τ be a positive integer. The process (y k ) k∈N is called a τ -admissible selection process if (i) ∀m ∈ N \L, ∀k ∈ N, ∀κ ∈ {0, . . . , τ -1},y kτ +κ m = 1 =⇒ ∀n ∈ a(m), y kτ n = y kτ +1 n = • • • = y kτ +κ-1 n = 0;and the process defined by (23) ỹk n := max{y kτ n , y kτ +1 n , y kτ +2 n , . . . , y kτ +τ -1 n } satisfies (ii) for all m ∈ N \L, (ỹ k m ) k∈N is i.i.d. and for all k ∈ N, and all m ∈ N \L, ỹk

  of lemma 5.2 (with V m replacing f ) 5 implies lim k→+∞ V m x kτ m -V kτ -1

ν=0 P

 ν=0 {z = b} ∩ {z m+1 = i} ∩ {k(1) = k 1 , . . . , k(m) = k m } = ∞ {z = b} ∩ {k(1) = k 1 , . . . , k(m) = k m } ∩{y ν = i} ∩ {ν = k(m + 1)} = ∞ ν=0 P y ν = i P {z = b} ∩ {k(1) = k 1 , . . . , k(m) = k m } ∩{ν = k(m + 1)} = P y 0 = i P {z = b} ∩ {k(1) = k 1 , . . . , k(m) = k m } .For the last equality we have used the fact that (y k ) is i.i.d. and the fact that k(m + 1) is almost surely finite and thus {ν = k(m + 1)} ν∈N is a partition of the set of events.Summing over the possible realisations of k(1), . . . , k(m), we obtainP {z = b} ∩ {z m+1 = i} = P z = b P(y 0 = i).Now summing over the possible realisations of b shows that z m+1 is equal in law to y 0 . Thus P {z = b} ∩ {z m+1 = i} = P {z = b} ∩ {y 0 = i} = P z = b P(y 0 = i) = P z = b P(z m+1 = i)

Corollary 2.1 ensures the α-Lipschitz assumption on V k t+1 , and the other assumptions are obviously verified.

We do not make any stagewise independence assumptions on the random variables

Lemma 3.1 (iii) provides a Lipschitz condition on V k m .

This requires that the choice of optimal control among the set of minimizers is deterministic (say that with minimum norm).

Acknowledgments.

The first author was supported in this research by a grant from the OSIRIS Department at EDF R&D, France. The authors also wish to thank Kengy Barty for useful discussions on earlier versions of this paper.

The first author was supported in this research by a grant from the OSIRIS Department at EDF R&D, France.

It follows that

is greater than ε, and the other three terms each have an absolute value smaller than ε/4. Consequently f k(l) (x * ) > f k(l)-κ (x * ) + ε 4 , for infinitely many l which contradicts the fact that f k (x * ) is bounded above by f (x * ). Lemma 5.3. If (y k ) k∈N is a τ -admissible selection process then for all k ∈ N, κ ∈ {0, . . . , τ -1}, and all n ∈ N \L we have

Proof. Let n, k and κ be such that y kτ +κ n = 1. Let a(n) := (n 0 , n 1 , . . . , n t ) be the sequence of ascendents of n t := n, i.e. n 0 is the root node, and for all t < t, n t = p(n t +1 ). Define the hypothesis H(t, κ) :

(a)

Let κ < κ and assume that for κ and all t ≤ t, H(t , κ ) holds true. This is satisfied for κ = 0. Let t < t and assume H(t , κ + 1) is true. Since x 0 is fixed, this is satisfied for t = 0. By definition of u kτ +κ +1 n t+1 we have

thus by H(t , κ + 1) (a) we have

Now as n t +1 is an ascendent of n and κ < κ by property (i) of definition 1, we have that the representation of V n t +1 is not updated at iteration κ , i.e.

V kτ +κ n t +1 = V kτ +κ -1

.

And thus

) and assume that for all k ∈ N, y k is independent of B k . Let k(j) denote the j th integer such that w k = 1, i.e. k(0) = 0 and for all j > 0,

Finally we define all j > 0, the j th value of (y k ) such that w k = 1, i.e.

z j := y k(j) .

Then (z k ) k∈N is a sequence of i.i.d. random variables equal in law to y 0 .

Proof. Let Y denote the support of y 0 . We start with z 1 . For i ∈ Y ,