65F50 Sparse matrices
Refine
Document Type
- ZIB-Report (5)
Language
- English (5)
Has Fulltext
- yes (5)
Is part of the Bibliography
- no (5)
Keywords
- KKT recursion (2)
- discrete dynamics (2)
- operative planning (2)
- tree-sparse QP (2)
- Convex program (1)
- Gas network (1)
- KKT system (1)
- KKT system factorization (1)
- Multistage stochastic programs (1)
- PDE constrained optimization (1)
Institute
- ZIB Allgemein (5)
Operative planning in gas distribution networks leads to large-scale mixed-integer optimization problems involving a hyperbolic PDE defined on a graph. We consider the NLP obtained under prescribed combinatorial decisions---or as relaxation in a branch and bound framework, addressing in particular the KKT systems arising in primal-dual interior methods. We propose a custom solution algorithm using sparse local projections, based on the KKT systems' structual properties induced by the discretized gas flow equations in combination with the underlying network topology. The numerical efficiency and accuracy of the algorithm are investigated, and detailed computational comparisons with a control space method and with the multifrontal solver MA27 are provided.
Operative planning in gas networks with prescribed binary decisions yields large scale nonlinear programs defined on graphs. We study the structure of the KKT systems arising in interior methods and present a customized direct solution algorithm. Computational results indicate that the algorithm is suitable for optimization in small and medium-sized gas networks.
Tree-Sparse Convex Programs
(2001)
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.
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.
Multistage stochastic programs can be 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 an interior point method. Test runs on a multistage portfolio selection problem demonstrate the performance of the algorithm.