Kengy Barty

AND Pierre Carpentier

Pierre Girardeau

DECOMPOSITION OF LARGE-SCALE STOCHASTIC OPTIMAL CONTROL PROBLEMS

Keywords: 1991 Mathematics Subject Classification. 93E20, 49M27, 49L20. Key words and phrases. Stochastic optimal control, Decomposition methods, Dynamic programming. 1

come

Introduction

Stochastic optimal control is concerned about finding strategies to manage dynamical systems in an optimal way, with respect to some cost function. The particularity of such optimization problems is that the optimization variables we deal with are random variables. Indeed, the dynamical systems we consider are partially driven by some exogeneous noises and the objective function may also include such noises. Hence controls are random variables. Classical approaches such as Dynamic Programming and Stochastic Programming, that we briefly recall below, encounter difficulties when the system becomes large. The aim of this paper is to present a new heuristic to solve a class of such problems using price decomposition.

The problems we are studying are common in practice. For example, consider a physical system, say a set of numerous power units, that evolve depending on exogeneous noises (water inflows, failures) and on controls (production levels). At each time step, an observation on the system arises and a control has to be chosen on the basis of the available information, namely the past observations (non-anticipativity constraint). The objective is to minimize the sum of the units' production costs over a given discretized time horizon, while satisfying a global demand constraint at each time step. This decision process hence consists of finding optimal strategies, i.e. functions that map, at each time t, the available information to the optimal decision with respect to the production cost.

As far as we know, most methods that have been proposed to decompose largescale stochastic optimal control problems are based on Stochastic Programming (see [START_REF] Prékopa | Stochastic programming[END_REF][START_REF]Stochastic Programming[END_REF]). This approach consists in representing the non-anticipativity constraints using a so-called scenario tree. Once discretized on such a structure, the problem is not stochastic anymore and various deterministic decomposition techniques have been used to solve it (see [START_REF] Higle | Stochastic decomposition[END_REF]). In this context, there are two main issues that are not easy to deal with. The first is concerned with the "distance" between the original problem and its deterministic reformulation [START_REF] Artstein | Sensitivity to σ-fields of information in stochastic allocation[END_REF][START_REF] Heitsch | Stability of multistage stochastic programs[END_REF], or how to draw a scenario tree in such a way that the solution of the discretized problem is an accurate estimate of the original one. In order to obtain some given accuracy, [START_REF] Shapiro | On complexity of multistage stochastic programs[END_REF] shows that the growth of the number of leaves in the tree, hence the numerical complexity, has to be exponential with respect to the time horizon. The second issue is concerned with the way one can rebuild strategies from optimal commands obtained in the discretized problem [START_REF] Pennanen | Epi-convergent discretizations of multistage stochastic programs[END_REF].

On the other hand, when dealing with a Markov Decision Process, methods based on Dynamic Programming (DP) (see [START_REF] Bellman | Dynamic programming[END_REF][START_REF] Bertsekas | Dynamic programming and optimal control[END_REF]) do provide a way to obtain strategies as feedback functions with respect to so-called state variables. Unfortunately, the well-known curse of dimensionality prevents us from using this approach straightforward on large-scale problems, because the computational burden increases exponentionally with the state dimension. Numerous approximations have been proposed to tackle the difficulty. For instance, a popular idea in the field of hydro-power management, introduced by Turgeon in [START_REF] Turgeon | Optimal operation of multi-reservoir power systems with stochastic inflows[END_REF], consists of obtaining local strategies as a function of the local stock and the aggregated complementary stock. Another idea, namely Approximate Dynamic Programming (ADP), looks for the value functions (solutions of the DP equation) within a finitedimensional space (see [START_REF] Bellman | Functional approximations and dynamic programming[END_REF] or [BT96, §6.5]). To be practically efficient, such an approach requires some a priori information about the problem, in order to define a well suited functional subspace. Indeed, there is no systematic means to choose the basis functions and several choices have been proposed [START_REF] Tstsiklis | Feature-based methods for large scale dynamic programming[END_REF][START_REF] De Farias | The Linear Programming Approach to Approximate Dynamic Programming[END_REF].

