Abstract
We devise an algorithm for solving the infinite-dimensional linear programs that arise from general deterministic semi-Markov decision processes on Borel spaces. The algorithm constructs a sequence of approximate primal-dual solutions that converge to an optimal one. The innovative idea is to approximate the dual solution with continuous piecewise linear ridge functions that naturally represent functions defined on a high-dimensional domain as linear combinations of functions defined on only a single dimension. This approximation gives rise to a primal/dual pair of semi-infinite programs, for which we show strong duality. In addition, we prove various properties of the underlying ridge functions.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 528-550 |
| Number of pages | 23 |
| Journal | Mathematics of Operations Research |
| Volume | 32 |
| Issue number | 3 |
| DOIs | |
| State | Published - Aug 2007 |
Keywords
- Approximate dynamic programming
- Deterministic semi-Markov decision processes
- Infinite/semi-infinite linear programming algorithms
- Ridge function approximations
ASJC Scopus subject areas
- General Mathematics
- Computer Science Applications
- Management Science and Operations Research