Stochastic optimization

Stochastic optimization is the branch of mathematical optimization concerned with decision problems in which some of the data are uncertain and are represented as random variables with a known or estimated probability distribution. Rather than optimizing against a single deterministic scenario, the decision maker optimizes an expectation, a quantile, or another functional of a random objective, often subject to constraints that must hold either on average, with high probability, or for every realization. The paradigm originates with George Dantzig's 1955 formulation of "linear programming under uncertainty", which introduced the idea of choosing a plan before uncertainty is resolved and then paying a cost to adjust once it is observed. The modern theory is developed at length in the standard monographs of Birge and Louveaux and of Shapiro, Dentcheva and Ruszczyński.

The term is used in two overlapping senses. In the mathematical-programming tradition it denotes stochastic programming: models in which the uncertainty is described by a distribution and the objective is an expectation or a risk measure. In a broader sense it also covers stochastic search and simulation-based methods whose iterations are themselves randomized. This article treats the first sense — optimization of a decision under distributional uncertainty — and contrasts it with the deterministic worst-case alternative, robust optimization.

Two-stage and multistage recourse

The canonical model is the two-stage stochastic program with recourse. A first-stage decision $x$ is chosen "here and now", before the random vector $\xi$ is observed; after a realization of $\xi$ becomes known, a second-stage or recourse decision $y$ is taken to correct or complete the plan. Writing $Q(x,\xi )$ for the optimal second-stage cost, the problem is to minimize $c^{\mathrm{\top }}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ over the feasible first-stage set. The expected recourse function is the object that couples the stages, and a central structural result is that for problems with fixed recourse and finitely many scenarios this function is piecewise linear and convex in $x$, which makes the two-stage problem a large but convex program. Extending the idea to several decision epochs, in which information is revealed and decisions are taken in alternating stages, gives the multistage stochastic program, whose scenario representation grows exponentially in the number of stages.

Because the expectation is an integral over the distribution of $\xi$, the exact problem is tractable in closed form only in special cases. When the distribution is discretized into a finite set of scenarios with associated probabilities, the two-stage program becomes a deterministic-equivalent linear or mixed-integer program; decomposition methods such as the L-shaped (Benders) method exploit the block structure of this equivalent to solve it without forming it in full.

Sample average approximation

When the distribution is continuous or high-dimensional, a widely used strategy is sample average approximation (SAA), also called the sample-path or Monte Carlo method. A sample ${\xi }^1,\dots ,{\xi }^N$ is drawn from the distribution of $\xi$, the true expectation is replaced by the empirical average $\frac{1}{N}\sum _{k}Q(x,{\xi }^k)$, and the resulting deterministic problem is solved. Kleywegt, Shapiro and Homem-de-Mello analyzed this scheme for stochastic discrete optimization and showed that, under mild conditions, the probability that an optimal solution of the sampled problem is an exact optimal solution of the true problem approaches one exponentially fast as the sample size $N$ grows. Because SAA reduces a stochastic program to a sequence of ordinary optimization problems driven by simulated data, it links stochastic programming to the Monte Carlo method and to statistical estimation, and it comes with confidence-interval procedures that bound the optimality gap of the returned solution. Convergence of the sampled optimal value and optimal solutions to their true counterparts is treated generally under the heading of epigraphical or epi-convergence in the reference texts.

Chance constraints

Not every requirement can be averaged. When a constraint expresses reliability — a service level that must be met, a resource that must not be exceeded — it is natural to require that it hold with at least a prescribed probability. Charnes and Cooper introduced chance-constrained programming for exactly this situation, replacing a hard constraint $g(x,\xi )\le 0$ by the probabilistic requirement $\mathrm{Pr}\{g(x,\xi )\le 0\}\ge 1-\alpha$ for a small risk level $\alpha$. Individual chance constraints control each requirement separately, while a joint chance constraint bounds the probability that any of several requirements is violated. Chance-constrained feasible sets are generally non-convex, and much of the subsequent theory concerns conditions — such as log-concavity of the underlying distribution — under which convexity is recovered, together with tractable convex approximations and sampling-based reformulations.

Risk measures

Optimizing the expected cost is risk-neutral: it treats a gain and an equally likely loss symmetrically and is insensitive to the spread of outcomes. Risk-averse stochastic optimization instead optimizes a risk measure of the random cost. A widely adopted choice is the Conditional value at risk (CVaR), the expected loss in the worst $\alpha$ fraction of outcomes. Rockafellar and Uryasev showed that CVaR can be minimized by minimizing a convex auxiliary function jointly over the decision and an added scalar, so that risk-averse problems retain the convexity and linear-programming structure of their risk-neutral counterparts. This result underlies risk-averse Portfolio optimization and, more generally, the theory of coherent and convex risk measures that provides the axiomatic backbone of modern risk-averse stochastic programming.

Contrast with robust optimization

Stochastic optimization presumes a probability distribution and optimizes an expectation or a probabilistic guarantee. Robust optimization takes a different stance: it dispenses with the distribution, describes uncertainty by an uncertainty set of possible parameter values, and optimizes against the worst case within that set. Bertsimas, Brown and Caramanis survey the theory and note that, for many uncertainty sets, the robust counterpart of a tractable nominal problem remains a tractable convex program, which makes robust models attractive when a distribution is unavailable or unreliable. The two paradigms are complementary rather than exclusive: distributionally robust optimization occupies the middle ground, optimizing the worst-case expectation over a family (an "ambiguity set") of distributions consistent with the available data, and chance constraints can be viewed as connecting the probabilistic and set-based views.

Application to workforce and capacity planning

Staffing and capacity planning in contact centers and other service operations is a natural setting for stochastic optimization because future demand — call and contact volumes, handle times, shrinkage — is uncertain when schedules must be committed. A two-stage recourse formulation fits the planning horizon directly: the first stage fixes the staffing plan or shift roster before demand is known, and the second stage represents the recourse actions available once demand materializes, such as overtime, voluntary time off, or the use of a flexible reserve pool, each with its own cost. Chance constraints express service-level agreements, requiring, for example, that the probability of meeting an answer-time target across an interval be at least a stated value rather than met only in expectation. Sample average approximation lets planners drive such models with simulated or historical demand scenarios instead of a closed-form demand distribution. Where demand can shift abruptly — during Irregular operations or demand shocks — a risk measure such as CVaR, or a distributionally robust formulation, hedges against the tail scenarios that a risk-neutral expected-cost plan would under-weight.

See also

• Mathematical optimization
• Monte Carlo method
• Conditional value at risk
• Portfolio optimization
• Irregular operations