Computational Algorithms for Convex Stochastic Programs with Simple Recourse

Abstract

This paper presents computational algorithms for the solution of a class of stochastic programming problems. Let x and y represent the decision and state vectors, and suppose that x must be chosen from some set K and that y is a linear function of both x and an additive random vector ξ. If y is uniquely determined once x is chosen and ξ is observed, we say that the problem has simple recourse. The algorithms presented apply, e.g., when the preference functions h(x) and g(y) are convex, and continuously differentiable, k is a convex polytope, ξ has a distribution that satisfies mild convergence conditions, and the objective is to minimize the expectation of the sum of the two preference functions. An illustrative example of an inventory problem is formulated, and the special case when g is asymmetric, quadratic, and separable is presented in detail to illustrate the calculations involved.