Primal and dual linear decision rules in stochastic and robust optimization (Q647394)

Numerically tractable approximations of stochastic linear programs may be based on the application of linear decision rules. Such an approach, however, provides an upper bound for the optimal value of the stochastic program, based on a restriction of the form of feasible decisions. To complement the upper approximation by an error bound the authors suggest to use also lower bounds based on exploitation of suitable decision rules for dual stochastic programs. The upper and lower bounding approximate problems are analyzed regarding the structure of the stochastic program and properties of the probability distribution. Under modest assumptions, for stochastic programs with fixed recourse both of them can be evaluated as linear programs of moderate sizes. An extension to multistage linear problems requires additional assumptions. For stochastic programs with random recourse quadratic decision rules appear and the bounds can be approximated via semidefinite programs. Appropriateness of using linear decision rules is illustrated on a multistage inventory problem.