Generalized Decision Rule Approximations for Stochastic Programming via Liftings

Angelos Georghiou, Wolfram Wiesemann and Daniel Kuhn

No 43, Working Papers from COMISEF

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 higherdimensional 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.

Pages: 36 pages
Date: 2010-08-24
New Economics Papers: this item is included in nep-ore
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://comisef.eu/files/wps043.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to comisef.eu:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:com:wpaper:043

Access Statistics for this paper

More papers in Working Papers from COMISEF
Bibliographic data for series maintained by Anil Khuman ().