↑ arvau

Wikipedia / Stochastic programming

In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, but follow known probability distributions. This framework contrasts with deterministic optimization, in which all problem parameters are assumed to be known exactly. The goal of stochastic programming is to find a decision which both optimizes some criteria chosen by the decision maker, and appropriately accounts for the uncertainty of the problem parameters. Because many real-world decisions involve uncertainty, stochastic programming has found applications in a broad range of areas ranging from finance to transportation to energy optimization.

Methods

Several stochastic programming methods have been developed:

Two-stage problem definition

In such formulation:

  • is the first-stage decision variable vector.

  • is the second-stage decision variable vector.

  • contains the data of the second-stage problem.

becomes available, we optimize our behavior by solving an appropriate optimization problem.

is the cost of this recourse action.

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

is modeled as a random vector with a known, one could obtain a posteriori distribution by a Bayesian update.

Scenario-based approach

Discretization

has a finite number of possible realizations, called scenarios and, moreover, the two-stage problem can be formulated as one large linear programming problem (this is called the deterministic equivalent of the original problem, see section ).

has an infinite (or very large) number of possible realizations the standard approach is then to represent this distribution by scenarios. This approach raises three questions, namely:

  1. How to construct scenarios, see ;

  2. How to solve the deterministic equivalent. Optimizers such as CPLEX, and GLPK 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;

  3. 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 programming

A stochastic linear program scenario, may be regarded as having the following form:

involve only first-period variables and are the same in every scenario. The other constraints involve variables of later periods and differ in some respects from scenario to scenario, reflecting uncertainty about the future.

scenario in the second period with no uncertainty. In order to incorporate uncertainties in the second stage, one should assign probabilities to different scenarios and solve the corresponding deterministic equivalent.

Deterministic equivalent of a stochastic problem

. Then we can minimize the expected value of the objective, subject to the constraints from all scenarios:

need only be specified once, while the remaining constraints must be given separately for each scenario.

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 has a practical value since almost always a "true" realization of the random data will be different from the set of constructed (generated) scenarios.

. Such exponential growth have continuous distributions.

Monte Carlo sampling and sample average approximation (SAA) method

. Usually the sample is assumed to be independent and identically distributed is approximated by the sample average

and consequently the first-stage problem is given by

This formulation is known as the sample average approximation.

Statistical inference

Consider the following stochastic programming problem

is given by the optimal value of the corresponding second-stage problem.

is well defined and finite valued is finite almost surely.

, or it can be generated by Monte Carlo sampling techniques. Then we can formulate a corresponding sample average approximation

By the law of large numbers is an unbiased.

Consistency of SAA estimators

be the optimal value and the set of optimal solutions, respectively, of the SAA problem.

be a sequence of (deterministic) real valued functions. The following two properties are equivalent:

  1. .

such that

  • with probability 1

    1. denotes the , defined as

of the SAA problem is estimated, then the corresponding SAA problem takes the form

depending on the sample and therefore is random. Nevertheless, consistency results for SAA estimators can still be derived under some additional assumptions:

such that

  • with probability 1

  • with probability 1.

    1. .

Asymptotics of the SAA optimal value

is supposed to be finite. Moreover, by the central limit theorem we have that

denotes convergence in distribution has a normal distribution.

has asymptotically normal% confidence interval:

denotes the cdf of the standard normal distribution) and

.

Applications and examples

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.

Example: multistage portfolio optimization

should hold.

being constant, defines an implementable policy of the decision process. It is said that such a policy is feasible, and the balance of wealth constraints,

is given by

.

Suppose the objective is to maximize the expected utility of this wealth at the last period, that is, to consider the problem

. This can be done in various ways. For example, one can construct a particular scenario tree defining time evolution

In order to write dynamic programming has been chosen. Therefore, one needs to solve the following problem

denotes the conditional expectation.

, one should solve the problem

, one solves the problem

Stagewise independent random process

is the optimal value of the problem

is the optimal value of

.

Software tools

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:

  • AIMMS – supports the definition of SP problems

  • EMP SP (Extended Mathematical Programming for Stochastic Programming) – a module of GAMS created to facilitate stochastic programming (includes keywords for parametric distributions, chance constraints and risk measures such as Value at risk and Expected shortfall).

  • SAMPL – a set of extensions to AMPL specifically designed to express stochastic programs (includes syntax for chance constraints, integrated chance constraints and robust optimization problems)

They both can generate SMPS instance level format, which conveys in a non-redundant form the structure of the problem to the solver.

See also

References

Further reading