When dealing with large-scale optimization problems, the decomposition/coordination approach aims at finding a solution to the original problem by iteratively solving several smaller-dimensional subproblems. In the deterministic case, several types of decomposition have been proposed (e.g. by prices or by quantities) and unified in a general framework using the Auxiliary Problem Principle in [START_REF] Cohen | Auxiliary Problem Principle and decomposition of optimization problems[END_REF]. In the open-loop stochastic case, i.e. when controls do not rely on any observation, [START_REF] Cohen | Decomposition Coordination Algorithms for Stochastic Optimization[END_REF] proposed to take advantage of both decomposition techniques and stochastic gradient algorithms. These techniques have been extended in the closed-loop stochastic case by [START_REF] Barty | A stochastic gradient type algorithm for closed loop problems[END_REF], but so far they fail to provide decomposed state dependent strategies in the Markovian case. This is because a subproblem's optimal strategy depends on the state of the whole system, not only on the local state. In other words, decomposition approaches are meant to decompose the control space, namely the range of the strategy, but the numerical complexity of the problems we consider here also arises because of the dimensionality of the state space, that is to say the domain of the strategy.

We here propose a way to use price decomposition within the closed-loop stochastic case. The coupling constraints, namely the constraints preventing the problem from being naturally decomposed, are dualized using a Lagrange multiplier (price). At each iteration, the price decomposition algorithm solves each subproblem using the current prices, then uses the solutions to update the prices. In the stochastic context, prices are a random process whose dynamics are not available, so the subproblems do not in general fall into the Markovian setting. However, on a specific instance of this problem, [START_REF] Strugarek | Approches variationnelles et autres contributions en optimisation stochastique[END_REF] has exhibited a dynamics for the optimal multipliers, and he has shown that these dynamics were independent of the decision variables. Hence it was possible to come down to the Markovian framework and to use DP to solve the subproblems in this case. Following this idea, we propose to choose a parameterized dynamics for these multipliers so that solving subproblems using DP becomes possible. The update is then performed using a sampling/regression technique.

This paper is organized as follows. In §2 we describe the general type of problems we are concerned with in this paper. Then, in §3, we recall the Dynamic Programming equation and highlight the difficulties induced when considering large-scale problems. In §4, we present the classical price decomposition approach in Hilbert spaces and the difficulties encountered when dealing with stochastic optimal control problems. Based on these ingredients, we present in §5 a heuristic allowing us to solve subproblems using DP. We finally validate this approach on a simplified power management problem in §6.

Mathematical framework

Throughout this paper the random variables, defined over a probability space (Ω, A, P), will be denoted using bold letters (e.g. W ∈ L 2 (Ω, A, P, W)) whereas their realizations will be denoted using normal letters (e.g. w ∈ W).

In this paper we consider a finite horizon stochastic optimal control problem, where T denotes the time horizon. Three types of random variables are involved in the problem, namely a state, a control, and a noise. The state X t ∈ L 2 (Ω, A, P, R n ) evolves with respect to dynamics depending on the control U t ∈ L 2 (Ω, A, P, R m ) and on some exogeneous noise ξ t ∈ L 2 (Ω, A, P, R p ). Unlike deterministic optimal control problems, in the stochastic case the time "direction" is of particular importance. In order to fulfill the causality principle, the control at a given time step t only depends on the observation of noises prior to t. Moreover, we assume that the observation available at time t consists of all past noises. In order to mathematically represent such an information structure, we denote by A t the σ-field generated at time t by past noises (ξ 1 , . . . , ξ t ), so that the control U t at time step t has to be measurable with respect to A t . These last constraints will be called the non-anticipativity constraints.

The global system consists of N units, whose dynamics and cost functions are mutually independent. More precisely, the state X t (respectively the control U t ) of the global system writes X 1 t , . . . ,

X N t with X i t ∈ L 2 (Ω, A, P, R ni ) (respectively U 1 t , . . . , U N t with U i t ∈ L 2 (Ω, A, P, R mi )) and n = N i=1 n i and m = N i=1 m i , so that the global dynamics X t+1 = f t X t , U t , ξ t+1 can be written independently unit by unit: X i t+1 = f i t X i t , U i t , ξ t+1 , i = 1, . . . , N .
In the same way, the global cost L t X t , U t , ξ t+1 is equal to the sum of the local unit costs L i t X i t , U i t , ξ t+1 , i = 1, . . . , N . At the end of the time period, each unit i leads a cost K i that only depends on the final state X i T of the unit. For now, the global problem can be stated independently unit by unit. The coupling between the units arises from a set of static R d -valued constraints, the constraint at time step t reading N i=1 g i t X i t , U i t = 0 (see remark 2 for extensions to more enhanced relations). We suppose that all functions f i t , L i t and g i t are at least Borel measurable.

The initial state X 0 is assumed to be known. Denoting (X 1 , . . . , X T ) by X and (U 0 , . . . , U T -1 ) by U , the problem we wish to solve is: min

