Approximations of Countably Infinite Linear Programs over Bounded Measure Spaces
From MaRDI portal
Abstract: 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 distributions of Markov~chains.
Recommendations
- Approximation Schemes for Infinite Linear Programs
- scientific article; zbMATH DE number 3174750
- scientific article; zbMATH DE number 1217739
- An Approximation Approach for Linear Programming in Measure Space
- A simplex method for countably infinite linear programs
- scientific article; zbMATH DE number 854127
- Measure theoretic versions of linear programming
- Linear programming in measure spaces
- Semi-infinite linear optimization on noncompact spaces and its application to approximation theory
- Infinite-dimensional convex programming with applications to constrained approximation
Cites work
- A linear programming approach to nonstationary infinite-horizon Markov decision processes
- A LINEAR PROGRAMMING APPROACH TO THE STEADY-STATE ANALYSIS OF REFLECTED BROWNIAN MOTION
- A shadow simplex method for infinite linear programs
- A simplex algorithm for minimum-cost network-flow problems in infinite networks
- A simplex method for uncapacitated pure-supply infinite network flow problems
- Applied Probability and Queues
- Approximating Ergodic Average Reward Continuous-Time Controlled Markov Chains
- Approximation Schemes for Infinite Linear Programs
- Bounding Stationary Expectations of Markov Processes
- Circumventing the Slater conundrum in countably infinite linear programs
- Computing Moments of the Exit Time Distribution for Markov Processes by Linear Programming
- Convergence of controlled models and finite-state approximation for discounted continuous-time Markov decision processes with constraints
- Denumerable Constrained Markov Decision Processes and Finite Approximations
- Discounted continuous-time controlled Markov chains: convergence of control models
- Discounted Continuous-Time Markov Decision Processes with Constraints: Unbounded Transition and Loss Rates
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Extreme point characterizations for infinite network flow problems
- Fast ADMM for Sum-of-Squares Programs Using Partial Orthogonality
- Finite horizon approximations of infinite horizon linear programs
- Finite-state approximations for denumerable state discounted Markov decision processes
- GloptiPoly 3: moments, optimization and semidefinite programming
- Handbook of Markov decision processes. Methods and applications
- scientific article; zbMATH DE number 4029251 (Why is no real title available?)
- scientific article; zbMATH DE number 1325008 (Why is no real title available?)
- scientific article; zbMATH DE number 1348599 (Why is no real title available?)
- scientific article; zbMATH DE number 700091 (Why is no real title available?)
- Infinite horizon production planning in time-varying systems with convex production and inventory costs
- Linear programming approximations for Markov control processes in metric spaces
- Markov chains and invariant probabilities
- Markov Chains and Stochastic Stability
- Online searching with turn cost
- Some questions concerning the approximation of the optimal value of infinite-dimensional problems in linear programming
- Stability of Markovian processes III: Foster–Lyapunov criteria for continuous-time processes
- Stationarity Equations in Continuous Time Markov Chains
- Stationary distributions of continuous-time Markov chains: a review of theory and truncation-based approximations
- Stationary dual prices and depreciation
- Sum-of-squares optimization without semidefinite programming
- Sums of squares, moment matrices and optimization over polynomials
Cited in
(6)- scientific article; zbMATH DE number 3174750 (Why is no real title available?)
- From infinite to finite programs: explicit error bounds with applications to approximate dynamic programming
- A simplex method for countably infinite linear programs
- On finite approximations to Markov decision processes with recursive and nonlinear discounting
- An Approximation Approach for Linear Programming in Measure Space
- Abstraction-guided truncations for stationary distributions of Markov population models
This page was built for publication: Approximations of Countably Infinite Linear Programs over Bounded Measure Spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5853565)
