Hierarchical Sparsity in Multistage Convex Stochastic Programs
Please always quote using this URN: urn:nbn:de:0297-zib-5837
- Interior point methods for multistage stochastic programs involve KKT systems with a characteristic global block structure induced by dynamic equations on the scenario tree. We generalize the recursive solution algorithm proposed in an earlier paper so that its linear complexity extends to a refined tree-sparse KKT structure. Then we analyze how the block operations can be specialized to take advantage of problem-specific sparse substructures. Savings of memory and operations for a financial engineering application are discussed in detail.
Author: | Marc Steinbach |
---|---|
Document Type: | ZIB-Report |
Tag: | Hierarchical KKT Sparsity; Multistage Stochastic Programs |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C15 Stochastic programming |
Date of first Publication: | 2000/05/03 |
Series (Serial Number): | ZIB-Report (00-15) |
ZIB-Reportnumber: | 00-15 |
Published in: | Appeared in: Stochastic Optimization. Algorithms and Applications, S. P. Uryasev, P. M. Pardalos, Applied Optimization, Vol. 54, Kluwer Academic Publishers, 2001, pp. 385-410 |