X,U E T -1 t=0 N i=1 L i t X i t , U i t , ξ t+1 + N i=1 K i X i T (1a) s.t. X i t+1 = f i t X i t , U i t , ξ t+1 , ∀t = 0, . . . , T -1, ∀i = 1, . . . , N, (1b)
X i 0 = x i , ∀i = 1, . . . , N, (1c) N i=1 g i t X i t , U i t = 0, ∀t = 0, . . . , T -1, (1d) U t is A t -measurable, ∀t = 0, . . . , T -1, (1e) x t ≤ X t ≤ x t , ∀t = 1, . . . , T, (1f)
u t ≤ U t ≤ u t , ∀t = 0, . . . , T -1. (1g)
There are three types of coupling in Problem (1):

• The first one comes from the state dynamics (1b) that induce a temporal coupling, subsystem by subsystem. • The second one arises from the static constraints (1d) that link together all the subsystems at each time step t. • The third type of coupling comes from the non-anticipativity constraints (1e), which link together controls relying on the same noise history. If two realizations of the noise process are identical up to time t, then the same control has to be applied at time t on both realizations.

We ultimately suppose that noises ξ t are independent (white noise). We are thus in the Markovian case and it is well known that the optimal control, which is a priori a function of all the past noises, only depends on the current state [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF].

Remark 1 (White noise assumption). If the noises ξ t are not independent 1 but still have known dynamics, one can always include the necessary noise history in the state to come back to the Markovian case. Unfortunately, this usually leads to a higher state dimension, and hence a higher numerical complexity in the DP framework, as will be explained in §3.

Remark 2 (Coupling constraints involving noises). It is possible to replace the static coupling constraint

N i=1 g i t X i t , U i t = 0 by N i=1 g i t X i t , U i t = D t
, where D t is a random variable representing for instance a global demand. However, expressions are then harder to write: in the Markovian case, i.e. when the D t 's are independent one from another, D t is observed before choosing the control at time t, so optimal controls must depend on both the state X t and the noise D t .

Stochastic Dynamic Programming

In order to solve stochastic optimal control problems in the Markovian framework, Bellman proposed in [START_REF] Bellman | Dynamic programming[END_REF] the Dynamic Programming (DP) method. It consists of introducing value functions V t : R n → R that represent the expected optimal cost when starting from state x at time t. In the case of Problem (1), it reads:

(2)

V t (x) = min X,U E T -1 s=t N i=1 L i s X i s , U i s , ξ s+1 + N i=1 K i X i T X t = x ,
subject to the same constraints as in (1) and using the convention that if the optimization problem (2) is not feasible, then V t (x) = +∞. The value functions are usually computed in a recursive manner using the DP equation:

V T (x) = N i=1 K i x i , (3a)
and, for t = 1, . . . , T -1:

V t (x) = min u∈[u t ,ut] E N i=1 L i t x i , u i , ξ t+1 + V t+1 f t x, u, ξ t+1 , (3b) s.t. N i=1 g i t x i , u i = 0. (3c)
Unlike Stochastic Programming methods, a major advantage of DP is that it provides the control U t as a feedback function on the state variable X t :

U t = Φ t (X t ) .
Except on very simple examples, Equation (3) cannot be solved analytically, and many numerical methods have been proposed. A common practice is to discretize the state space and estimate the expectations using Monte Carlo sampling. Unfortunately, as was mentioned in §1, we are facing the curse of dimensionality: the complexity of DP grows exponentially with respect to the state space dimension.

Moreover, Equation (3) is not decomposable in the sense that it cannot be replaced by the solving of N DP equations depending only on the local state x i . Indeed, even if V T is a sum of functions depending on the local state x i as in (3a), this additive property does not hold for the preceeding time steps because of the coupling constraint (3c). Hence, looking for the value function as a sum of functions depending only on the local state would lead to suboptimal strategies. In other words, the local state of a subsystem is not sufficient to take the optimal local decision; some global information about the system is necessary.

Nonetheless, DP remains a seductive approach for small-scale problems since it provides a way to obtain feedback functions. Based on a decomposition scheme presented in §4, we will describe in §5 a heuristic approach in which Problem (1) is decomposed into small-scale subproblems that we solve using DP.

Price decomposition

Let us recall some results about the classical Uzawa algorithm [START_REF] Arrow | Studies in linear and nonlinear programming[END_REF], which aims at iteratively getting round the static coupling constraint (1d). When the cost function is additive, this algorithm is also referred to as the price decomposition approach (see [START_REF] Cohen | Auxiliary Problem Principle and decomposition of optimization problems[END_REF] for further details). Let us first introduce the Lagrangian of problem (1):

