We propose a new method for certain multistage stochastic programs with linear or nonlinear objective function, combining a primal interior point approach with a linear-quadratic control problem over the scenario tree. The latter problem, which is the direction finding problem for the barrier subproblem is solved through dynamic programming using Riccati equations. In this way we combine the low iteration count of interior point methods with an efficient solver for the subproblems. The computational results are promising. We have solved a financial problem with 1,000,000 scenarios, 15,777,740 variables and 16,888,850 constraints in 20 hours on a moderate computer. © 2002 Elsevier Science B.V. All rights reserved.
The topics of this dissertation are the development of a new Stochastic Programming method and the application of Stochastic Programming in finance. Stochastic Programming is an area within Operations Research that has grown considerably over the last ten years. With new Stochastic Programming methods and more computer resources, Stochastic Programming has become a tool that at least for the moment foremost is used in the financial area. The first contribution in the dissertation is an extensive test of how well one could manage an option portfolio with optimization. When the investment strategy is back tested over a ten year period, the achieved return is much higher than the index even when the increased risk is considered. The second contribution is a new method to solve Stochastic Programming problems. The approach builds on a primal interior point approach. It shows that the resulting subproblems can be efficiently solved with Dynamic Programming. With a parallel implementation of the algorithm we manage to solve very large scale optimization problems with up to 5.8 million scenarios, 102 million variables and 290 million constraints in 80 minutes.