Tree-Sparse Convex Programs

Please always quote using this URN: urn:nbn:de:0297-zib-6340
  • Dynamic stochastic programs are prototypical for optimization problems with an inherent tree structure inducing characteristic sparsity patterns in the KKT systems of interior methods. We propose an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations are theoretically analyzed from a control-theoretic viewpoint and compared to each other. Associated KKT solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Marc C. Steinbach
Document Type:ZIB-Report
Tag:Convex program; discrete-time optimal control multistage stochastic program; local projection; recursive factorization; tree
MSC-Classification:15-XX LINEAR AND MULTILINEAR ALGEBRA; MATRIX THEORY / 15Axx Basic linear algebra / 15A23 Factorization of matrices
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
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C25 Convex programming
Date of first Publication:2001/04/09
Series (Serial Number):ZIB-Report (01-08)
Published in:Appeared in: Mathematical Methods of Operations Research 56 (2002) 347-376