L (X, U , λ) = E T -1 t=0 N i=1 L i t X i t , U i t , ξ t+1 + λ ⊤ t g i t X i t , U i t + N i=1 K i X i T ,
with λ t ∈ L 2 Ω, A, P, R d the Lagrange multiplier associated to the coupling constraint (1d) and λ = (λ 0 , . . . , λ T -1 ). When the Lagrangian has a saddle point, we know from classical duality theory in optimization [START_REF] Ekeland | Convex analysis and variational problems[END_REF] that Problem (1) is equivalent to:

max λ min X,U L (X, U , λ) (4a) s.t. X i t+1 = f i t X i t , U i t , ξ t+1 , ∀t = 0, . . . , T -1, ∀i = 1, . . . , N, (4b)
U t is A t -measurable, ∀t = 0, . . . , T -1, (4c) x t ≤ X t ≤ x t , ∀t = 1, . . . , T, (4d)
u t ≤ U t ≤ u t , ∀t = 0, . . . , T -1. (4e)
Recall that the Lagrange multiplier λ t can be interpreted as the marginal price one should pay for satisfying the coupling constraint (1d). Because of the A tmeasurability of the variables involved in this constraint and of the properties of conditional expectation, it is easy to see that we can always choose λ t to be A tmeasurable.

Let us introduce the dual function ψ (λ) := min X,U L (X, U , λ) subject to constraints (4b), (4c), (4d) and (4e). The key point of the price decomposition algorithm is that computing ψ (λ) is much easier than solving the original Problem (1). Indeed, one can write:

ψ (λ) = min X,U E T -1 t=0 N i=1 L i t X i t , U i t , ξ t+1 + λ ⊤ t g i t X i t , U i t + N i=1 K i X i T , = N i=1 min X i ,U i E T -1 t=0 L i t X i t , U i t , ξ t+1 + λ ⊤ t g i t X i t , U i t + K i X i T ,
so that we replace the solving of an optimization problem with variables (X, U ) by the solving of N subproblems with variables X i , U i . Given λ k , an iteration of the price decomposition algorithm first solves the N subproblems:

min X i ,U i E T -1 t=0 L i t X i t , U i t , ξ t+1 + λ k t ⊤ g i t X i t , U i t + K i X i T (5a) s.t. X i t+1 = f i t X i t , U i t , ξ t+1 , ∀t = 0, . . . , T -1, (5b) U i t is A t -measurable, ∀t = 0, . . . , T -1, (5c) x i t ≤ X i t ≤ x i t , ∀t = 1, . . . , T, (5d)
u i t ≤ U i t ≤ u i t , ∀t = 0, . . . , T -1. (5e)
The Lagrange multiplier λ k is then updated using a gradient-like algorithm. Under standard assumptions2 , the gradient of ψ is:

∇ λ t ψ λ k = N i=1 g i t X i,k+1 t , U i,k+1 t ,
where X i,k+1 t and U i,k+1 t are the solutions of Problem (5). At first sight, Problem (5) looks like a stochastic optimal control problem with control U i t and state X i t , the solution of which would be a local feedback on X i t . This contradicts the fact that the solution of Problem (1) is a feedback function on the whole state X 1 t , . . . , X N t . In order to understand where this contradiction comes from, one has to highlight the role of λ in Problem (5).

Dual Approximate Dynamic Programming

Let us take a closer look at Problem (5). First suppose that λ is a white noise process. Then Problem (5) lies in the Markovian framework with state X i t and noise (ξ t , λ t ). The optimal control U i t depends only on the local state X i t and one can apply stochastic dynamic programming to solve this small-scale optimal control problem. Unfortunately, we do not know anything about the time correlations of the price process λ. . .

Let us now consider the general case. Defining X i t , λ 1 , . . . , λ t as the state at time t, Problem (5) falls in the Markovian setting. In particular, the optimal control U i t is X i t , λ 1 , . . . , λ t -measurable. However DP in this context proves numerically intractable because the state dimension increases with respect to time.

Consider now an intermediate case, and suppose that the dual variable λ has a short memory dynamics, for instance that λ t+1 only depends on λ t and ξ t+1 :

(6) λ t+1 = h t λ t , ξ t+1 .
Using X i t , λ t as the state variable at time t, Problem (5) falls in the Markovian setting. The state dimension does not increase with respect to time anymore and is hopefully small so that Problem (5) can be solved using DP.

In a very specific instance of Problem (1), namely:

