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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Marc C. 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)
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