## 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.

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 |