(7) min X,U E T -1 t=0 N i=1 c i 2 U i t 2 + N i=1 γ i 2 X i T -X i 0 2 s.t. X i t+1 = X i t -U i t + A i t+1 , ∀t = 0, . . . , T -1, n i=1 U i t = D t , ∀t = 0, . . . , T -1, U t is A t -measurable, ∀t = 0, . . . , T -1, with ξ t = D t , A 1 t , . . . , A N t , [ Str06
] has brought to light such an intermediate case. Here the dimension of the state X i t (respectively of the control U i t ) in the subsystem i is n i = 1 (respectively m i = 1), for i = 1, . . . , N . The result is the following.

Proposition 1. If D t , A 1 t , . . . , A N t t=0,...,T is a white noise process and if there exists α ∈ R + such that γ i = αc i , ∀i = 1, . . . , N , then the optimal Lagrange multipliers satisfy:

λ t+1 = λ t + 1 N i=1 1 ci D t+1 (1 + α) -D t -αE (D t+1 ) -α (A t+1 -E (A t+1 )) , λ 0 = 1 N i=1 1 ci D 0 (1 -α) -α T s=1 E (A s ) -α T -1 s=1 E (D s ) .
Using such a dynamics for the multipliers, it is straightforward to show that Problem (7) splits into N independent optimization subproblems. Taking the state variable as X i t , λ t , D t , the i-th subproblem can be solved using DP in dimension 3. In summary, we have replaced one N -dimensional problem by N 3-dimensional problems.

Note that the proportionality assumption on the cost coefficients in proposition 1 is rather unnatural. Nevertheless, it shows that, in some cases, there exist dynamics for the Lagrange multipliers that is independent of the decision variables.

To deal with more general cases, we propose to approximate the dual process λ by some parameterized short-memory process. That is, we try to identify the multipliers that are the closest to the optimal ones within a constrained subspace of stochastic processes. This approach is similar to that employed in the Approximate Dynamic Programming (ADP) method. Since it concerns dual variables rather than DP value functions, we refer to this approach as Dual Approximate Dynamic Programming.

The performance of such an approach highly depends on the choice of the subspace of stochastic processes in which we force the multipliers to lie. However, a major difference with ADP techniques is that approximating the dual variables may lead to violations of the coupling constraints. The larger the chosen subspace, the less the coupling constraints will be violated. Moreover, prior information on the problem may be useful to devise a suitable dynamics.

Let us now present the implementation of DADP. We constrain dual variables to satisfy:

(8) λ t+1 = h αt λ t , ξ t+1 ,
where h αt is an a priori chosen function parameterized by α t ∈ R q . We denote by S the set of all random processes that verify Equation (8) for some real vector α = (α 1 , . . . , α T -1 ). Given a vector α k of coefficients, the first step of DADP is to solve the N subproblems (5) using DP with state X i t , λ t . In order to update the Lagrange multipliers, we draw s trajectory samples of the noise ξ and integrate the dynamics (5b) and (8) using the optimal feedback laws, thus obtaining s trajectory samples of X k , U k and λ k . We then perform a gradient step on λ sample by sample:

λ k+ 1 2 ,σ t = λ k,σ t + ρ t N i=1 g i t X i,k,σ t , U i,k,σ t , ∀σ = 1, . . . , s,
with ρ t being well-chosen real values. Finally, we apply a regression operator R s on the samples λ k+ 1 2 in order to obtain a stochastic process λ k+1 lying in S:

R s λ k+ 1 2 = arg min α0,...,αT -1 T -1 t=0 s σ=1 µ σ t -λ k+ 1 2 ,σ t 2 R d s.t. µ σ t+1 = h αt µ σ t , ξ σ t+1 .
This heuristic is outlined in algorithm 1.

Algorithm 1 Dual Approximate Dynamic Programming

Require: ε > 0, γ > 0, a shape h α for the prices dynamics, α 0 . repeat k ← k + 1 for i = 1 to N do Solve i-th subproblem by DP using parameters α k for the price dynamics, and obtain X i,k and U i,k . Both implicitly depend on α k . end for Update paramaters α k :

α k+1 = R s   λ k t + ρ t N i=1 g i t X i,k t , U i,k t t=0,...,T -1   ,
where:

λ k t+1 = h α k t λ k t , ξ t+1 , ∀t = 0, . . . , T -1. until λ k+1 -λ k < ε
Remark 3 (Convexity of S). The regression operator R s is meant to be a samplebased approximation of the projection operator R on S. Since the latter set can be non-convex, R λ k+ 1 2 is not necessarily unique: this may lead to numerical instabilities.

Remark 4 (Enhancement of S). It may be desirable to consider a larger set S in order to estimate more accurately the price process. For instance, one can extend relation (8) in order to include more memory in the process:

λ t+1 = h αt (λ τ ) τ ≤t , (ξ τ ) τ ≤t+1 ,
However, this will in general increase the numerical complexity of DP in the solving of the subproblems.

