A Separable Piecewise Linear Upper Bound for Stochastic Linear Programs.

Abstract

Stochastic linear programs require the evaluation of an integral in which the integrand is itself the value of a linear program. This integration is often approximated by discrete distributions that bound the integral from above or below. A difficulty with previous upper bounds is that they generally require a number of function evaluations that grows exponentially in the number of variables. We give a new upper bound that requires operations that only grow polynomially in the number of random variables. We show that this bound is sharp if the function is linear and give computational results to illustrate its performance. Keywords: Stochastic programming, Upper bounds, Convex functions, Integration.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1987
Accession Number
ADA178694

Entities

People

  • John R. Birge
  • Stein W. Wallace

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Availability
  • Classification
  • Computer Programming
  • Engineering
  • Evolutionary Algorithms
  • Integrals
  • Linear Programming
  • Mathematical Programming
  • Michigan
  • Operations Research
  • Optimization
  • Probability
  • Random Variables
  • Schools
  • Security
  • Statistics

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Calculus or Mathematical Analysis
  • Graph Algorithms and Convex Optimization.