APPROXIMATIONS OF COUNTABLY INFINITE LINEAR PROGRAMS OVER BOUNDED MEASURE SPACES

被引：1

作者：

Kuntz, Juan ^{[1
,2
,3
]}

Thomas, Philipp ^{[1
]}

Stan, Guy-Bart ^{[2
]}

Barahona, Mauricio ^{[1
]}

机构：

[1] Imperial Coll London, Dept Math, London SW7 2AZ, England

[2] Imperial Coll London, Dept Bioengn, London SW7 2AZ, England

[3] Univ Warwick, Dept Stat, Coventry CV4 7AL, W Midlands, England

来源：

SIAM JOURNAL ON OPTIMIZATION | 2021年 / 31卷 / 01期

基金：

英国工程与自然科学研究理事会; 英国生物技术与生命科学研究理事会; 欧盟地平线“2020”;

关键词：

countably infinite linear programs; outer approximations; moment bounds; Markov chains; stationary distributions; exit distributions; occupation measures; MARKOV DECISION-PROCESSES; SIMPLEX-METHOD; OPTIMIZATION; SQUARES; SUM; MOMENTS; SYSTEMS;

D O I：

10.1137/19M1268847

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study a class of countably infinite 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 distributions of Markov chains.

引用

页码：604 / 625

页数：22

共 49 条

[1] DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization
Ahmadi, Amir Ali
Majumdar, Anirudha
[J]. SIAM JOURNAL ON APPLIED ALGEBRA AND GEOMETRY, 2019, 3 (02) : 193 - 230
[2] DENUMERABLE CONSTRAINED MARKOV DECISION-PROCESSES AND FINITE APPROXIMATIONS
ALTMAN, E
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1994, 19 (01) : 169 - 191
[3] Anderson EJ., 1987, Linear Programming in Infinite Dimensional Spaces: Theory and Applications
[4] [Anonymous], 2002, HDB MARKOV DECISION
[5] [Anonymous], 1999, STOCH MODEL SER, DOI 10.1201/9781315140223
[6] [Anonymous], 2009, MARKOV CHAINS STOCHA
[7] Asmussen S., 2003, Applied Probability and Queues, V51, DOI DOI 10.1007/B97236
[8] FINITE-STATE APPROXIMATIONS FOR DENUMERABLE STATE DISCOUNTED MARKOV DECISION-PROCESSES
CAVAZOSCADENA, R
[J]. APPLIED MATHEMATICS AND OPTIMIZATION, 1986, 14 (01) : 1 - 26
[9] Online searching with turn cost
Demaine, Erik D.
Fekete, Sandor P.
Gal, Shmuel
[J]. THEORETICAL COMPUTER SCIENCE, 2006, 361 (2-3) : 342 - 355
[10] Using Semidefinite Programming to Calculate Bounds on Stochastic Chemical Kinetic Systems at Steady State
Dowdy, Garrett R.
Barton, Paul I.
[J]. 27TH EUROPEAN SYMPOSIUM ON COMPUTER AIDED PROCESS ENGINEERING, PT C, 2017, 40C : 2239 - 2244

← 1 2 3 4 5 →