Remark 5 (Another formulation). Alternatively, we could have considered a gradient algorithm that iterates directly on the parameters α of the dynamics (8). In this case, since we have no restrictions on α, the feasible set would have been convex. Unfortunately, because the dynamics (8) may be nonlinear with respect to α, the dual function ψ introduced in §4 might be non-concave with respect to α.

Numerical experiments

We tested this approach on a simple power management problem. On this smallscale example, we will be able to compare DADP results to those obtained by DP. Consider a power producer who owns two types of power plants:

• Two hydraulic plants that are characterized at each time step t by their water stock X i t and power production U i t , and receive water inflows ξ i t+1 , i = 1, 2. These two units are subject to dynamic constraints but are costfree;

• One thermal unit with a production cost that is quadratic with respect to its production U 3 t . There are no dynamics associated with this unit.

Using these plants, the power producer must supply a power demand D t at each time step t, over a discrete time horizon of T = 25 time steps. All noises, i.e. the demand D t and the inflows ξ 1 t and ξ 2 t are chosen to be white noise processes. In the model we moreover impose small quadratic costs on the hydraulic power productions in order to ensure that, at least in the deterministic framework and without our approximation, the algorithm would build primal iterates that converge to the optimal solution of the original problem (see [START_REF] Ekeland | Convex analysis and variational problems[END_REF]). The problem reads3 : min

X,U E T -1 t=0 ǫ U 1 t 2 + ǫ U 2 t 2 + L t U 3 t + K 1 X 1 T + K 2 X 2 T (9a) s.t. X i t+1 = X i t -U i t + ξ i t+1 , ∀i = 1, 2, ∀t = 0, . . . , T -1, (9b) U 1 t + U 2 t + U 3 t = D t , ∀t = 0, . . . , T -1, (9c) x i ≤ X i t ≤ x i , ∀i = 1, 2, ∀t = 1, . . . , T, (9d) 0 ≤ U i t ≤ u i , ∀i = 1, 2, ∀t = 0, . . . , T -1, (9e) 0 ≤ U 3 t , ∀t = 0, . . . , T -1, (9f) U i t is σ D 0 , ξ 1 0 , ξ 2 0 , . . . , D t , ξ 1 t , ξ 2 t -measurable, ∀i = 1, 2, 3. (9g)
In this problem, the state X t is two-dimensional, hence DP remains numerically tractable and we can use the DP solution as a reference. In order to use DADP, we choose an auto-regressive process for the Lagrange multipliers:

λ t+1 = α t λ t + β t D t+1 + γ t , (10a)
λ 0 = β 0 D 0 + γ 0 . (10b)
We then perform the algorithm and depict its convergence in Figure 2. We first draw the values of the dual function ψ introduced in §4 along with iterations (lower curve) and observe that it converges to the optimal value of the original problem computed by DP. Note that each value of ψ is computed by Monte Carlo simulation over 10 3 scenarios. We also draw the cost of the problem with all constraints satisfied (primal cost) at each iteration (upper curve). As explained in §5, DADP does not ensure that the coupling constraint (9c) is satisfied. To circumvent this difficulty, the thermal unit strategy is chosen in the simulation so as to ensure feasibility of the coupling constraint, i.e.:

(11)

U 3 t = D t -U 1 t + U 2 t .
That is, DADP returns three strategies, for each of the hydraulic units and for the thermal unit. However, we use relation (11) for the thermal strategy during simulations in order to ensure demand satisfaction.

Figure 2 shows that the algorithm behaves well, in the sense that the value of the objective function converges quite quickly to a neighbourhood of the optimal value. However, even after 100 iterations the curve is still a bit noisy. This is because the price dynamics employed generates a non-convex-set of stochastic processes. Consequently, the least squares problem solved at each iteration is non-linear, and hence small variations in the actual gradient can result in large changes in the calculated gradient.

The key to convergence in DADP is to obtain a dynamics for the Lagrange multipliers that accurately matches the optimal one. We have represented in Figure 3 iterations, and those derived from DP. We observe that the approximate price dynamics issued from DADP satisfactorily converges to the optimal one. This indicates that:

(1) the dual process converged, although the set of stochastic processes defined by ( 10) is non-convex, (2) there is no need to enhance the chosen dynamics (10) for the multipliers in this particular problem. Note that the optimal prices derived from DP are obtained by numerically differentating the Bellman functions, hence the numerical instabilities we observe in the lower parts of the DP prices curves.

