This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Klabjan, D. Articles by Adelman, D. Search for Related Content

An Infinite-Dimensional Linear Programming Algorithm for Deterministic Semi-Markov Decision Processes on Borel Spaces

Department of Civil and Environmental Engineering, University of Illinois at Urbana-Champaign, 205 North Matthews Avenue, Urbana, Illinois 61801
Graduate School of Business, University of Chicago, 5801 South Woodlawn Avenue, Chicago, Illinois 60637
klabjan{at}uiuc.edu
dan.adelman{at}chicagogsb.edu

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.

Key Words: infinite/semi-infinite linear programming algorithms; deterministic semi-Markov decision processes; approximate dynamic programming; ridge function approximations
History: Received: November 17, 2004; revision received: July 6, 2006;