Robust optimization

Robust optimization is a field of mathematical optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the parameters of the problem itself and/or its solution. It is related to, but often distinguished from, probabilistic optimization methods such as chance-constrained optimization.

Robust optimization is a field of mathematical optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the parameters of the problem itself and/or its solution. It is related to, but often distinguished from, probabilistic optimization methods such as chance-constrained optimization. == Example 1== Consider the following linear programming problem \max_{x,y} \ \{3x + 2y\} \ \ \mathrm { subject \ to }\ \ x,y\ge 0; cx + dy \le 10, \forall (c,d)\in P where P is a given subset of \mathbb{R}^{2} . What makes this a 'robust optimization' problem is the \forall (c,d)\in P clause in the constraints. Its implication is that for a pair (x,y) to be admissible, the constraint cx + dy \le 10 must be satisfied by the worst (c,d)\in P pertaining to (x,y) , namely the pair (c,d)\in P that maximizes the value of cx + dy for the given value of (x,y) . If the parameter space P is finite (consisting of finitely many elements), then this robust optimization problem itself is a linear programming problem: for each (c,d)\in P there is a linear constraint cx + dy \le 10 . If P is not a finite set, then this problem is a linear semi-infinite programming problem, namely a linear programming problem with finitely many (2) decision variables and infinitely many constraints. \hat{\rho}(x,\hat{u}):= \max_{\rho\ge 0}\ \{\rho: u\in S(x), \forall u\in B(\rho,\hat{u})\} where \hat{u} denotes the nominal value of the parameter, B(\rho,\hat{u}) denotes a ball of radius \rho centered at \hat{u} and S(x) denotes the set of values of u that satisfy given stability/performance conditions associated with decision x . In words, the robustness (radius of stability) of decision x is the radius of the largest ball centered at \hat{u} all of whose elements satisfy the stability requirements imposed on x . The picture is this: where the rectangle U(x) represents the set of all the values u associated with decision x . ==== Example 2==== Consider the case where the objective is to satisfy a constraint g(x,u)\le b, . where x\in X denotes the decision variable and u is a parameter whose set of possible values in U . If there is no x\in X such that g(x,u)\le b,\forall u\in U , then the following intuitive measure of robustness suggests itself: \rho(x):= \max_{Y\subseteq U} \ \{size(Y): g(x,u)\le b, \forall u\in Y\} \ , \ x\in X where size(Y) denotes an appropriate measure of the "size" of set Y . For example, if U is a finite set, then size(Y) could be defined as the cardinality of set Y . In words, the robustness of decision is the size of the largest subset of U for which the constraint g(x,u)\le b is satisfied for each u in this set. An optimal decision is then a decision whose robustness is the largest. This yields the following robust optimization problem: \max_{x\in X, Y\subseteq U} \ \{size(Y): g(x,u) \le b, \forall u\in Y\} This intuitive notion of global robustness is not used often in practice because the robust optimization problems that it induces are usually (not always) very difficult to solve. ====Example 3==== Consider the robust optimization problem z(U):= \max_{x\in X}\ \{f(x): g(x,u)\le b, \forall u\in U\} where g is a real-valued function on X\times U , and assume that there is no feasible solution to this problem because the robustness constraint g(x,u)\le b, \forall u\in U is too demanding. To overcome this difficulty, let \mathcal{N} be a relatively small subset of U representing "normal" values of u and consider the following robust optimization problem: z(\mathcal{N}):= \max_{x\in X}\ \{f(x): g(x,u)\le b, \forall u\in \mathcal{N}\} Since \mathcal{N} is much smaller than U , its optimal solution may not perform well on a large portion of U and therefore may not be robust against the variability of u over U . One way to fix this difficulty is to relax the constraint g(x,u)\le b for values of u outside the set \mathcal{N} in a controlled manner so that larger violations are allowed as the distance of u from \mathcal{N} increases. For instance, consider the relaxed robustness constraint g(x,u) \le b + \beta \cdot dist(u,\mathcal{N}) \ , \ \forall u\in U where \beta \ge 0 is a control parameter and dist(u,\mathcal{N}) denotes the distance of u from \mathcal{N} . Thus, for \beta =0 the relaxed robustness constraint reduces back to the original robustness constraint. This yields the following (relaxed) robust optimization problem: z(\mathcal{N},U):= \max_{x\in X}\ \{f(x): g(x,u)\le b + \beta \cdot dist(u,\mathcal{N}) \ , \ \forall u\in U\} The function dist is defined in such a manner that dist(u,\mathcal{N})\ge 0,\forall u\in U and dist(u,\mathcal{N})= 0,\forall u\in \mathcal{N} and therefore the optimal solution to the relaxed problem satisfies the original constraint g(x,u)\le b for all values of u in \mathcal{N} . It also satisfies the relaxed constraint g(x,u)\le b + \beta \cdot dist(u,\mathcal{N}) outside \mathcal{N} . ===Non-probabilistic robust optimization models=== The dominating paradigm in this area of robust optimization is Wald's maximin model, namely \max_{x\in X}\min_{u\in U(x)} f(x,u) where the \max represents the decision maker, the \min represents Nature, namely uncertainty, X represents the decision space and U(x) denotes the set of possible values of u associated with decision x . This is the classic format of the generic model, and is often referred to as minimax or maximin optimization problem. The non-probabilistic (deterministic) model has been and is being extensively used for robust optimization especially in the field of signal processing. The equivalent mathematical programming (MP) of the classic format above is \max_{x\in X,v\in \mathbb{R}} \ \{v: v\le f(x,u), \forall u\in U(x)\} Constraints can be incorporated explicitly in these models. The generic constrained classic format is \max_{x\in X}\min_{u\in U(x)} \ \{f(x,u): g(x,u)\le b,\forall u\in U(x)\} The equivalent constrained MP format is defined as: \max_{x\in X,v\in \mathbb{R}} \ \{v: v\le f(x,u), g(x,u)\le b, \forall u\in U(x)\} ===Probabilistically robust optimization models=== These models quantify the uncertainty in the "true" value of the parameter of interest by probability distribution functions. They have been traditionally classified as stochastic programming and stochastic optimization models. Recently, probabilistically robust optimization has gained popularity by the introduction of rigorous theories such as scenario optimization able to quantify the robustness level of solutions obtained by randomization. These methods are also relevant to data-driven optimization methods. ===Robust counterpart=== The solution method to many robust program involves creating a deterministic equivalent, called the robust counterpart. The practical difficulty of a robust program depends on if its robust counterpart is computationally tractable. ==External links== ROME: Robust Optimization Made Easy Robust Decision-Making Under Severe Uncertainty Robustimizer: Robust optimization software

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374109149 under CC BY-SA 4.0; modifications have been made.