Stochastic programming

Stochastic programming — a branch of mathematical programming that develops models and methods for solving optimization problems under uncertainty, when some model parameters are not known exactly but are represented as random variables with known or estimated probability distributions.

Unlike deterministic problems, where all data are considered given constants, stochastic programming aims to find a solution (or decision policy) that is optimal in some statistical sense. Most often this means minimizing or maximizing the expected value of the objective function. The key idea is to find a decision policy that will be best "on average" across all possible realizations of random parameters, which is especially relevant for problems where decisions are made repeatedly under similar conditions (e.g., in inventory management or power systems).

Mathematical Problem Formulation

In general form, the stochastic programming problem can be formulated as: $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ where:

• $x$ — the vector of decision variables (decisions) that need to be determined.
• $X$ — the set of feasible solutions for $x$, defined by deterministic constraints.
• $\xi$ — a random vector representing the uncertain parameters of the problem (e.g., demand, prices, weather conditions).
• $f(x,\xi )$ — the objective function, whose value depends on both the decision $x$ and the realization of the random vector $\xi$.
• $\mathbb{𝔼}[\cdot ]$ — the expectation operator, computed over the probability distribution of vector $\xi$.

A crucial principle underlying multi-stage stochastic models is the non-anticipativity principle. It states that decisions made at any stage can only depend on information available at that moment and cannot "look into the future".

Two-Stage Problem with Recourse

The most common model is the two-stage stochastic program with recourse. The decision-making process is divided into two stages:

1. First stage: A "here-and-now" decision is made — the vector $x$ is determined. This decision must be made before the specific realization of the random vector $\xi$ becomes known.
2. Second stage: After the random event has occurred, a corrective or recourse decision is made — the vector $y(\xi )$, aimed at minimizing negative consequences or utilizing favorable opportunities arising from the combination of the first-stage decision $x$ and outcome $\xi$.

Mathematically, the two-stage stochastic linear programming problem is formulated as follows: $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ subject to first-stage constraints: $Ax=b,x\ge 0$. Here $Q(x,\xi )$ is the recourse function, representing the optimal value of the second-stage problem: $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ where $\xi$ is a random vector containing parameters $q(\xi ),T(\xi )$ and $h(\xi )$; and $c,A,b$ and $W$ are deterministic parameters.

Key Properties and Theorems

• Convexity: One of the fundamental results of the theory is that for two-stage stochastic linear programming problems, the expected recourse function $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ is a convex function. This property is of great importance as it guarantees that the overall first-stage problem is a convex programming problem, for which efficient solution methods exist and the global optimum coincides with the local optimum.
• Deterministic equivalent: If the random vector $\xi$ has a finite number of possible realizations (scenarios) ${\xi }_1,\dots ,{\xi }_K$ with probabilities $p_1,\dots ,p_K$, then the stochastic programming problem can be reformulated as one large deterministic optimization problem. In this case, the expectation is replaced by a weighted sum over all scenarios. However, the size of this problem grows linearly with the number of scenarios, leading to the "curse of dimensionality" and making this approach computationally intractable for a large number of scenarios.

Comparison with Robust Optimization

Stochastic programming is one of several approaches to optimization under uncertainty. Its key difference from robust optimization lies in the way uncertainty is modeled and the optimality criterion.

Comparison of Approaches to Optimization under Uncertainty

Criterion	Stochastic Optimization	Robust Optimization
Uncertainty representation	Parameters are random variables with known probability distribution	Parameters belong to a given uncertainty set, distribution not required
Optimality criterion	Optimization of expected value of objective function	Optimization for worst-case scenario (minimax)
Solution characteristics	Policy optimal "on average," may be infeasible for rare scenarios	Solution guaranteed to be feasible for all realizations; may be conservative

Examples

• Newsvendor problem: A classic inventory management problem where a seller must decide what quantity of goods to purchase without knowing exact future demand. The solution balances between the risk of losses from surplus and the risk of lost profit from shortage.
• Farmer problem: A farmer decides how many acres of land to allocate to different crops on a total area, not knowing the future weather that affects crop yields. After the weather becomes known, the farmer can take corrective actions (e.g., sell surpluses or purchase missing crops on the market).

See also

• Probability theory
• Simulation modeling
• Dynamic programming
• Integer programming