AN INTERIOR RANDOM VECTOR ALGORITHM FOR MULTISTAGE STOCHASTIC LINEAR-PROGRAMS

In this paper, an interior point algorithm for linear programs is adap ted for solving multistage stochastic linear programs. The algorithm i s based on Monteiro and Adler's path-following algorithm for determini stic linear programs. In practice, the complexity of the algorithm is linear with respect to the size of the sample space. The algorithm sta rts from a feasible solution of the problem and proceeds along a path of random vectors. The cubic polynomial complexity of the algorithm fo r deterministic linear programs is derived from the calculations of th e Newton steps. In the algorithm developed in this paper, the probabil istic structure of the problem is taken into consideration while calcu lating a Newton step and the size of the sample space appears linearly in the complexity. The development of an algorithm that requires a re latively small number of arithmetic operations, in terms of the sample space size, allows the use of the algorithm for multistage stochastic linear programs with a very large number of scenarios.