Details
| Original language | English |
|---|---|
| Pages (from-to) | 347-376 |
| Number of pages | 30 |
| Journal | Mathematical Methods of Operations Research |
| Volume | 56 |
| Issue number | 3 |
| Publication status | Published - Jan 2003 |
| Externally published | Yes |
Abstract
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 perspective and compared to each other. Associated KKT system solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.
Keywords
- Convex program, Discrete-time optimal control, Dynamic stochastic program, Sparse factorization, Tree
ASJC Scopus subject areas
- Computer Science(all)
- Software
- Mathematics(all)
- Decision Sciences(all)
- Management Science and Operations Research
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Mathematical Methods of Operations Research, Vol. 56, No. 3, 01.2003, p. 347-376.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Tree-sparse convex programs
AU - Steinbach, Marc C.
PY - 2003/1
Y1 - 2003/1
N2 - 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 perspective and compared to each other. Associated KKT system solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.
AB - 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 perspective and compared to each other. Associated KKT system solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.
KW - Convex program
KW - Discrete-time optimal control
KW - Dynamic stochastic program
KW - Sparse factorization
KW - Tree
UR - http://www.scopus.com/inward/record.url?scp=0036461530&partnerID=8YFLogxK
U2 - 10.1007/s001860200227
DO - 10.1007/s001860200227
M3 - Article
AN - SCOPUS:0036461530
VL - 56
SP - 347
EP - 376
JO - Mathematical Methods of Operations Research
JF - Mathematical Methods of Operations Research
SN - 1432-2994
IS - 3
ER -