Monte Carlo methods for multi-stage stochastic programs

Stochastic programming is a natural and powerful extension of deterministic mathematical programming, and it is effectively utilized for analyzing optimization problems when the problem’s parameters are not known with certainty. These uncertain parameters are treated as a random vector with a known distribution in the stochastic programming framework. Typically, the size of stochastic programming models is large due to the number of dimensions and realizations of the random vector. With recent advances in optimization algorithms and computing technology, an increasing number of realistically-sized two- and multi-stage stochastic programming models are being successfully formulated and solved. Despite these successes, multi-stage stochastic programs in which the random vector has a large number of dimensions and/or realizations (or is even continuous), still remain a computational challenge primarily because of the exponential growth of the model’s size with respect to the number of stages. In this dissertation, we exploit special structures in order to attack these computationally difficult problems. Our research can be broadly divided into three parts. First, we propose two Monte Carlo sampling-based solution methods for multi-stage stochastic programs. Both methods exploit special structures for a particular class of multi-stage problems, and result in feasible solution policies. These policies have desirable asymptotic properties, but, of course, in practice are generated using finite scenario trees. As a result, in the second part of the dissertation, we develop Monte Carlo techniques to determine the quality of an arbitrary feasible policy. In particular, we build a statistically-based point estimate for a lower bound of the optimal objective function value for a minimization problem, and use it to construct a confidence interval on the solution’s quality. In the third part, we aim to develop procedures to reduce the bias associated with the lower-bound estimator, thereby improving our ability to construct a reasonably tight confidence interval on the solution’s quality. Towards this goal, we vary the number of descendants in the sample tree to reduce the bias in the context of American-style option pricing and stochastic lot sizing. All proposed methodologies are numerically tested on problems from the literature.