An infinite-dimensional linear programming algorithm for deterministic semi-Markov decision processes on borel spaces

Diego Klabjan*, Daniel Adelman

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

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 languageEnglish (US)
Pages (from-to)528-550
Number of pages23
JournalMathematics of Operations Research
Volume32
Issue number3
DOIs
StatePublished - Aug 1 2007

Keywords

  • Approximate dynamic programming
  • Deterministic semi-Markov decision processes
  • Infinite/semi-infinite linear programming algorithms
  • Ridge function approximations

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'An infinite-dimensional linear programming algorithm for deterministic semi-Markov decision processes on borel spaces'. Together they form a unique fingerprint.

Cite this