Stochastic Optimization

Unlike deterministic optimization, the objective function is not a single value but a random variable subject to statistical noise. The goal shifts to optimizing an expected value or a probabilistic quantile (e.g., Value-at-Risk).

• Sample Average Approximation (SAA): Replaces the true expected value with a Monte Carlo average computed from a finite set of scenarios.
• Stochastic Gradient Descent (SGD): Uses a noisy estimate of the gradient from a mini-batch of data rather than the full dataset, enabling scalability to massive problems.

A formulation where constraints are allowed to be violated with a small, specified probability. This is critical when hard guarantees are impossible due to inherent randomness.

• A logistics constraint might read: P(Demand > Inventory) ≤ 0.05, ensuring a 95% service level.
• Transforms an infeasible deterministic problem into a solvable probabilistic one by explicitly budgeting for risk.

Randomness is deliberately injected into the search algorithm to escape local optima and explore the solution landscape more broadly.

• Simulated Annealing: Accepts worse solutions with a probability that decays over time, mimicking the cooling of metal.
• Genetic Algorithms: Uses random mutation and crossover operations to evolve a population of solutions.
• Particle Swarm Optimization: Moves candidate solutions through the search space using randomized velocity updates influenced by personal and global bests.

Solutions are evaluated not against a single forecast, but against a discrete set of generated scenarios representing possible futures. The goal is to find a solution that performs well across all scenarios.

• Minimax Regret: Minimizes the maximum difference between the chosen solution's performance and the optimal performance had the future been known perfectly.
• Stochastic Decomposition: Iteratively builds and refines a scenario tree to approximate complex multi-stage decision processes.

Stochastic search algorithms must balance exploring unknown regions of the solution space against exploiting known high-performing regions. This is the core mechanism driving convergence.

• Thompson Sampling: Chooses actions based on the probability they are optimal, given the posterior distribution of the objective.
• Upper Confidence Bound (UCB): Selects the option with the highest potential, adding a bonus for uncertainty to encourage exploration of less-tested solutions.

A foundational framework for decisions under uncertainty. First-stage decisions (here-and-now) are made before uncertainty is resolved. Second-stage recourse actions correct for any infeasibility or suboptimality revealed later.

• Example: A warehouse lease (first-stage) is signed before seasonal demand is known. Once demand materializes, spot-market shipping (recourse) covers any shortfall.
• The objective minimizes the sum of first-stage costs and the expected value of future recourse costs.

The formal mathematical framework for modeling sequential decision-making under uncertainty. An MDP defines a state space, action space, transition probabilities, and a reward function. It provides the theoretical foundation for stochastic optimization in dynamic environments where outcomes are partly random and partly under the control of a decision-maker. Key components:

• State (S): A representation of the current environment
• Action (A): A choice available to the agent
• Transition Probability (P): The probability of moving to state s' given action a
• Reward (R): The immediate feedback signal
• Policy (π): The strategy mapping states to actions

The fundamental dilemma at the heart of stochastic optimization where an agent must balance gathering new information against leveraging known rewards. Pure exploitation risks missing superior solutions hidden in unexplored regions of the search space. Pure exploration wastes resources on suboptimal options. Common strategies include:

• ε-greedy: Select a random action with probability ε, otherwise exploit
• Upper Confidence Bound (UCB): Select actions based on optimistic estimates of their potential
• Thompson Sampling: Choose actions according to their probability of being optimal given current beliefs
• Boltzmann Exploration: Select actions probabilistically based on their estimated values, with a temperature parameter controlling randomness

A probabilistic metaheuristic inspired by the physical annealing process in metallurgy, where a material is heated and then slowly cooled to reduce defects. The algorithm accepts worse solutions with a probability that decreases over time according to a cooling schedule, allowing it to escape local optima. Key parameters:

• Temperature (T): Controls the probability of accepting worse solutions; starts high and decays
• Cooling Schedule: The rate at which temperature decreases (e.g., geometric: T_k = α * T_{k-1} where 0 < α < 1)
• Acceptance Probability: Typically P(accept) = exp(-ΔE / T), where ΔE is the increase in objective value
• Neighborhood Function: Defines how to generate candidate solutions from the current state

An approach to optimization under uncertainty that seeks solutions immune to worst-case realizations of uncertain parameters within a defined uncertainty set. Unlike stochastic optimization, which optimizes expected values, robust optimization guarantees feasibility for all parameter realizations within the uncertainty set. Key concepts:

• Uncertainty Set (U): A bounded region containing all possible parameter values (e.g., box, ellipsoidal, polyhedral sets)
• Robust Counterpart: The deterministic reformulation of the uncertain problem that ensures constraint satisfaction for all u ∈ U
• Price of Robustness: The degradation in objective value relative to the nominal optimal solution
• Adjustable Robust Optimization: Allows some decisions to adapt after uncertainty is revealed, reducing conservatism

A sequential design strategy for optimizing expensive-to-evaluate black-box functions using a probabilistic surrogate model and an acquisition function. It is particularly effective when function evaluations are costly (e.g., hyperparameter tuning, A/B testing, experimental design). Core components:

• Surrogate Model: Typically a Gaussian Process (GP) that models the posterior distribution over the objective function given observed data
• Acquisition Function: A criterion that balances exploration and exploitation to select the next evaluation point (e.g., Expected Improvement, Probability of Improvement, Upper Confidence Bound)
• Sequential Decision: Each new observation updates the surrogate model, refining the search

A heuristic search algorithm that builds a search tree by randomly sampling actions and using the simulation results to focus computation on the most promising moves. MCTS is a stochastic optimization method for sequential decision problems with large branching factors. Four phases per iteration:

• Selection: Traverse the tree from root to leaf using a tree policy (e.g., UCB1 applied to trees)
• Expansion: Add one or more child nodes to the tree
• Simulation (Rollout): Play out a random sequence of actions from the new node to a terminal state
• Backpropagation: Propagate the simulation result back up the tree, updating node statistics
• Key Application: Achieved superhuman performance in Go (AlphaGo) and is widely used in game AI and planning