In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. Whereas deterministic optimization problems are formulated with known parameters, real world problems almost invariably include some unknown parameters. When the parameters are known only within certain bounds, one approach to tackling such problems is called robust optimization. Here the goal is to find a solution which is feasible for all such data and optimal in some sense. Stochastic programming models are similar in style but take advantage of the fact that probability distributions governing the data are known or can be estimated. The goal here is to find some policy that is feasible for all (or almost all) the possible data instances and maximizes the expectation of some function of the decisions and the random variables. More generally, such models are formulated, solved analytically or numerically, and analyzed in order to provide useful information to a decision-maker.
Contents
- Two stage problems
- Distributional assumption
- Discretization
- Stochastic linear program
- Deterministic equivalent of a stochastic problem
- Scenario construction
- Monte Carlo sampling and Sample Average Approximation SAA Method
- Statistical Inference
- Consistency of SAA estimators
- Asymptotics of the SAA optimal value
- Multistage portfolio optimization
- Stagewise independent random process
- Biological applications
- Economic applications
- Modelling languages
- References
As an example, consider two-stage linear programs. Here the decision maker takes some action in the first stage, after which a random event occurs affecting the outcome of the first-stage decision. A recourse decision can then be made in the second stage that compensates for any bad effects that might have been experienced as a result of the first-stage decision. The optimal policy from such a model is a single first-stage policy and a collection of recourse decisions (a decision rule) defining which second-stage action should be taken in response to each random outcome.
Stochastic programming has applications in a broad range of areas ranging from finance to transportation to energy optimization. This article includes an example of optimizing an investment portfolio over time.
Two-stage problems
The basic idea of two-stage stochastic programming is that (optimal) decisions should be based on data available at the time the decisions are made and cannot depend on future observations. The two-stage formulation is widely used in stochastic programming. The general formulation of a two-stage stochastic programming problem is given by:
The classical two-stage linear stochastic programming problems can be formulated as
where
In such formulation
At the first stage we optimize (minimize in the above formulation) the cost
The considered two-stage problem is linear because the objective functions and the constraints are linear. Conceptually this is not essential and one can consider more general two-stage stochastic programs. For example, if the first-stage problem is integer, one could add integrality constraints to the first-stage problem so that the feasible set is discrete. Non-linear objectives and constraints could also be incorporated if needed.
Distributional assumption
The formulation of the above two-stage problem assumes that the second-stage data
Discretization
To solve the two-stage stochastic problem numerically, one often needs to assume that the random vector
When
- How to construct scenarios, see § Scenario construction;
- How to solve the deterministic equivalent. Optimizers such as CPLEX, GLPK and Gurobi can solve large linear/nonlinear problems. The NEOS Server, hosted at the University of Wisconsin, Madison, allows free access to many modern solvers. The structure of a deterministic equivalent is particularly amenable to apply decomposition methods, such as Benders' decomposition or scenario decomposition;
- How to measure quality of the obtained solution with respect to the "true" optimum.
These questions are not independent. For example, the number of scenarios constructed will affect both the tractability of the deterministic equivalent and the quality of the obtained solutions.
Stochastic linear program
A stochastic linear program is a specific instance of the classical two-stage stochastic program. A stochastic LP is built from a collection of multi-period linear programs (LPs), each having the same structure but somewhat different data. The
The vectors
Note that solving the
Deterministic equivalent of a stochastic problem
With a finite number of scenarios, two-stage stochastic linear programs can be modelled as large linear programming problems. This formulation is often called the deterministic equivalent linear program, or abbreviated to deterministic equivalent. (Strictly speaking a deterministic equivalent is any mathematical program that can be used to compute the optimal first-stage decision, so these will exist for continuous probability distributions as well, when one can represent the second-stage cost in some closed form.) For example, to form the deterministic equivalent to the above stochastic linear program, we assign a probability
We have a different vector
Scenario construction
In practice it might be possible to construct scenarios by eliciting experts' opinions on the future. The number of constructed scenarios should be relatively modest so that the obtained deterministic equivalent can be solved with reasonable computational effort. It is often claimed that a solution that is optimal using only a few scenarios provides more adaptable plans than one that assumes a single scenario only. In some cases such a claim could be verified by a simulation. In theory some measures of guarantee that an obtained solution solves the original problem with reasonable accuracy. Typically in applications only the first stage optimal solution
Suppose
Monte Carlo sampling and Sample Average Approximation (SAA) Method
A common approach to reduce the scenario set to a manageable size is by using Monte Carlo simulation. Suppose the total number of scenarios is very large or even infinite. Suppose further that we can generate a sample
and consequently the first-stage problem is given by
This formulation is known as the Sample Average Approximation method. The SAA problem is a function of the considered sample and in that sense is random. For a given sample
Statistical Inference
Consider the following stochastic programming problem
Here
Assume that
Suppose that we have a sample
By the Law of Large Numbers we have that, under some regularity conditions
Consistency of SAA estimators
Suppose the feasible set
- Let
g : X → R andg ^ N : X → R be a sequence of (deterministic) real valued functions. The following two properties are equivalent: - for any
x ¯ ∈ X and any sequence{ x N } ⊂ X converging tox ¯ g ^ N ( x N ) converges tog ( x ¯ ) - the function
g ( ⋅ ) is continuous onX andg ^ N ( ⋅ ) converges tog ( ⋅ ) uniformly on any compact subset ofX - If the objective of the SAA problem
g ^ N ( x ) converges to the true problem's objectiveg ( x ) with probability 1, asN → ∞ , uniformly on the feasible setX . Thenϑ ^ N ϑ ∗ N → ∞ . - Suppose that there exists a compact set
C ⊂ R n - the set
S of optimal solutions of the true problem is nonempty and is contained inC - the function
g ( x ) is finite valued and continuous onC - the sequence of functions
g ^ N ( x ) converges tog ( x ) with probability 1, asN → ∞ , uniformly inx ∈ C - for
N large enough the setS ^ N S ^ N ⊂ C with probability 1
In some situations the feasible set
where
- Suppose that there exists a compact set
C ⊂ R n - the set
S of optimal solutions of the true problem is nonempty and is contained inC - the function
g ( x ) is finite valued and continuous onC - the sequence of functions
g ^ N ( x ) converges tog ( x ) with probability 1, asN → ∞ , uniformly inx ∈ C - for
N large enough the setS ^ N S ^ N ⊂ C with probability 1 - if
x N ∈ X N x N x , thenx ∈ X - for some point
x ∈ S ∗ x N ∈ X N x N → x with probability 1.
Asymptotics of the SAA optimal value
Suppose the sample
where
In other words,
where
is the sample variance estimate of
Multistage portfolio optimization
The following is an example from finance of multi-stage stochastic programming. Suppose that at time
Consider the total returns
where in period
which depends on the realization of the random process and the decisions up to time
Suppose the objective is to maximize the expected utility of this wealth at the last period, that is, to consider the problem
This is a multistage stochastic programming problem, where stages are numbered from
In order to write dynamic programming equations, consider the above multistage problem backward in time. At the last stage
where
Similarly, at stages
whose optimal value is denoted by
Stagewise independent random process
For a general distribution of the process
and
for
Biological applications
Stochastic dynamic programming is frequently used to model animal behaviour in such fields as behavioural ecology. Empirical tests of models of optimal foraging, life-history transitions such as fledging in birds and egg laying in parasitoid wasps have shown the value of this modelling technique in explaining the evolution of behavioural decision making. These models are typically many-staged, rather than two-staged.
Economic applications
Stochastic dynamic programming is a useful tool in understanding decision making under uncertainty. The accumulation of capital stock under uncertainty is one example; often it is used by resource economists to analyze bioeconomic problems where the uncertainty enters in such as weather, etc.
Modelling languages
All discrete stochastic programming problems can be represented with any algebraic modeling language, manually implementing explicit or implicit non-anticipativity to make sure the resulting model respects the structure of the information made available at each stage. An instance of an SP problem generated by a general modelling language tends to grow quite large (linearly in the number of scenarios), and its matrix loses the structure that is intrinsic to this class of problems, which could otherwise be exploited at solution time by specific decomposition algorithms. Extensions to modelling languages specifically designed for SP are starting to appear, see:
They both can generate SMPS instance level format, which conveys in a non-redundant form the structure of the problem to the solver.