Method for solving stochastic control problems of linear systems in high dimension
AssigneeInternational Business Machines Corporation
InventorNimrod Megiddo
Life of this patent
Estimating the term…
Abstract
Stochastic control problems of linear systems in high dimensions are solved by modeling a structured Markov Decision Process (MDP). A state space for the MDP is a polyhedron in a Euclidean space and one or more actions that are feasible in a state of the state space are linearly constrained with respect to the state. One or more approximations are built from above and from below to a value function for the state using representations that facilitate the computation of approximately optimal actions at any given state by linear programming.
Claims36
A method for solving, in a computer, stochastic control problems of linear systems in high dimensions, comprising:
- (a) modeling, in the computer, a structured Markov Decision Process (MDP), wherein a state space for the MDP is a polyhedron in a Euclidean space and one or more actions that are feasible in a state of the state space are linearly constrained with respect to the state;
- and
- (b) building, in the computer, one or more approximations from above and from below to a value function for the state using representations that facilitate the computation of approximately optimal actions at any given state by linear programming.
A computer apparatus for solving stochastic control problems of linear systems in high dimensions, comprising:
- (a) a computer;
- (b) logic, performed by the computer, for modeling a structured Markov Decision Process (MDP), wherein a state space for the MDP is a polyhedron in a Euclidean space and one or more actions that are feasible in a state of the state space are linearly constrained with respect to the state;
- and
- (c) logic, performed by the computer, for building one or more approximations from above and from below to a value function for the state using representations that facilitate the computation of approximately optimal actions at any given state by linear programming.
An article of manufacture embodying a computer readable medium storing a computer program comprising computer executable instructions, which when executed by a computer perform a process for solving stochastic control problems of linear systems in high dimensions, the computer program comprising instructions for:
- (a) modeling a structured Markov Decision Process (MDP), wherein a state space for the MDP is a polyhedron in a Euclidean space and one or more actions that are feasible in a state of the state space are linearly constrained with respect to the state;
- and
- (b) building one or more approximations from above and from below to a value function for the state using representations that facilitate the computation of approximately optimal actions at any given state by linear programming.
Dependencies are inferred from the claim text.