Optimization Online


Generalized Decision Rule Approximations for Stochastic Programming via Liftings

Angelos Georghiou (angelosg***at***control.ee.ethz.ch)
Wolfram Wiesemann (wwiesema***at***imperial.ac.uk)
Daniel Kuhn (daniel.kuhn***at***epfl.ch)

Abstract: Stochastic programming provides a versatile framework for decision-making under uncertainty, but the resulting optimization problems can be computationally demanding. It has recently been shown that, primal and dual linear decision rule approximations can yield tractable upper and lower bounds on the optimal value of a stochastic program. Unfortunately, linear decision rules often provide crude approximations that result in loose bounds. To address this problem, we propose a lifting technique that maps a given stochastic program to an equivalent problem on a higher-dimensional probability space. We prove that solving the lifted problem in primal and dual linear decision rules provides tighter bounds than those obtained from applying linear decision rules to the original problem. We also show that there is a one-to-one correspondence between linear decision rules in the lifted problem and families of non-linear decision rules in the original problem. Finally, we identify structured liftings that give rise to highly flexible piecewise linear decision rules and assess their performance in the context of a stylized investment planning problem.

Keywords: Decision Rule Approximations, Stochastic Programming, Robust Optimization, Error Bounds

Category 1: Robust Optimization

Citation: Working paper, Department of Computing, Imperial College London, August 2010

Download: [PDF]

Entry Submitted: 08/09/2010
Entry Accepted: 08/09/2010
Entry Last Modified: 05/12/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society