Remark 6 (Numerical complexity). We chose to validate the method on a twodimensional power management problem, so we could compute a reference solution using DP. Note that there would be no additional difficulty in implementing the same algorithm with a larger number of hydraulic units, i.e. with a largerdimensional state. The complexity of DADP grows linearly with the number of subsystems. The most time consuming part of the algorithm is solving the subproblems. However, this calculations can be easily parallelized on a computer, so that the time needed at each DADP iteration remains constant with respect to the number of subsystems.

Conclusion

In this paper we present an approach, called Dual Approximate Dynamic Programming (DADP), to solve large-scale stochastic optimal control problems in a price decomposition framework, without discretizing randomness. This method employs classical duality theory results to solve decomposable large-scale systems, as it usually is in the deterministic framework. In order to be able to solve subproblems using DP, we suppose that the Lagrange multipliers obey some parameterized dynamics. The DADP algorithm then iterates on the parameters of these dynamics. What is original in this approach is the use of a dual variable in the optimal local feedback functions as an auxiliary variable that sums up the remaining part of the system.

On an example, we show that this approach is very attractive from a numerical point of view. Using rather simple dynamics for the multipliers, we obtained surprisingly good results with a small number of iterations. The main advantage of the method is that the complexity of the algorithm grows linearly with respect to the number of subsystems so that the curse of dimensionality is circumvented for the considered class of problems.

There are still several important theoretical questions. Since we constrain the dual variables to lie in some a priori chosen subset, we cannot state that the coupling constraints will be satisfied. Hence it would be useful to be able to evaluate the distance between the solution given by the heuristic and the feasible set; this would also give clues on how to choose well-suited dynamics for the dual variables on particular problems. Furthermore, the stochastic process subset on which we constrain the dual variables is possibly non-convex. In this context, it might be valuable to use more enhanced numerical methods for the update of the Lagrange multipliers. Further studies will be concerned with these issues.

Figure 1 .

 1 Figure 1. Mean of D t , ξ 1 t and ξ 2 t over time (in red is one sample trajectory).

Figure 2 .

 2 Figure 2. Value of the dual function (blue), of the primal function (red) and optimum (black) along with iterations.

Figure 3 .

 3 Figure 3. Comparison, using 100 samples, of the approximate prices trajectories (red) with the optimal ones (black), after 10, 20, 50, and 90 iterations of the algorithm (from left to right and top to bottom).

See[START_REF] Danskin | The theory of max-min[END_REF] for results on the differentiability of the dual fonction ψ.

In this example, we consider two hydraulic plants with characteristics:x 1 = 0, x 1 = 50, u 1 = 6, K 1 (x) = -7x, x 2 = 0, x 2 =

40, u 2 = 6, K 2 (x) = -12x, ǫ = 0.1 where y (resp. y) denotes a lower (resp. upper) bound for variable y. Moreover, producing u with the thermal plant costs Lt (u) = u + u 2 .


Alfredo Gonzalez-Perez
email: alfredo.gonzalez@campusroslagen.se

UV-LED water disinfection for small-scale decentralized systems

Keywords: UV-LED, water disinfection, flashing modes, UV mercury lamps, regulation

We summarize here the recent advances in UV-LED technology with focus on their use for drinking water disinfection on small scale drinking water production plants and with a main target on decentralized systems as well as point-of-use applications. The state of the art on the UV-LED technology and the challenges for their use for drinking water production are highlighted together with regulation and standardization issues. Technological/operational differences compared with the existing UV technology on mercury-based UV lamps are also shown. The possibility to use flashing modes and combinations of different UV wavelengths to enhance disinfection are two of the most advantageous options available for devices using LED technology for disinfection. The UV-LED disinfection units are already implemented into small and medium-sized water treatment units characteristic of water decentralized systems.

INTRODUCTION

Ultraviolet treatment is a safer approach for drinking water disinfection, however the dominant technology today for delivering UV is based on the use of low-or highpressure mercury lamps. These lamps require high operating voltages, continuous operation, and pose a hazard for people and the environment. UV-LEDs are projected to replace the old mercury-based lamps with the added value of low power consumption, no pre-heating needed, and the possibility to operate in pulsed mode, as well as the combination of UV wavelengths. This transition will happen, and it is now the responsibility of researchers, technologists, entrepreneurs, and water purification plant operators to make a quick and efficient implementation towards a mercury-free UV disinfection technology. This will contribute to securing long term resilience, stability, sustainability, and security of potable drinking water in society. The transition towards water decentralized systems will open new possibilities for the implementation of pure UV-LED water disinfection units.

RESULTS AND DISCUSSION

