Refine
Year of publication
- 2012 (3) (remove)
Language
- English (3)
Keywords
- stochastic programming (3) (remove)
Project
- C7 (3)
Application Area
- C (3)
We consider risk-averse formulations of multistage stochastic linear programs. For these formulations, based on convex combinations of spectral risk measures, risk-averse dynamic programming equations can be written. As a result, the Stochastic Dual Dynamic Programming
(SDDP) algorithm can be used to obtain approximations of
the corresponding risk-averse recourse functions. This allows us to define a risk-averse nonanticipative feasible policy for thestochastic linear program. Formulas for the cuts that approximate the recourse functions are given.
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.
Piecewise linear convex functions arise as integrands in stochastic programs. They are Lipschitz continuous on their domain, but do not belong to tensor product Sobolev spaces. Motivated by applying Quasi-Monte Carlo methods we show that all terms of their ANOVA decomposition, except the one of highest order, are smooth if the underlying densities are smooth and certain geometric condition is satisfied. The latter condition is generically satisfied in the normal case.