Recursive Direct Optimization and Successive Refinement in Multistage Stochastic Programs
Please always quote using this URN: urn:nbn:de:0297-zib-3706
- 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.
Author: | Marc Steinbach |
---|---|
Document Type: | ZIB-Report |
Tag: | KKT recursion; Multistage stochastic programs; discrete dynamics; successive refinement; tree-sparse QP |
MSC-Classification: | 65-XX NUMERICAL ANALYSIS / 65Fxx Numerical linear algebra / 65F50 Sparse matrices |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C06 Large-scale problems | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C15 Stochastic programming | |
Date of first Publication: | 1998/10/30 |
Series (Serial Number): | ZIB-Report (SC-98-27) |
ZIB-Reportnumber: | SC-98-27 |