Recent reviews by Lui et al. [START_REF] Lui | Point-of-use water disinfection using ultraviolet and visible light-emitting diodes[END_REF] and [START_REF] Song | Application of ultraviolet light-emitting diodes (UV-LEDs) for water disinfection: A review[END_REF] summarized the current understanding, recent advances, and current problems of the application of UV-LEDs for water disinfection focusing on point-of-use applications, and recent studies on the inactivation efficiency of different wavelengths respectively. It is however clear that there are several key challenges that need to be addressed for a successful implementation of UV-LED for water disinfection purposes. UV mercury lamps and UV-LEDs operate in substantially different manner. There is an urgent need to establish standardized protocols for studying UV-LED inactivation of microorganisms. The inactivation credit of UV radiation for viruses, bacteria and protozoan oocysts in water was recently reviewed by [START_REF] Hijnen | Inactivation credit of UV radiation for viruses, bacteria and protozoan (oo)cysts in water: a review[END_REF]. They summarized the efforts for a quantitative microbial risk assessment by relating the inactivation kinetics of microorganisms with the applied UV fluence. A better understanding of the microorganisms' response to UV-LEDs goes alongside in the list of needs to be addressed. The application of multiple wavelengths (other than the characteristic for the absorption of DNA at 260 nm) on the whole UV spectra to improve the inactivation efficiency, as well as the use of pulsating operation modes of the LEDs, are two main research directions that are critical in the development of new UV-LED reactors for point-of-use and small-scale applications in drinking water purification plants. In this work we will summarise the recent advances and key R&D directions for a successful implementation of UV-LED disinfection for small-scale decentralized water systems.

The specific UV-LED technology to implement is also an important factor in formulating a complete strategy for small to medium scale water disinfection. Unlike the development we have seen with visible LEDs, in particular the GaN-based blue LED reaching efficiencies upwards of 80%, the AlGaN-based UV-LED is still struggling to achieve the desired efficiency. The reason for this is well known; the AlGaN material used suffers from high amounts of crystal dislocations that degrade the optical and electrical properties of the material. There is currently an intense worldwide effort focused on developing UV LEDs with better wavelength tunability and more competitive wall plug efficiency. The option to use multiple wavelengths that is characteristic from UV-LED disinfection is one of the several advantages that will came from the implementation of this kind of technology. At the same time these new options will pose big challenges for the regulation that is not adapted to LEDbased technology. On table 1.1 we show a selection of multiple wavelengths combinations (UV-C, UV-B and UV-A) targeting different microorganisms on different mediums. Looking at the current state-of-the-art we can see that the technology is ready for small scale drinking water production plants, but an obvious lack of the right regulatory framework is present. There is also a room of opportunity for the use of different UV wavelengths in combination as well as flashing modes adding functionality for disinfection purposes. Regulations and standards to measure performance are focus on the pre-existing technology while the new UV-LED technology require a new regulation that considers differences in design of the reactor, operation modes and energy source, etc. This regulation should come to place in the following years through a more active cooperation and dialogue between the technologists and regulators. The results of our survey show that developing new devices with UV-LED technology should result in increased efficiency and help to embrace the objectives of the MINAMATA convention on mercury allowing for drinking water UV disinfection without the use of mercury-based UV lamps. This UV-LED systems are already optimal for small and medium-scale decentralized water purification systems.

Table 1 . 1 .

 11 Disinfection studies under combinations of different UV wavelengths targeting several microorganisms.

	Author			Microorganism		Media	UVC	UVB	UVC/
									UVA	UVA	UVB-
										UVC
	(A.		C.	E. coli and CIP 6224,	buffered	Yes Yes N/A
	Chevremont	et	Enterococcus faecalis		solutions
	al., 2012)
	(Oguma et al.,	E. coli			PBS	No	No	No
	2013)
	(Nakahashi et al.,	Vibrio parahaemolyticus	PBS	Yes N/A N/A
	2014)
	(Beck	et	al.,	E.	coli	K12,	MS2	PBS	N/A N/A No
	2017)			coliphage,	Human
				Adenovirus	type	2,
				Bacillus pumilus spores
	(Green et al.,	E. coli, L. innocua, L.	saline	No	N/A Yes
	2018)			monocytogenes and L.	solution
				seeligeri, 5 pathogenic
				salmonella strains
	(Hull and Linden,	MS2 bacteriophages		PBS	N/A N/A N/A
	2018)
	(Li et al., 2017)	E. coli			saline	N/A N/A No
								solution
	(Nyangaresi et al.,	E. coli			sterilized	No	N/A No
	2018)							saline
								solution

Acknowledgement. The author wants to acknowledge the Water Center for Innovation (Campus Roslagen AB) at Norrtälje Municipality for support and discussions on water decentralization and regulation.