Refine
Language
- English (12)
Keywords
- Stochastic programming (3)
- Lr-distance (2)
- filtration (2)
- multistage (2)
- scenario reduction (2)
- scenario tree (2)
- stability (2)
- two-stage (2)
- ANOVA decomposition (1)
- Quasi-Monte Carlo (1)
Project
- C7 (6)
Application Area
- C (6)
An important issue for solving multistage stochastic programs consists in the approximate representation of the (multivariate) stochastic input process in the form of a scenario tree. In this paper, forward and backward approaches are developed for generating scenario trees out of an initial fan of individual scenarios. Both approaches are motivated by the recent stability result in [15] for optimal values of multistage stochastic programs. They are based on upper bounds for the two relevant ingredients of the stability estimate, namely, the probabilistic and the filtration distance, respectively. These bounds allow to control the process of recursive scenario reduction [13] and branching. Numerical experience is reported for constructing multivariate scenario trees in electricity portfolio management.
Modern electricity portfolio and risk management models represent multistage stochastic programs. The input of such programs consists in a finite set of scenarios having the form of a scenario tree. They model the probabilistic information on random data (electrical load, stream flows to hydro units, market prices of fuel and electricity). Since the corresponding deterministic equivalents of multistage stochastic programs are mostly large scale, one has to find significant tree-structured scenarios. Our approach to generate multivariate scenario trees is based on recursive deletion and bundling of scenarios out of some given (possibly large) scenario set originating from historical or simulated data. The procedure makes use of certain Monge-Kantorovich transportation distances for multivariate probability distributions. We report on computational results for generating load-inflow scenario
trees based on realistic data of EDF Electricité de France.
We extend earlier work on scenario reduction by relying directly on Fortet-Mourier metrics instead of using upper bounds given in terms of mass transportation problems. The importance of Fortet-Mourier metrics for quantitative stability of two-stage models is reviewed and some numerical results are also provided.
By extending the stability analysis of [17] for multistage stochastic programs we show that their solution sets behave stable with respect to the sum of an Lr-distance and a filtration distance. Based on such stability results we suggest a scenario tree generation method for the (multivariate) stochastic input process. It starts with a fan of individual scenarios and consists of a recursive deletion and branching procedure which is controlled by bounding the approximation error. Some numerical experience for generating scenario trees in electricity portfolio management is reported.
Stochastic Optimization of Electricity Portfolios: Scenario Tree Modeling and Risk Management
(2008)
We present recent developments in the field of stochastic programming with regard to application in power management. In particular we discuss issues of scenario tree modeling, i.e., appropriate discrete approximations of the underlying stochastic parameters. Moreover, we suggest risk avoidance strategies via the incorporation of
so-called polyhedral risk functionals into stochastic programs. This approach, motivated through tractability of the resulting problems, is a constructive framework providing particular flexibility with respect to the dynamic aspects of risk.
Quasi-Monte Carlo algorithms are studied for designing discrete approximations of two-stage linear stochastic programs. Their integrands are piecewise linear, but neither smooth nor of bounded variation in the sense of Hardy and Krause. We show that under some weak geometric condition on the two-stage model all terms of their
ANOVA decomposition, except the one of highest order, are smooth and, hence, certain Quasi-Monte Carlo algorithms may achieve the optimal rate of convergence $O(n^{-1+\delta})$ with $\delta\in(0,\frac{1}{2})$ and a constant not depending on the dimension if the integrands belong to weighted tensor product Sobolev spaces with properly selected weights. The geometric condition is generically (i.e., almost everywhere) satisfied if the underlying distribution is normal. We also discuss sensitivity
indices and efficient dimensions of two-stage integrands, and suggest a dimension reduction heuristic for such integrands.
Portfolio and risk management problems of power
utilities may be modeled by multistage stochastic programs. These
models use a set of scenarios and corresponding probabilities
to model the multivariate random data process (electrical load,
stream flows to hydro units, and fuel and electricity prices). For
most practical problems the optimization problem that contains
all possible scenarios is too large. Due to computational complexity
and to time limitations this program is often approximated by
a model involving a (much) smaller number of scenarios. The proposed
reduction algorithms determine a subset of the initial scenario
set and assign new probabilities to the preserved scenarios.
The scenario tree construction algorithms successively reduce the
number of nodes of a fan of individual scenarios by modifying the
tree structure and by bundling similar scenarios. Numerical experience
is reported for constructing scenario trees for the load
and spot market prices entering a stochastic portfolio management
model of a German utility
Mathematical models for the electricity portfolio
management of a utility that owns a hydro-thermal generation system
and trades on the power market often lead to complex stochastic
optimization problems. We present a new approach to solving
stochastic hydro-storage subproblems that occur when stochastic
Lagrangian relaxation is applied to solving such models. The special
structure of such hydro-storage subproblems allows the design
of a stochastic network flow algorithm. The algorithm represents
a stochastic extension of a relaxation method, that algorithmically
solves the linear minimum cost flow problem. It is based on the
iterative improvement of dual costs. Numerical experience of the
new algorithm is reported and its performance is compared with
that of standard LP software .
Quantitative stability of linear multistage stochastic programs is studied. It
is shown that the infima of such programs behave (locally) Lipschitz continuous
with respect to the sum of an Lr-distance and of a distance measure for the filtrations
of the original and approximate stochastic (input) processes. Various issues
of the result are discussed and an illustrative example is given. Consequences for
the reduction of scenario trees are also discussed.