Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Scenario free approximations to stochastic programming via decision rules

The standard approach to solve a multistage stochastic program is to approximate the stochastic process of the underlying random parameters by a scenario tree. This method suffers from the curse of dimensionality since scenario trees are known to grow exponentially with the number of decision stages. Instead of discretizing the stochastic process, one can alternatively approximate the recourse decisions by a linearly parameterized family of decision rules. This complementary approach is computationally attractive since the resulting approximate problems often scale polynomially with the number of decision stages. While this decision rule approximation provides a feasible solution and a conservative estimate of the true optimal value of the stochastic program, it can incur a substantial loss of optimality. In this talk we show that applying the decision rule approximation to the original as well as a dual version of the stochastic program yields upper and lower bounds on the true optimal value. The gap between the bounds estimates the approximation error. We also show that linear decision rules, which approximate the recourse decisions by linear functions of the random parameters, can solve an inventory problem from the literature with up to 80 stages at about 5% accuracy. However, linear decision rules can perform poorly if the true optimal recourse decisions are highly non-linear, as is often the case for stochastic programs with many random parameters per stage. In this case, we improve the approximation quality by using lifting techniques to optimize efficiently over a class of piecewise linear continuous decision rules.
Type of Seminar:
Optimization and Applications Seminar
Dr. Daniel Kuhn
Department of Computing, Imperial College London
Oct 25, 2010   16:30-18:00

ETHZ Rämistrasse 101, HG G 19.1
Contact Person:

Prof. John Lygeros
File Download:

Request a copy of this publication.
Biographical Sketch:
Daniel Kuhn is a lecturer in the Department of Computing at Imperial College London. Before taking up his lectureship, he held post-doctoral research fellowships at Imperial College and at Stanford University and was head of the derivatives research unit at the Institute for Operations Research and Computational Finance at the University of St. Gallen. He holds a diploma in Theoretical Physics from ETH Zurich and a PhD in Operations Research from University of St. Gallen. His current research interests are focused on the development of efficient computational methods for the solution of stochastic and robust optimization problems and the design of approximation schemes which ensure their computational tractability. This theoretical work is primarily application-driven, the main application areas being energy systems, finance and engineering.