Optimization Online


Primal and dual linear decision rules in stochastic and robust optimization

Daniel Kuhn (dkuhn***at***doc.ic.ac.uk)
Wolfram Wiesemann (wwiesema***at***doc.ic.ac.uk)
Angelos Georghiou (ag604***at***doc.ic.ac.uk)

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 modelled 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 using (established) primal and (novel) dual robust optimization techniques, 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: Linear decision rules, stochastic optimization, robust optimization, error bounds, semidefinite programming

Category 1: Robust Optimization

Category 2: Stochastic Programming

Citation: Working paper, Department of Computing, Imperial College London, February 2009

Download: [PDF]

Entry Submitted: 02/04/2009
Entry Accepted: 02/04/2009
Entry Last Modified: 11/10/2009

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 Programming Society