Approximations

• J. R. Birge and Liqun Qi, "Continuous Approximation Schemes for Stochastic Programming," Annals of Operations Research 56 (1995) 15-38.

  Abstract

  One of the main methods for solving stochastic programs is approximation by discretizing the probability distribution. However, discretization may lose differentiability of expectational functionals. The complexity of discrete approximation schemes also increases exponentially as the dimension of the random vector increases. On the other hand, stochastic methods can solve stochastic programs with larger dimensions but their convergence is in the sense of probability one. In this paper, we study the differentiability property of stochastic two-stage programs and discuss continuous approximation methods for stochastic programs. We present several ways to calculate and estimate this derivative. We then design several continuous approximation schemes and study their convergence behavior and implementation. The methods include several types of truncation approximation, lower dimensional approximation and limited basis approximation.

• C.J. Donohue and J. R. Birge, " An Upper Bound on a Specific Class of Convex Functions, " Technical Report, IOE, University of Michigan.

  Abstract

  This paper shows how to construct a bound with only two functions evaluations when a convex function has a property called convex marginal returns. Examples of this property are given.

• C.J. Donohue and J. R. Birge, " An Upper Bound on the Network Recourse Function, " Technical Report, IOE, University of Michigan.

  Abstract

  This paper shows how to construct a bound for a stochastic with network recourse such as a vehicle allocation problem.

• J.R. Birge, S.M. Pollock, and L. Qi, " A Quadratic Recourse Function for the Two-Stage Stochastic Program," Technical Report, Department of Industrial and Operations Engineering, University of Michigan, 1995.

  Abstract

  We present a quadratic recourse representation of the two-stage stochastic linear problem. Unlike the usual linear recourse model, it is differentiable with respect to the first stage decision variables. This offers the possibility of applying high convergence rate methods to solve the two-stage problem. We show that the quadratic recourse function approximates the linear recourse function (and the corresponding solution of the two-stage problem with quadratic recourse converges to the solution of the two-stage problem with linear recourse) as a parameter $k \to \infty$ and another parameter $\epsilon_k \to 0$. We also give a bound for this approximation.