Primal and dual linear decision rules in stochastic and robust optimization |
| |
Authors: | Daniel Kuhn Wolfram Wiesemann Angelos Georghiou |
| |
Institution: | (3) Dept. Indust. Econ. and Techn. Management Gløshaugen Norwegian Univ. Sci. and Techn., N-7491, Trondheim, Norway;(4) Management Sci. Program The Univ. of Tennessee, Knoxville, TN 37919, USA |
| |
Abstract: | Linear stochastic programming provides a flexible toolbox for analyzing real-life decision situations, but it can become computationally
cumbersome when recourse decisions are involved. The latter are usually modeled as decision rules, i.e., functions of the
uncertain problem data. It has recently been argued that stochastic programs can quite generally be made tractable by restricting
the space of decision rules to those that exhibit a linear data dependence. In this paper, we propose an efficient method
to estimate the approximation error introduced by this rather drastic means of complexity reduction: we apply the linear decision
rule restriction not only to the primal but also to a dual version of the stochastic program. By employing techniques that
are commonly used in modern robust optimization, we show that both arising approximate problems are equivalent to tractable
linear or semidefinite programs of moderate sizes. The gap between their optimal values estimates the loss of optimality incurred
by the linear decision rule approximation. Our method remains applicable if the stochastic program has random recourse and
multiple decision stages. It also extends to cases involving ambiguous probability distributions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|