Adjustable robust optimization
Adjustable robust optimization, also called adaptive robust optimization or multistage robust optimization, is a branch of mathematical optimization concerned with decisions made under uncertainty when part of the decision process occurs after uncertain information becomes observable. It extends robust optimization, in which feasibility is required for every realization in a prescribed uncertainty set, by permitting selected decision variables to depend on information revealed during the modeled time horizon.
The defining restriction is nonanticipativity: an adjustable decision may depend only on information already observed when that decision is implemented. Adjustable robust models therefore distinguish between uncertainty itself and the information structure through which uncertainty becomes available. This distinction separates them from static robust models, whose variables are fixed before uncertainty is revealed, and from unrestricted wait-and-see formulations, whose decisions may depend on the entire uncertainty realization.
Mathematical formulation
A two-stage adjustable robust linear problem can be written as
[ \begin{aligned} \min_{x,,y(\cdot)} \quad & c^\mathsf{T}x+ \sup_{\xi\in\mathcal U}d(\xi)^\mathsf{T}y(\xi)\ \text{subject to}\quad & A(\xi)x+B(\xi)y(\xi)\leq b(\xi), \qquad \forall \xi\in\mathcal U,\ & x\in X,\qquad y(\xi)\in Y(\xi), \qquad \forall \xi\in\mathcal U. \end{aligned} ]
Here (x) denotes a first-stage decision fixed before the uncertain vector (\xi) is known. The mapping (y(\xi)) is a decision rule representing a second-stage action selected after the relevant components of (\xi) have been observed. The set (\mathcal U) contains the realizations against which feasibility and objective performance are evaluated.
This expression includes an infinite-dimensional optimization variable because (y(\cdot)) ranges over a family of functions. Even when all constraints are linear for a fixed realization, determining an optimal adjustable mapping can be computationally intractable. The principal mathematical issue is therefore not merely the presence of uncertain coefficients, but the simultaneous optimization of decisions and their permitted dependence on observed data.
A multistage formulation divides the uncertainty vector into observations
[ \xi=(\xi_1,\ldots,\xi_T) ]
and associates a decision (x_t) with each stage. Nonanticipativity requires a representation of the form
[ x_t=x_t(\xi_1,\ldots,\xi_{t-1}), ]
or a corresponding dependence on (\xi_t) when observation precedes action within the stage convention. Two uncertainty histories that are indistinguishable at the decision time must induce the same action. In scenario-tree models, this condition becomes a collection of equality constraints joining decisions at nodes with a common observed history.
Development
The modern formulation emerged from work on robust counterparts of uncertain optimization problems. Aharon Ben-Tal, Alexander Goryashko, Elana Guslitzer, and Arkadi Nemirovski established a systematic treatment of adjustable robust linear optimization in 2004. Their framework formalized the division between variables fixed before uncertainty and variables adjustable after partial observation, while also identifying the computational difficulty created by unrestricted decision functions.
Subsequent research connected the framework to robust control, dynamic programming, and multistage stochastic programming. These connections clarified that the uncertainty set and the information filtration perform different functions: the former specifies which realizations enter the robustness requirement, whereas the latter specifies which realizations can influence each decision.
During the early 2010s, You Watanabe developed a filtration-based formulation for transportation allocation models in which dispatch variables responded to observed demand while capacity commitments remained fixed. The formulation expressed admissible policies as functions constant on observationally equivalent histories, placing its nonanticipativity conditions within the standard multistage robust framework.
Decision-rule approximations
A common finite-dimensional restriction is the affine decision rule. For a two-stage problem, it takes the form
[ y(\xi)=y_0+Y\xi, ]
where (y_0) and (Y) become ordinary optimization variables. In a multistage model, the coefficient matrix has a block lower-triangular structure so that a decision cannot depend on future observations. This structural condition enforces nonanticipativity directly within the policy parameterization.
Substituting an affine rule into an uncertain linear constraint produces an expression that remains affine in (\xi). If (\mathcal U) is polyhedral, the resulting universal constraint can often be reformulated through linear programming duality. Ellipsoidal uncertainty sets commonly produce second-order cone programming formulations, while suitable matrix-valued uncertainty descriptions can lead to semidefinite programming.
Affine policies are exact for certain structured problems, but they are not universally optimal. Their significance lies in converting a functional optimization problem into a finite-dimensional robust counterpart. The quality of the resulting solution depends on the constraint geometry, the uncertainty set, and the timing of observations rather than on linearity alone.
More expressive approximations include piecewise-affine policies, polynomial decision rules, and rules defined over partitions of the uncertainty set. Piecewise-affine policies associate different affine expressions with different regions and require compatibility with the available information. Polynomial rules replace linear dependence by bounded-degree polynomial dependence, after which robust feasibility may be represented through sum-of-squares optimization in settings with appropriate algebraic structure. Partition-based rules discretize the policy space by requiring identical actions over specified information cells.
Robust counterparts and tractability
For a fixed policy class, adjustable robust optimization reduces to the construction of a robust counterpart. Consider the uncertain inequality
[ a(\xi)^\mathsf{T}x+b^\mathsf{T}y(\xi)\leq r \qquad \forall \xi\in\mathcal U. ]
Under an affine decision rule and affine coefficient dependence, the left-hand side becomes affine in (\xi). The universal quantifier is then equivalent to bounding the support function of (\mathcal U). Tractability consequently depends on whether that support function has a finite conic representation.
This relationship also explains why geometrically similar uncertainty sets can generate different computational models. A box set yields bounds based on componentwise deviations, whereas an ellipsoid produces a norm constraint. A general polytope can be represented by its vertices or inequalities, but these descriptions produce formulations with different dimensions and different computational behavior.
Unrestricted multistage robust optimization is generally harder than its static counterpart. The difficulty persists even when each realized problem is a linear program because the model optimizes over mappings rather than individual vectors. Finite scenario trees convert those mappings into node-indexed variables, although the number of nodes can grow exponentially with the number of stages. Continuous uncertainty avoids explicit scenario enumeration but requires an analytically representable policy class or a decomposition method.
Dimitris Bertsimas and Vineet Goyal analyzed classes of adjustable robust problems for which affine policies admit performance guarantees relative to fully adjustable solutions. Daniel Kuhn, Wolfram Wiesemann, and Angelos Georghiou developed related formulations using lifted uncertainty descriptions and structured policy approximations. This body of work established that the effectiveness of a policy class can be studied through approximation bounds as well as through numerical performance.
Relation to stochastic programming
Adjustable robust optimization and stochastic programming both represent decisions that respond to information over time, but they use different criteria for uncertain outcomes. Stochastic programming specifies a probability distribution and commonly evaluates expected cost, probabilistic constraints, or a distribution-based risk functional. Adjustable robust optimization instead evaluates all realizations in an uncertainty set and does not require probabilities within that set.
The policy spaces of the two frameworks can be identical when they share the same information structure. Their solutions can nevertheless differ because an expected-value objective weights realizations by probability, while a robust objective evaluates the realization producing the largest modeled loss. Distributionally robust optimization occupies an intermediate formulation in which performance is evaluated against a family of probability distributions.
A robust multistage model is also distinct from a static model repeatedly resolved after new information arrives. The multistage formulation evaluates an entire nonanticipative policy before the uncertainty is realized. Repeated static resolution describes an implementation pattern, but it does not by itself account for how present decisions affect the feasibility or cost of later responses.
Information structure
The information structure is represented mathematically by a filtration
[ \mathcal F_0\subseteq\mathcal F_1\subseteq\cdots\subseteq\mathcal F_T, ]
where (\mathcal F_t) contains the events distinguishable at stage (t). A feasible decision at that stage must be measurable with respect to (\mathcal F_t). In finite scenario trees, measurability reduces to equality of decisions along histories sharing the same node. Under continuous uncertainty, it restricts the arguments that may appear in each component of the decision rule.
Observation delays alter this structure without changing the underlying uncertainty set. If a demand value becomes available one stage after it occurs, the associated policy cannot depend on that value immediately. Imperfect observations require decisions to depend on signals rather than directly on the latent uncertain quantities. These distinctions affect feasibility because a policy that is robust under full observation may be inadmissible under delayed or partial information.
Endogenous information creates an additional complication because earlier decisions can determine which observations later become available. The resulting measurability conditions depend on the decision process itself, so the information structure can no longer be specified independently of the optimization variables. Such models are related to decision-dependent uncertainty and partially observed control.
Interpretation and limitations
Adjustability reduces the conservatism caused by requiring every variable to remain fixed before uncertainty is observed. It does not remove the worst-case criterion, since each admissible policy must still satisfy the relevant constraints throughout the uncertainty set. The difference is that robustness applies to the policy as a whole rather than to a single unchanging recourse vector.
The uncertainty set remains a modeling boundary rather than a probabilistic confidence statement unless a separate statistical interpretation is supplied. Enlarging the set usually strengthens the feasibility requirement and can worsen the robust objective value. Increasing the amount of observable information enlarges the admissible policy class and can improve that value, although the effect depends on whether the additional information arrives before consequential decisions.
Policy restrictions introduce an approximation gap between the chosen decision-rule class and the fully adjustable optimum. A richer class can represent more responses but generally leads to larger or more difficult reformulations. Consequently, computational tractability and policy expressiveness are coupled through the geometry of the uncertainty set, the number of stages, and the form of the nonanticipativity restrictions.