Stochastic optimization of a hydroelectric reservoir using piecewise polynomial approximations

INFOR, Feb 2003 by Lamond, Bernard F

Recd. Oct. 2001, Rev. Oct. 2002, Acc. Feb. 2003

ABSTRACT

We propose a method for optimizing a single hydro-electric reservoir using a piecewise polynomial approximation of the future value functions. Unlike previous methods based on splines, we avoid discretizing the inflow distribution. Instead, we carry out the expectation step of dynamic programming using an exact, easy-to-evaluate formula for the integral of a piecewise polynomial function. We then apply our method to solving a model which assumes a piecewise linear reward function of the energy produced, and takes into account the turbine head effects.

Keywords: Markov decision processes, stochastic dynamic programming, piecewise polynomial approximation, optimal reservoir management, energy planning.

RESUME

Nous proposons une methode pour optimiser un reservoir hydro-electrique unique en utilisant une approximation polynomiale par morceau des fonctions de valeur future. Contrairement aux methodes precedentes basees sur les splines, nous evitons la discretisation de la distribution des apports. A la place, nous effectuons l'elape du calcul de l'esperance en programmation dynamique en utilisant une formule exacte et facile a evaluer pour l'integrale de la fonction polynomiale par morceau. Nous appliquons ensuite notre methode a la resolution d'un modele qui assume une fonction de recompense lineaire par morceau de l'energic produite, et tenant compte de l'effet de hauteur de chute des turbines.

Mots-cles : Processus de decision markoviens, programmation dynamique stochastique, approximation polynomiale par morceau, gestion optimale des reservoirs, planification energetique.

1. INTRODUCTION

We consider a discrete time, finite horizon, stochastic optimization model for a hydro-electric system with a single reservoir. We assume the rewards from electricity production are given by a concave, piecewise linear function of the energy produced. The energy produced may depend on the storage as well as the discharge, thus allowing turbine head effects to be taken into account. See Lamond and Boukhtouta (1996), Lamond and Boukhtouta (2001) and the references therein for surveys of models and methods for stochastic reservoir optimization.

As in the usual stochastic dynamic programming (DP) approach (see, e.g., Puterman (1994)), we define the following random variables for t = 1,..., T

S^sub t^ = state at beginning of period t

A^sub t^ = action taken in period t

R^sub t^ = immediate reward received in period t.

Let also S^sub T+1^ be the terminal state. Realizations of the state and action variables are denoted s^sub t^, and a^sub t^, respectively, with state space S and conditional action set A^sub t^(s^sub t^) when S^sub t^ = s^sub t^ [is an element of] S We define the immediate reward functions

A simple solution method is to discretize the state and action variables s^sub t^ and a^sub t^, and to assume discrete transition probabilities, so that equations (1, 2) can be solved using discrete dynamic programming. A very fine discretization is usually required in order to obtain a satisfactory accuracy, however, resulting in a large amount of computation (Kitanidis and Foufoula-Georgiou (1987)). This approach is, in fact, impractical for solving multidimensional models of systems with many reservoirs. Nonetheless, some authors have proposed aggregation methods for multireservoir systems that solve a sequence of problems with two reservoirs (Turgeon (1980), Turgeon (1981)) or three reservoirs (Archibald et al. (1997)). In this context, the small models ought to be solved quickly yet accurately, because they have to be solved repetitively. Here, we propose an approach for solving a one dimensional problem which is faster and more accurate than discrete DP.

One such approach is to use continuous state and action variables and to approximate the functions V^sub t^(s^sub t^) using, for example, polynomial or piecewise polynomial functions (Chen et al. (1999), Foufoula-Georgiou and Kitanidis (1988), Johnson et al. (1993), Philbrick and Kitanidis (2001)). When the function is suitably smooth, spline approximations are used to preserve continuity of the first derivative at the grid points. Then eq. (1) is solved by a continuous, nonlinear programming method, and the expectation in eq. (2) is evaluated using a Gaussian quadrature rule for numerical integration, which corresponds to a coarse discretization of the distribution of the random variables (for example, expectations are computed using only two or three quadrature points in Chen et al. (1999), Foufoula-Georgiou and Kitanidis (1988), Johnson et al. (1993), and Philbrick and Kitanidis (2001)).

Here we also use continuous state and action variables and a piecewise polynomial approximation for V^sub t^(s^sub t^). However, due to the piecewise linear revenues, our function V^sub t^(s^sub t^) is not as smooth as in Chen et al. (1999), Foufoula-Georgiou and Kitanidis (1988), Johnson et al. (1993), and Philbrick and Kitanidis (2001), hence their (coarse) Gaussian quadrature scheme is not suitable for computing the expectation in our case. Therefore, we derive an exact formula for efficiently evaluating the expectation function W^sub t+1^(s^sub t^,a^sub t^) of eq. (2) using a continuous distribution instead of a coarse discretization. Our approach extends the work of Drouin et al. (1996) and Lamond and Lang (1996), where a method for efficiently computing the expectation of a piecewise linear function is given for a discrete distribution over a fine grid. Here, we extend this result in two ways: we allow (i) piecewise polynomial functions of higher degree and (ii) continuous distributions.