SC 98-27 Marc C. Steinbach: Recursive Direct Optimization and Successive Refinement in
Multistage Stochastic Programs
Abstract: The paper presents a new algorithmic approach for multistage
stochastic
programs which are seen as discrete optimal control problems with a
characteristic dynamic structure induced by the scenario tree.
To exploit that structure, we propose a highly efficient dynamic programming
recursion for the computationally intensive task of KKT systems solution
within a primal-dual interior point method. Convergence is drastically enhanced
by a successive refinement technique providing both primal and dual
initial estimates. Test runs on a multistage portfolio selection problem
demonstrate the performance of the method.
Keywords: Multistage stochastic programs,
discrete dynamics,
tree-sparse QP,
KKT recursion,
successive refinement
MSC: 90C15, 90C06, 65F50, 90A09