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 条

[21] GloptiPoly 3: moments, optimization and semidefinite programming
Henrion, Didier
Lasserre, Jean-Bernard
Lofberg, Johan
[J]. OPTIMIZATION METHODS & SOFTWARE, 2009, 24 (4-5) : 761 - 779
[22] Linear programming approximations for Markov control processes in metric spaces
Hernandez-Lerma, O
Lasserre, JB
[J]. ACTA APPLICANDAE MATHEMATICAE, 1998, 51 (02) : 123 - 139
[23] Approximation schemes for infinite linear programs
Hernandez-Lerma, O
Lasserre, JB
[J]. SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (04) : 973 - 988
[24] HERNANDEZ-LERMA O., 2003, MARKOV CHAINS INVARI, DOI [10.1007/978-3-0348-8024-4, DOI 10.1007/978-3-0348-8024-4]
[25] Hernndez-Lerma O., 1999, Further topics on discrete-time Markov control processes, VVol. 42, DOI [10.1007/978-1-4612-0561-6, DOI 10.1007/978-1-4612-0561-6]
[26] Huang K., 2005, THESIS
[27] STATIONARY DUAL PRICES AND DEPRECIATION
JONES, PC
ZYDIAK, JL
HOPP, WJ
[J]. MATHEMATICAL PROGRAMMING, 1988, 41 (03) : 357 - 366
[28] KUNTZ J., SIAM REV
[29] Kuntz J., 2017, THESIS
[30] KUNTZ J., 2020, ARXIV200102183MATHPR

← 1 2 3 4 5 →