Nonlinear Programming Techniques Applied to Stochastic Programs with Recourse

Stochastic convex programs with recourse can equivalently be formulated as nonlinear convex programming problems. These possess some rather marked characteristics. Firstly, the proportion of linear to nonlinear variables is often large and leads to a natural partition of the constraints and objective. Secondly, the objective function corresponding to the nonlinear variables can vary over a wide range of possibilities; under appropriate assumptions about the underlying stochastic program it could be, for example, a smooth function, a separable polyhedral function or a nonsmooth function whose values and gradients are very expensive to compute. Thirdly, the problems are often large-scale and linearly constrained with special structure in the constraints. This paper is a comprehensive study of solution methods for stochastic programs with recourse viewed from the above standpoint. We describe a number of promising algorithmic approaches that are derived from methods of nonlinear programming. The discussion is a fairly general one, but the solution of two classes of stochastic programs with recourse are of particular interest. The first corresponds to stochastic linear programs with simple recourse and stochastic right-hand-side elements with given discrete probability distribution. The second corresponds to stochastic linear programs with complete recourse and stochastic right-hand-side vectors defined by a limited number of scenarios, each with given probability. A repeated theme is the use of the MINOS code of Murtagh and Saunders as a basis for developing suitable implementations