publication . Article . Preprint . 2018

Approximations of Countably Infinite Linear Programs over Bounded Measure Spaces

Juan Kuntz; Philipp Thomas; Guy-Bart Stan; Mauricio Barahona;
Open Access
  • Published: 08 Oct 2018 Journal: SIAM Journal on Optimization, volume 31, pages 604-625 (issn: 1052-6234, eissn: 1095-7189, Copyright policy)
  • Publisher: Society for Industrial & Applied Mathematics (SIAM)
  • Country: United Kingdom
We study a class of countably-infinite-dimensional linear programs (CILPs) whose feasible sets are bounded subsets of appropriately defined spaces of measures. The optimal value, optimal points, and minimal points of these CILPs can be approximated by solving finite-dimensional linear programs. We show how to construct finite-dimensional programs that lead to approximations with easy-to-evaluate error bounds, and we prove that the errors converge to zero as the size of the finite-dimensional programs approaches that of the original problem. We discuss the use of our methods in the computation of the stationary distributions, occupation measures, and exit distrib...
Persistent Identifiers
free text keywords: Theoretical Computer Science, Software, math.OC, math.PR, 0102 Applied Mathematics, 0103 Numerical and Computational Mathematics, Operations Research, Mathematics - Optimization and Control, Mathematics - Probability
Funded by
UKRI| Engineering Fellowships for Growth: Systems and control engineering framework for robust and efficient synthetic biology
  • Funder: UK Research and Innovation (UKRI)
  • Project Code: EP/M002187/1
  • Funding stream: EPSRC
UKRI| EPSRC Centre for Mathematics of Precision Healthcare
  • Funder: UK Research and Innovation (UKRI)
  • Project Code: EP/N014529/1
  • Funding stream: EPSRC
Control Engineering of Biological Systems for Reliable Synthetic Biology Applications
  • Funder: European Commission (EC)
  • Project Code: 766840
  • Funding stream: H2020 | RIA
Validated by funder
UKRI| Doctoral Training Grant
  • Funder: UK Research and Innovation (UKRI)
  • Project Code: BB/F017510/1
  • Funding stream: BBSRC
FET H2020FET OPEN: FET-Open research and innovation actions
FET H2020FET OPEN: Control Engineering of Biological Systems for Reliable Synthetic Biology Applications
34 references, page 1 of 3

[1] E. Altman. Denumerable constrained Markov decision processes and finite approximations. Math. Oper. Res., 19(1):169-191, 1994.

[2] E. Altman. Constrained Markov decision processes. Chapman & Hall/CRC, 1999.

[3] E. J. Anderson and P. Nash. Linear programming in infinite-dimensional spaces: theory and applications. Wiley, 1987.

[4] S. Asmussen. Applied Probability and Queues. Springer-Verlag New York, 2003.

[5] R. Cavazos-Cadena. Finite-state approximations for denumerable state discounted markov decision processes. Appl. Math. Optim., 14(1):1-26, 1986.

[6] K. L. Chung. Markov chains with stationary transition probabilities. Springer, 2nd edition, 1967.

[7] E. D. Demaine, S. P. Fekete, and S. Gal. Online searching with turn cost. Theor. Comput. Sci., 361(2-3):342-355, sep 2006. [OpenAIRE]

[8] G. R. Dowdy and P. I. Barton. Using Semidefinite Programming to Calculate Bounds on Stochastic Chemical Kinetic Systems at Steady State. Computer Aided Chemical Engineering, 40:2239-2244, 2017.

[9] G. R. Dowdy and P. I. Barton. Bounds on stochastic chemical kinetic systems at steady state. J. Chem. Phys., 148(8):084106, 2018.

[10] E. Feinberg and A. Shwartz. Handbook of Markov decision processes: methods and algorithms. Kluwer, Boston, 2002.

[11] A. Ghate. Circumventing the Slater conundrum in countably infinite linear programs. Eur. J. Oper. Res., 246(3):708-720, 2015. [OpenAIRE]

[12] A. Ghate. Inverse optimization in countably infinite linear programs. 43(3):231-235, 2015. [OpenAIRE]

[13] A. Ghate, D. Sharma, and R. L. Smith. A shadow simplex method for infinite linear programs. Oper. Res., 58(4-part-1):865-877, 2010.

[14] A. Ghate and R. L. Smith. A linear programming approach to nonstationary infinite-horizon Markov decision processes. Oper. Res., 61(2):413-425, 2013.

[15] K. R. Ghusinga, C. A. Vargas-Garcia, A. Lamperski, and A. Singh. Exact lower and upper bounds on stationary moments in stochastic biochemical systems. Phys. Biol., 14(4):04LT01, 2017.

34 references, page 1 of 3
Any information missing or wrong?Report an Issue