Recent Advances in Robust Optimization Aharon Ben-Tal MINERVA Optimization Center Technion – Israel Institute of Technology ♣ Robust Optimization is a methodology for processing uncertain optimization problems min {f (x, ζ) : F (x, ζ) ∈ K} x • x ∈ Rn is the decision vector • ζ ∈ Rd is the data (or data perturbation) • f (x, ζ) : Rn × Rd → R and F (x, ζ) : Rn × Rd → Rm are given functions, and K ⊂ Rm is a given set. f (·, ·), F (·, ·), K form the structure of the uncertain problem. ♣ In contrast to Stochastic Programming, RO does not assume stochastic nature of data ζ and uses instead uncertain-but-bounded uncertainty model: ζ runs through a given (typically, compact) uncertainty set Z ⊂ Rd. ♣ RO, people: • 1973: A.L. Soyster (LP) • 1997: P. Kouvelis & G. Yu (IP) L. El Ghaoui & H. Lebret & F. Oustry • 1997 –: (CP) A. Ben-Tal & A. Nemirovski • 2000 –: E. Adida, A. Atamturk, A. Beck, D. Bertsimas, C. Bhattacharyya, H.-G. Bock, S. Boyd, G. Calafiore, M. Diehl, Y. Eldar, E. Erdogan, L. Grate, E. Guslitzer, B. Golany, D. Goldfarb, C. Hol, G. Iyengar, M. Jordan, E. Kostina, O. Kostyukova, G. Lanckriet, A. Nilim, M. Sim, D. Pachamanova, C. Roos, C. Schrerer, A. Sood, A. Thiele, J.-Ph. Vial, M. Zhang,... ♠ RO, applications: • Structural/Circuit/Network Design • Control • Signal Processing • Machine Learning • Portfolio Optimization • Inventory... Example of uncertain LP: Multi-product inventory with backlogged demand and shared warehouse capacity C min C,xt ,yt ,wt ,vt s.t. • • • • PT 0 t=1 [ch yt [inventory management cost] + c0bwt + c0pvt] ≤ C [cost description] xt+1 = xt + vt − ζt [balance equations] −xt ≤ wt, 0 ≤ wt [bounds on backlogged demand] q 0 yt ≤ Q [warehouse capacity bound] xt ≤ y t , 0 ≤ y t [bounds on [xt]+] v t ≤ vt ≤ v t [bounds on orders] xt ∈ Rd: inventory state at time t • vt ∈ Rd: replenishment orders at time t • yt ∈ Rd: stored items at time t • wt ∈ Rd: backlogged demand at time t • • Uncertain data: demands q ∈ Rd+: storage coefficients co ∈ Rd+: ordering costs ch ∈ Rd+: holding costs cb ∈ Rd+: backlog penalty ζ = [ζ1; ...; ζT ] n o min {f (x, ζ) : F (x, ζ) ∈ K} : ζ ∈ Z x (Unc) Assume that our “decision environment” is such that • All decisions xj should be made before ζ “reveals itself ” and thus should be independent of ζ • The constraints are “hard”: their violations cannot be tolerated • We intend to take full care of all data ζ ∈ Z and do not care what happens when ζ 6∈ Z. Under these assumptions, seemingly the only meaningful way to process (Unc) is to solve the Robust Counterpart min {t : ∀ζ ∈ Z : f (x, ζ) ≤ t, F (x, ζ) ∈ K} t,x of the uncertain problem. (RC) Example: To build the RC of the Inventory problem, we use balance equations to eliminate the states and pass to the RC of the resulting inequality constrained problem, thus arriving at min C,yt ,wt ,vt s.t. C PT 0 0 0 t=1 [ch yt + cb wt + cp vt ] ≤ C P x1 + τt−1 =1 [vτ − ζτ ] ≤ yt , 0 ≤ yt Pt−1 −x1 − τ =1[xτ − ζτ ] ≤ wt, 0 ≤ v t ≤ vt ≤ v t , q 0 yt ≤ Q wt ∀ζ ∈ Z (RC) Note: When Z is a computationally tractable convex set, the semiinfinite problem (RC) is computationally tractable. E.g., when Z is polyhedral: Z = {ζ : ∃u : P ζ + Qu + r ≥ 0}, RC can be converted into an explicit LP program of sizes polynomial in T, d and the sizes of the representation of Z. • In dynamical decision-making, some of the decisions xj should be made when the actual data becomes partially known and thus can depend on the corresponding portions of the data Example: In the Inventory problem with uncertain demand, replenishment orders vt of day t usually can depend on the actual demands at days 1, ..., t − 1. ♣ To account for adjustability, we allow for every xj to depend on a prescribed portion Pj ζ of ζ: xj = Xj (Pj ζ), thus arriving at Adjustable Robust Counterpart min n {t : ∀ζ ∈ Z : f (X(ζ), ζ) ≤ t, F (X(ζ), ζ) ∈ K} t,{Xj (·)}j=1 [X(ζ) = {Xj (Pj ζ)}] (ARC) Note: ARC is infinite-dimensional and thus is typically heavily computationally intractable. Seemingly the only applicable technique is Dynamic Programming ⇒“curse of dimensionality” ♣ To overcome, to some extent, intractability of ARC, we restrict the decision rules to be affine: Xj (Pj ζ) = ξj0 + ξjT Pj ζ, thus arriving at the Affinely Adjustable Robust Counterpart min t,{ξj0 ,ξj }nj=1 {t : ∀ζ ∈ Z : f (X(ζ), ζ) ≤ t, F (X(ζ), ζ) ∈ K} [X(ζ) = {ξj0 + ξjT Pj ζ}nj=1] (AARC) Example: The only “actual decisions” in the Inventory problem are orders vt. Assume that vt can depend on the preceding demands ζ t−1 = [ζ1; ...; ζt−1]. To build the AARC, we • introduce linear decision rules for the orders vt = vt0 + Vtζ t−1 • make xt, yt, wt affine functions of ζ: xt = x0t + Xtζ, yt = yt0 + Ytζ, wt = wt0 + Wtζ, thus ending up with min P C,vt0 ,Vt ,...,wt0 ,Wt C 0 0 0 0 0 t−1 [c [y + Y ζ] + c [w + W ζ] + c [v + V ζ ]] ≤ C t t t p t b t t≤T h t 0 0 0 t−1 xt+1 + Xt+1ζ = xt + Xtζ + vt + Vtζ − ζt 0 0 0 s.t. xt + Xtζ ≤ yt + Ytζ, 0 ≤ yt + Ytζ ∀ζ ∈ Z −[x0t + Xtζ] ≤ wt0 + Wtζ, 0 ≤ wt0 + Wtζ 0 t−1 0 0 v t ≤ v t + Vt ζ ≤ v t, q [yt + Ytζ] ≤ Q (AARC) Note: The AARC of the Inventory problem is computationally tractable provided that Z is so. E.g., when Z is a polyhedral set, (AARC) is equivalent to an explicit LP program. Example (continued): Consider single-product Inventory with N = 10 and a box uncertainty set: (1 − ρ)ζ n ≤ ζ ≤ (1 + ρ)ζ n. Here the ARC is well within the grasp of Dynamic Programming. ♣ How large are the gaps in the chain Opt(ARC) ≤ Opt(AARC) ≤ Opt(RC) ? • We built a sample of 768 Inventory problems with uncertainty of 10% – 50% by picking at random cost coefficients, storage capacity and nominal demand trajectory ζ n and subsequent filtering out problems with infeasible ARC’s. ♠ It turns out that Opt(ARC) = Opt(AARC) in every one of these 768 problems! Note: This phenomenon disappears when passing from minimizing the worst-case inventory management cost to minimizing the average of this cost. . ♠ Opt(RC) was typically essentially worse than Opt(ARC) = Opt(AARC): Opt(RC) Range of Opt(ARC) 1 (1, 2] (2, 10] (10, 1000] ∞ Frequency in the sample 38% 23% 14% 11% 15% ♣ In the RO context, affine decision rules not necessarily are bad! . ♣ Robust Counterparts of uncertain problem are semi-infinite programs and thus can be intractable even when all instances of the uncertain problem are easy to solve. ⇒ When Robust Counterparts are computationally tractable? What to do if it is not the case? ♣ “Solvable case”: Uncertain LP Theorem. The RC/AARC of uncertain affinely perturbed LP problem n o T min cζ x + dζ : [aiζ ]T x + biζ ≥ 0, i = 1, ..., m : ζ ∈ Z x with fixed recourse is computationally tractable. With Z given by a strictly feasible LP/CQP/SDP representation, the RC/AARC is an explicit LP/CQP/SDP program of sizes polynomial in the size of instances and the size of the representation of the uncertainty set. Semi-Infinite Convex Quadratic Programming ♣ Tractability of a semi-infinite convex quadratically constrained program T T T T m min {c x : x A A x + 2b x + c ≤ 0 , ∀ (i = 1, ..., m, {A , b , c } i i i i i i i i=1 ∈ U) } x | {z } m 2Aix T 1 + ci + 2bi x ∈ L T 1 − ci − 2bi x reduces to tractability of a single semi-infinite convex quadratic constraint xT AT Ax + 2bT x + c ≤ 0 ∀(A, b, c) ∈ V ♣ Fact: (∗) can be NP-hard already for a simple polyhedral set V. ⇒ We need to look for tight tractable approximations of (∗). • What is “an approximation” ? • How to measure the quality of an approximation? 13 (∗) Definition. Consider a semi-infinite conic inequality ∀ζ ∈ Z : Aζ x + bζ ∈ K (C) with Aζ , bζ affine in ζ, and let Z, 0 ∈ Z, be convex. We embed (C) into the parametric family of semi-infinite conic inequalities ∀(ζ ∈ ρZ) : Aζ x + bζ ∈ K (Cρ) (ρ ≥ 0: uncertainty level), and let Xρ be the feasible set of (Cρ). A computationally tractable system of conic inequalities (e.g., a system of explicit LMIs) Pρx + Qρu + rρ ∈ M (Sρ) is a tight within factor ϑ ≥ 1 safe approximation of (Cρ), if the projection Xρ∗ of the feasible set of (Sρ) onto the space of x-variables satisfies Xϑρ ⊂ Xρ∗ ⊂ Xρ ∀ρ ≥ 0. Approximating Semi-Infinite Convex Quadratic Constraint with Ellipsoidal Uncertainty Theorem. [Ben-Tal, Nem., Roos ’02] Consider semi-infinite convex quadratic inequality xT AT Ax + 2bT x + c ≤ 0 ∀ (A, b, c) = (A∗, b∗, c∗) + ρ L X `=1 ζ`(A`, b`, c`) : ζ ∈ Z (SC[ρ]) where the perturbation set Z is an intersection of ellipsoids centered at the origin: ½ ¾ T Z = ζ : ζ Qj ζ ≤ 1, j = 1, ..., N Qj º 0, X j Qj  0 (SC[ρ]) admits an explicit ϑ-approximation, where ϑ is as follows: ♠ In the case N = 1 of simple ellipsoidal uncertainty, ϑ = 1; ♠ In the case of box uncertainty (N = dim ζ, ζ T Qj ζ = ζj2), ϑ = π2 ; √ ♠ In the general case, ϑ ≤ O(1) ln N . For example, LN ≤ 100, 000, 000 ⇒ ϑ ≤ 6.36. 21 AARC without fix-recourse a(ξ)Tx(ξ) ≤ b(ξ) ∀ ξ ∈ Uρ ⇒ sol. set Xρ Uρ = { ξ0 + W ξ | ||ξ ||2 ≤ ρ } • If Uρ = single ellipsoid ⇒ RC is SDP • If U =∩ L ellipsoid ⇒ we can build an explicit SDP which generates an approximation X̂ ρ of the robust feasible set Xρ (i.e. Xˆ ρ ⊂ X ρ) which is tight up to a factor θ = O(1) log L i.e. • (∗) X θρ ⊂ Xˆ ρ ⊂ X ρ If Uρ is a box then (*) holds with ρ=π/2 ♣ Extending the notion of RC: Globalized Robust Counterpart. min {t : f (x, ζ) ≤ t, F (x, ζ) ∈ Q} : ζ ∈ Z t,x (Unc) ♠ In some applications, it makes sense to modify our attitude to uncertainty, specifically, to replace the requirement Full responsibility for the constraints f (x, ζ) ≤ t and F (x, ζ) ∈ Q when ζ ∈ Z and no responsibility whatsoever when ζ 6∈ Z with Full responsibility for the constraints when ζ ∈ Z and controlled deterioration of the constraints when ζ 6∈ Z. Globalized Robust Counterpart Uncertain linear inequality (1) a(ξ)Tx ≤ b(ξ) ξ ∈ U ⊂ ℜk GRC (2) a(ξ)Tx – b(ξ) ≤ α dist(ξ, U) ∀ ξ ∈ ℜk α > 0. NOTE α → ∞ then GRC = RC i.e. (3) a(ξ)Tx – b(ξ) ≤ 0 ∀ξ∈U 1 ♣ Generic application: Affine control of uncertainty-affected Linear Dynamical Systems. ♠ Consider Linear Time-Varying Dynamical system xt+1 = Atxt + Btut + Rtdt yt = Ctxt x0 = z (S) • xt: state; • ut: control • yt: output; • dt: uncertain input; • z: initial state to be controlled over finite time horizon t = 0, 1, ..., T . ♠ Assume that a “desired behaviour” of the system is given by a system of convex inclusions Diw − bi ∈ Qi, i = 1, ..., m on the state-control trajectory w = (x0, x1, ..., xT +1, u0, u1, ..., uT ), and the goal of the control is to minimize a given linear objective f (w). 24 xt+1 = Atxt + Btut + Rtdt yt = Ctxt x0 = z ♠ Restricting ourselves with affine output-based control laws ut = ξt0 + t X τ =0 (S) Ξtτ yτ , (∗) the problem of interest is (!) Find an affine control law (∗) which ensures that the resulting statecontrol trajectory w satisfies the system of convex inclusions Diw − bi ∈ Qi, i = 1, ..., m and minimizes, under this restriction, a given linear objective f (w). Dynamics (S) makes w a known function of inputs d = (d0, d1, ..., dT ), the initial state z and the parameters ξ of the control law (∗): w = W (ξ; d, z). Consequently, (!) is the optimization problem min {f (W (ξ; d, z)) : DiW (ξ; d, z) − bi ∈ Qi, i = 1, ..., m} ξ 25 (U) xt+1 = Atxt + Btut + Rtdt open loop dynamics: yt = Ctxt x0 = z t control law: ut = ξt0 + P Ξtτ yτ τ =0 ⇓ w := (u0, ..., uT , x0, ..., xT +1) = W (ξ; d, z) ⇓ min {f (W (ξ; d, z)) : DiW (ξ; d, z) − bi ∈ Qi, i = 1, ..., m} ξ (U) Note: Due to presence of uncertain input trajectory d and possible uncertainty in the initial state, (U) is an uncertain problem. Difficulty: While linearity of the dynamics and the control law make W (ξ; d, z) linear in (d, z), the dependence of W (·, ·) on the parameters ξ = {ξt0, Ξtτ }0≤τ ≤t≤T of the control law is highly nonlinear ⇒ (U) is not a bi-affine problem, which makes inapplicable the theory we have developed. In fact, (U) seems to be intractable already when there is no uncertainty in d, z! 26 Remedy: suitable re-parameterization of affine control laws. ♣ Consider a closed loop system along with its model: closed loop system: model: xt+1 = Atxt + Btut+Rtdt xct+1 = Atxct + Btut yt = Ctxt yct = Ctxct x0 = z xc0 = 0 ut = Ut(y0, ..., yt) ♠ Observation: We can run the model in an on-line fashion, so that at time t, before the decision on ut should be made, we have in our disposal purified outputs vt = yt − yct. ♠ Fact I [Equivalence]: Every transformation (d, z) 7→ w which can be obtained from an affine control law based on outputs: ut = ξt0 + t X τ =0 Ξtτ yτ (∗) can be obtained from an affine control law based on purified outputs: ut = ηt0 + and vice versa. 28 t X τ =0 Htτ vτ (∗∗) system: model: xt+1 = Atxt + Btut+Rtdt xct+1 = Atxct + Btut yt = Ctxt yct = Ctxct x0 = z xc0 = 0 control law: vt = yt − yct t ut = ηt0 + P Htτ vτ (∗∗) (S) τ =0 ♠ Fact II [bi-affinity]: The state-control trajectory w = W (η; d, z) of (S) is affine in (d, z) when the parameters η = {ηt0, Htτ }0≤τ ≤t≤T of the control law (∗∗) are fixed, and is affine in η when (d, z) is fixed. 29 ♠ Corollary: With parameterization (∗∗) of affine control laws, the problem Find an affine control law (∗) which ensures that the resulting state-control trajectory w satisfies the system of convex inclusions Diw − bi ∈ Qi, i = 1, ..., m and minimizes, under this restriction, a given linear objective f (w). becomes an uncertain bi-affine optimization problem and as such can be processed via the CRC approach. In particular, in the case when Qi are one-dimensional, the CRC of the problem is computationally tractable, provided that the normal range U of (d, z) and the associated cone L are so. If U, L and the norms used to measure distances are polyhedral, CRC is just an explicit LP program. 30 Supply chain control – GRC implementation for control problems xtj=amount echelon j orders from j-1 at the beginning of period t Ytj =inventory level in echelon j at the end of period t zj =initial inventory level at echelon j dt =external demand at period t TL(j) =I(j) +M(j-1) +L(j) the delay between the time an order is placed and received in echelon j. TM(j) =I(j+1) +M(j) the delay between the time an order is placed and shipped 22 from echelon Supply chain control – GRC implementation for control problems Main objective : minimizing cost Sub objective: stabilizing the system Problem Characteristics: Finite horizon Multi echelon Delays Backlogging Demand must be satisfied and is uncertain 23 Supply chain control Eliminating the equalities recursively will give us a LP problem of the form we discussed. How do we control this system? What are the consequences of different types of control? 24 LV control Lets assume we take the control suggested by Love [Love,1979] using target inventory: Resulting in the LP problem: 25 ILV control We can further improve this method by making the reference inventory a decision variable rather than a constant. 26 GRC control Applying the GRC to the AARC problem assuming 29 Robust Counterpart (AARC) ytj = ytj(d, z) affine function xtj = xtj(d, z) constraints must hold ∀ d ∈ D, z ∈ Z CRC A typical constraint is of the form Fi(d, z) ∈ Ki (Ki = interval) Its CRC version being (∗) n m t =1 j =1 ( dist ( Fi (d , z ), K i ) ≤ ∑ α it dist (dt , Dt ) + ∑ α ij dist z j , Z j When Dt, Zj are polyhedral (*) can be converted to linear inequalities. ) The purified outputs corresponding to the dynamic system (1) – (3) are here ⎧ t −T M (m ) ⎪ z0m − d z if j = m ∑ ⎪ t =1 j ⎪ vt = ⎨ ⎪z j j<m ⎪ 0 ⎪⎩ The affine control law is here x,t , j m T x,t , j l xt = η0 + ∑ ∑ ητl vτ l =1τ =1 j where ητxl,t , j = 0 ∀τ ≥ t (non anticipativity) Example [Love, 1979], Oscillating demand: Horizon: n=20 Echelons: m=3 Cost: c=2, p=3,h=1 Initial inventory: z=12 Lead time: L=2 No other delays 30 Inventory Behavior – “amplification of oscillation” LV OFV: 4795 RC OFV: 1207 ILV OFV: 3140 AARC OFV: 1165 GRC OFV: 1065 31 Example - extended Assuming demand is uncertain: Dt=[4,10], Zj=[10,14]; All other data is the same. 50 simulations, uniform distribution: Same as assumed. Dt=[2,12], Zj=[8,16]; 33 Results COST\ deviation ratio Input Assumed LV ILV RC AARC GRC 5128 3310 1263 1131 1081 (597%) (348%) (73%) (62%) (48%) Wider than assumed 5430 3561 1405 1202 1114 (634%) (380%) (94%) (65%) (53%) Theoretical (worst case) No bound No bound 2137 1410 1628 35 Results – GRC characteristics 1 1 0.9 0.9 0.8 0.8 0.7 0.7 0.6 RC . GRC α0 GRC α1 GRC α2 GRC α3 GRC α 0.5 0.4 0.3 0.2 0 0.6 RC . GRC α0 GRC α1 GRC α2 GRC α3 GRC α4 0.5 0.4 0.3 0.2 4 0.1 0 probability probability Although restricting α worsens the theoretical objective the common behavior is improved. 0.1 0.2 0.4 0.6 0.8 R 1 1.2 1.4 1.6 0 0 0.2 0.4 0.6 0.8 R 1 1.2 1.4 1.6 38 Probabilistic guaranties via RO d (1) f 0 ( y ) + ∑ ξl fl ( y ) ≤ 0 l =1 Assumption ξ1, ξ2, . . . , ξd independent rv’s ξ l ∼ Pl ∈ P l *compact all prob. dist. in Pl has common support = [−1,1]. Def. A vector y satisfying, for a given 0 < ξ < 1: (2) Pr{ f0(y) + Σ ξl fl(y) ≤ 0 } ≥ 1 − ε provides a safe approximation of (1). Challenge Find uncertainty set for ξ, U s.t. the RC of (1): (3) f0(y) + Σ ξl fl(y) ≤ 0 ∀ ξ ∈ U is a safe approximation of (1), i.e. satisfies (2). Theorem U = B ∩ (M + E ) B = ξ ∈ ℜd ξ ∞ ≤ 1 { } (4) where M = {ξ μ − ≤ ξ ≤ μ + , l = 1,K d } l l l E = {ξ ∑ ξl2 σ l2 ≤ 2 log(1 ε )} μl− , μl+ and σ l are such that 2 σ Al ( z ) ≤ max μl− z , μl+ z + l zl2 , ∀l = 1,K d 2 ( ) where Al ( z ) = max log(∫ exp( zs )dPl (s )). Pl ∈Pl Also E can be replaced by a scaled E = {ξ ∑ ξl σ l ≤ 2d log(1 ε ).} Values of μl+ , σ l are explicitly known for various families Pl, e.g. supp(P ) ⊂ [− 1,1] ⎫ μl± = 0 ⎬ P unimodal and symmetric⎭σ l = 1 6 supp(P ) ⊂ [− 1,1]⎫ μ − = −1 2 , μ + = 1 2 l ⎬ l P unimodal ⎭ σ l = 1 24 Moreover, for the LP case (fl(y) affine) the RC of (3), with U as in the Theorem, is conic quadratic or LP. CASE I Information on ζ ∼ P ζ` ’s are independent rv’s, |ζ` | ≤ 1, E(ζ` ) = 0 Here the uncertainty set is U Ball = {ζ | kζk2 ≤ Ω} . The RC of the uncertain linear const. (1) is v u L uX Ωt [(a` )T x − b` ]2 ≤ b0 − (a0 )T x . `=1 This conic-quadratic constraint is a safe approximation of the CC for p all Ω ≥ 2 log(1/2) i.e. for such Ω n o X X ζ` (a` )T x > b0 + ζ` b` ≤ exp(−Ω2 /2) P r (a0 )T x + Discussion What if we ignore the stochastic information and just use |ζ` | ≤ 1? In this case, the CC coincide with the RC of the linear eq. with uncertainty U Box = {ζ | |ζi | ≤ 1, which is here Hence ` = 1, . . . , L} X (a` )T x − b` ≤ b0 − (ao )T x x feasible for (3) ⇒ CC is feasible with prob. 1. When using the stochastic information, the RC is qX 2 Ω [(a` )T x − b` ] ≤ b0 − (a0 )T x (3) (4) (5) which corresponds to U Ball , and we have x feasible for (4) ⇒ CC is feasible with prob. 1 − exp(−Ω2 /2) (For Ω = 7.44 1 − exp(−Ω2 /2) = 1 − 10−12 so (4) and (6) are indistinguishable!) (6) But, for large L Vol(U Box ) −→ ∞ Vol(U Ball ) superexponentially (ratio is > 1 starting with L = 237). For small L, we could use L U = U Box ∩ U Ball = ζ ∈ IR | kζk∞ ≤ 1, kζk2 ≤ Ω Here the RC is and we have P |z | + ΩpP w2 ≤ b0 − (a0 )T x ` ` z` + w` = b` = (a` )T x If x is a component of a feasible solution (x, z, w) of (7) =⇒ (7) CC is feasible with 2 prob. 1 − exp(−Ω /2) (8) Discussion With U = U Box ∩ U Ball , we get always (for all L) less conservative RC (incomparable so for Ω > 7 compared to U Box ) and yet guarantee the CC with prob. essen. 1. Striking phenomenon Consider the special case of P in Case I: P r(ζi = ±1) = 1/2 . Note that here kζk22 = L ; hence, if L > Ω2 , the set U does not contain even a single realization of ζ, and yet the CC holds with high probability. Conclusion The “immunization power” of the RC (7) cannot be explained by the fact that the underlying perturbation set U contains “nearly all” realizations of the random perturbation vector.