A unified approach to inverse robust optimization problems

Berthold, Holger; Heller, Till; Seidel, Tobias Article — Published Version A unified approach to inverse robust optimization problems Mathematical Methods of Operations Research Provided in Cooperation with: Springer Nature Suggested Citation: Berthold, Holger; Heller, Till; Seidel, Tobias (2024) : A unified approach to inverse robust optimization problems, Mathematical Methods of Operations Research, ISSN 1432-5217, Springer, Berlin, Heidelberg, Vol. 99, Iss. 1, pp. 115-139, https://doi.org/10.1007/s00186-023-00844-x This Version is available at: https://hdl.handle.net/10419/314962 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Mathematical Methods of Operations Research (2024) 99:115–139 https://doi.org/10.1007/s00186-023-00844-x ORIGINAL ARTICLE A unified approach to inverse robust optimization problems Holger Berthold1·Till Heller1·Tobias Seidel1 Received: 25 March 2023 / Revised: 18 November 2023 / Accepted: 20 November 2023 / Published online: 22 February 2024 © The Author(s) 2024 Abstract A variety of approaches has been developed to deal with uncertain optimization problems. Often, they start with a given set of uncertainties and then try to minimize the influence of these uncertainties. The reverse view is to first set a budget for the price one is willing to pay and then find the most robust solution. In this article, we aim to unify these inverse approaches to robustness. We provide a general problem definition and a proof of the existence of its solution. We study properties of this solution such as closedness, convexity, and boundedness. We also provide a comparison with existing robustness concepts such as the stability radius, the resilience radius, and the robust feasibility radius. We show that the general definition unifies these approaches. We conclude with an example that demonstrates the flexibility of the introduced concept. Keywords Robust optimization ·Uncertainty sets ·Non-linear optimization ·Price of robustness ·GSIP 1 Introduction In many real-world problems, one does not know exactly the input data of a formulated optimization problem. This may be due to the fact that we are working with forecasts, predictions, or simply unavailable information. To cope with this, it is essential to treat the given data as uncertain. In principle, there are two different ways to treat uncertainty. Either one knows some distribution of the uncertainty, or not. In the first case, this information can be used for the mathematical optimization problem, while in BTobias Seidel [email protected].de Holger Berthold holger[email protected].de Till Heller [email protected].de 1Department Optimization, Fraunhofer Institute for Industrial Mathematics ITWM, Fraunhoferplatz 1, 67655 Kaiserslautern, Germany 123 116 H. Berthold et al. the second case, no additional information is given. Both approaches are widely used in many real-world applications, such as energy management, finance, scheduling, and supply chain management. For a detailed overview of possible applications of robust optimization, we refer to Bertsimas et al. (2011). In this article, we focus mainly on problems without information about the distribution of uncertainty. Fixing the uncertain scenario to solve the corresponding optimization problem may yield a solution that is infeasible for other scenarios of the uncertainty set. Therefore, one tries to find solutions that are feasible for all possible scenarios of the uncertainty set. The problem of finding an optimal solution, i.e. the solution with the best objective function value, among these feasible solutions is called the robust counterpart (cf. BenTal et al. 2009). There are many surveys on robust optimization, such as Ben-Tal et al. (2009)or Bertsimas et al. (2011). For tractability reasons, the focus is often limited to robust linear or robust conic optimization. Robust optimization in the context of semi-infinite optimization can be found, for instance, in Goberna et al. (2013), while López and Still (2007); Vázquez et al. (2008); Stein (2012); Stein and Still (2003) consider general solution methods. For applications and results on robust nonlinear optimization, we refer to a survey by Leyffer et al. (2020). The question of how to construct a suitable uncertainty set is essential for realworld applications. This has been addressed, for example, in Bertsimas et al. (2004) and Bertsimas and Brown (2009). However, the exact size of the uncertainty set is often difficult to determine in practice (cf. Gorissen et al. 2015). Nevertheless, this choice has a great influence on the actual solution (see, for example, Bertsimas and Sim 2004; Chassein and Goerigk 2018a,b). A closely related question is which subset of the uncertainty set is covered by a given solution. Considering a larger uncertainty set may lead to overly conservative solutions, since more and more scenarios have to be considered. This trade-off between the probability of violation and the effect on the objective function value of the nominal problem is called the price of robustness and was introduced by Bertsimas and Sim (2004). Many robust concepts that have been formulated and analyzed in recent years try to deal with the price of robustness in order to avoid or reduce it. Bertsimas and Sim (2003,2004) defined the Gamma robustness approach, where the uncertainty set is reduced by cutting out less likely scenarios. The concept of light robustness was first defined by Fischetti and Monaci (2009) and later generalized by Schöbel (2014). Given a tolerable loss for the optimal value of the nominal solution, one tries to minimize the grade of infeasibility over all scenarios of the uncertainty set. Another approach to try to avoid overly conservative solutions is to allow a second stage decision. Ben-Tal et al. (2004) introduced the idea of adjustable robustness, where the set of variables is divided into here-and-now variables and wait-and-see variables. While the former need to be chosen before the uncertainty is revealed, the latter need to be chosen only after the realization is known. For a survey on adjustable optimization, we refer to Yanıko˘glu et al. (2019). In this article, we pursue a different approach to address the price of robustness, whichwecallinverse robustness. The main idea is to reverse the perspective of the approaches described above. Instead of finding a solution that minimizes (or maximizes) the objective function under a given set of uncertainties, we want to find a 123 A unified approach to inverse robust optimization problems 117 solution that maximizes, for example, the size of the considered set of uncertainties respecting a bound on the objective function. In this way, we are not dependent on the a priori choice of the uncertainty set and then accepting the loss of objective value. Instead, we can set the price we are willing to pay and then find the most robust solution with this given budget. Furthermore, the study of the above approaches is often limited to the robust linear case. We want to define inverse robustness in a more general way and study the concept also for nonlinear problems. Our approach is related to the inverse perspective to robust optimization introduced by Chassein and Goerigk (2018a)). They considered a generalization of robust optimization problems where only the shape of the uncertainty set is given, but not its actual size. Later, they extended their results to finding a solution that performs well on average over different uncertainty set sizes (cf. Chassein and Goerigk 2018b). Especially for the linear case, concepts have been introduced to measure the robustness of a given solution. The stability radius and resilience radius of a solution can be seen as measures for a fixed solution of how much the uncertain data can deviate from a nominal value while still being an (almost) optimal solution. For a more detailed discussion of resilience we refer to Weiß (2016). Both concepts can be seen as properties of a given solution, and the shape of the uncertainty set must be specified in advance. A similar concept has been studied in the area of facility location problems. Labbé presented in Labbé et al. (1991) an approach to compute the sensitivity of a facility location problem. Several publications (Carrizosa and Nickel 2003; Carrizosa et al. 2015; Ciligot-Travain and Traoré 2014; Blanquero et al. 2011) investigate the question of how to find a solution that is least sensitive, and thus deal with a concept quite similar to resilience. We will show that finding a point that maximizes the stability radius or the resilience radius, given a budget on the objective, can be seen as a special case of inverse robust optimization. However, the general definition of inverse robustness provides more flexibility. First, it allows to define measures that can include distributional information about the uncertainty. Second, the shape of the considered uncertainty is not restricted to given shapes, but can be more complex. The outline of the article is as follows. In Sect.2we define the inverse robust optimization problem (IROP) and discuss properties of this approach using two examples. In the next section we investigate the existence and structural properties of the solutions to the inverse robust optimization problem. In Sect. 4we discuss different possible choices and descriptions for the cover space that contains all potential uncertainty sets. Afterwards, we compare our general definition with other inverse robustness concepts in Sect.5. In Sect.6we provide and discuss an extended example. Finally, we conclude the article with a brief outlook. 2 The inverse robust optimization problem In this article, we consider parametric optimization problems given by (Pu)min x∈X⊆Rnf(x,u)(1) s.t. g(x,u)≤0, 123 118 H. Berthold et al. depending on an uncertain parameter u∈Rm. We assume that f(·,u), g(·,u):X→ Rare at least continuous functions w.r.t. xfor some fixed parameter u, which is also called scenario, belonging to an uncertainty set U ⊆Rm.ThesetX⊆Rnis given by further restrictions on xthat do not depend on u. For simplicity, we consider only one constraint that depends on the uncertain parameter u. However, the following results generalize to multiple constraints by considering their maximum. We assume that there is a special scenario ¯u∈Ucalled nominal scenario. This could be the average of the scenarios, or the most likely scenario. The nominal problem (P¯u)is defined as follows: (P¯u)f∗:= min x∈Xf(x,¯u) s.t. g(x,¯u)≤0. We call the objective function value of the optimization problem for the nominal scenario above the nominal objective value and denote it as f∗. Throughout this article we assume that at least the nominal problem has a feasible solution and the nominal objective value f∗is well-defined. The idea of the inverse robust optimization problem (IROP) is to allow a nonnegative deviation ≥0 from the nominal objective value in order to cover the uncertainty set Uas much as possible. We refer to the deviation as the budget. The task to cover Uas much as possible needs a more precise interpretation. For this, we define a cover space W⊆2Uand a merit function V :W→Rwhich maps every subset of Uto a value in R. With this, we obtain an instance of the IROP as follows: (PIROP)max x∈X,W∈WV(W)(2) s.t. f(x,u)≤f∗+∀u∈W,(3) g(x,u)≤0∀u∈W,(4) u∈W.(5) We call the constraint (3)thebudget constraint and the constraints (4)thefeasibility constraint of the IROP. Depending on the uncertainty set U, it may be possible to choose a budget such that the entire uncertainty set can be covered. This case is rather uninteresting, since the budget constraint becomes irrelevant. We will mostly focus on the case where it is a limiting constraint, and given a budget , we cannot cover the entire uncertainty set U. The idea in inverse robustness is to choose a large uncertainty set Ujust as a ground set for the uncertainty. The actual uncertainty set Wcovered is determined by the optimization problem and depends on the chosen budget . Please note that it is a non-trivial task to define a merit function Vand a cover space W, since the optimal solution and the tractability depend on it. A bad choice can even lead to an ill-posed problem due to Vitali’s theorem (cf. Halmos 1950). However, this should not be seen as a drawback. These two objects make the definition of an inverse robust optimization problem very general. The merit function can be simply the volume, but can also contain information about the distribution of the uncertain 123 A unified approach to inverse robust optimization problems 119 parameter u. The cover space can either consist of sets with a concrete shape, such as ellipses or boxes, or it can also be a generic set system like a σ-algebra. In Sect.4we will discuss some concrete choices of the cover space. In Sect.3we are going to show some general statements about the existence and shape of solutions for (PIROP). One property we want to emphasize here, is that the existence of a feasible solution is relatively easy to guarantee. As long as {¯u}∈W, there is a feasible solution, as we assumed that the nominal problem is well-defined. Before turning to the theoretical investigation of the inverse robust optimization problem, we present two examples that show properties of the problem and the difference to the classical robust counterpart. 2.1 Dependency on budget The first example illustrates that the solution of an inverse robust optimization problem does not depend on the choice of the uncertainty set Uin general, but instead on the available budget ≥0. To this end, we focus on the following parametric optimization problem (Pu)min x∈[0,2]x+u2 s.t. −x+u≤0, where we consider a parameterized uncertainty set U(a)=[0,a]with a≥1. Choosing u=0 leads to the nominal solution f∗=0. The corresponding inverse robust optimization problem with W={[0,d],d∈ [0,a]} and the merit function V(W)=vol(W)has the form (PIROP)max x∈[0,2],d∈[0,a]d s.t. x+u2≤∀u∈[0,d], −x+u≤0∀u∈[0,d]. As we will see later, due to Lemmas 3.5–3.7, considering the cover space B(U(a)) would lead to an equivalent problem. The inverse robust optimization problem has the solution x∗=d∗= min −1 2+1 4+,2,a. If we choose a large parameter aor a small budget , this solution is independent of the uncertainty set parameter a≥1 and thus allows modeling mistakes in the specification of U. On the contrary, the corresponding strict robust optimization problem 123 120 H. Berthold et al. min x∈[0,2]max u∈[0,a]x+u2 s.t. max u∈[0,a]−x+u≤0 has the solution x∗(a)=aand f∗(a)=a2+afor a∈[1,2]and no solution for a>2. This dependence makes it in classical robust optimization crucial to think about the specification of Ubeforehand, whereas in inverse robust optimization a solution always exists. 2.2 Extreme scenarios In the next example we want to study the effect of extreme scenarios that can occur especially in nonlinear optimization. We consider for u∈[0,1]the following parameterized optimization problem min x∈[0,1]x s.t. x≥u100. If we consider the nominal scenario u=0, then the nominal objective value f∗=0, we receive for chosen budget ≥0 and the same cover space as before the following inverse robust optimization problem: max x∈[0,1],d∈[0,1]d s.t. x≤, x≥u100 ∀u∈[0,d]. The optimal solution is given by x∗=min{, 1}and d∗=min{1 100 ,1}.Onthe other hand, choosing an uncertainty set U=[0,a]with a∈[0,1]before solving the classical robust counterpart min x∈[0,1]x s.t. x≥u100 ∀u∈[0,a] leads to the optimal solution x∗=a100. A very conservative choice in classical robust optimization would be to choose a=1 which would also lead to a high price for robustness and x∗=1 as optimal robust solution. In inverse robustness we would first choose a budget , for example =0.1. The price of robustness we would pay is fixed. The maximal uncertainty set we can cover with this budget has a size of d∗=0.11/100 ≈0.977. This means that 123 A unified approach to inverse robust optimization problems 121 we only need to pay a price of 0.1, but cover more than 95% of the area of the original uncertainty set. Choosing a smaller a priori set with a=0.5 leads to a very small price to pay to achieve robustness, 1 2100 . However, if one is ready to pay more for robustness, e.g. =0.001 one can cover more than 90% of the area of the original uncertainty set, which is a large part of all scenarios. The reason for this phenomenon is that u=1 is, for this problem, an extreme scenario. Covering it has a high price in optimality. In the inverse robust formulation we tend to leave out extreme scenarios and try to find a good solution on the remainder. These first two examples show two differences to a robust counterpart. First, the solution depends directly on the price we are willing to pay to achieve robustness and not on the a priori choice of the uncertainty set. Second, the inverse robust optimization will leave out extreme scenarios, making it a less conservative approach for robust optimization. 3 Existence and structure of solutions After the formal introduction and two motivational examples, this section is devoted to properties of the solutions of the problems. We are first especially interested in the existence of a solution and then give some statements about structural properties of the solution. To illustrate that the solution does not always have to exist, we start with a simple example. We consider for an uncertain scenario u∈R2the following optimization problem: min x∈[0,∞)x+u1. If we choose as a nominal scenario ¯u=0, then the optimal solution is given by ¯x=0. As a cover space Wwe consider unit balls with an arbitrary norm W:= {W(p,d):= {u∈R2|up≤d},p∈N,d∈[0,∞)} and as merit function the volume V(W):= vol(W). If we now allow for a budget >0, we receive the following inverse robust optimization problem max x∈[0,∞),p∈N,d∈[0,∞)d s.t. x+u1≤∀u∈W(p,d). All feasible solutions have a volume strictly less than 2. The sequence (0,W(k,)) k∈N is feasible for the inverse robust optimization problem and vol(W(k,))is monotonically increasing and converges towards 2. This means that in this simple example no optimal solution exists. For this example, the main issue for existence is the choice of the cover space Wand not the optimization variables. After this negative example we now introduce statements that ensure the existence of a solution. Motivated by the above example, we make for the next statements some 123 122 H. Berthold et al. basic assumptions about the cover space Wand the merit function. Given a compact subset C⊆U, we denote the set of all compact subsets of Cby K(C). Assumption 3.1 We assume that the cover space Wsatisfies the following conditions: 1. For any W∈W, we know that W∈W, where Wdenotes the closure of W. 2. K(C)∩Wis complete with respect to the Hausdorff-metric dHfor any compact subset C⊆U. 3. {u}∈W. In the following we let ˜ W:=K(U)∩W. Note that, if Uis itself compact, it suffices to check the second condition in Assumption 3.1 for C=U. Assumption 3.2 Given a cover space W⊆2U, we assume that the objective function V:W→Rsatisfies the following conditions: 1. V:˜ W→Ris upper semi-continuous w.r.t. the topology induced by the Hausdorff-metric and 2. V(W1)≤V(W2)for all W1,W2∈Wwith W1⊆W2. In the remainder of this section we study how the structure of the parametric problem (Pu)influences an optimal chosen set W∗∈W. We start with a theorem that ensures the existence of a solution of (PIROP). Theorem 3.3 Given a compact uncertainty set U ⊆Rm, two continuous functions f ,g:X×U→Rw.r.t. (x,u)∈X×U, a compact set X ⊆Rn, a cover space W⊆2Uand a merit function V which fulfill Assumptions 3.1 and 3.2. Then there exists a maximizer (x∗,W∗)∈X×Wof (PIROP), where W ∗is a compact set. Proof First we show that if a solution exists, then the corresponding solution set W∗is a compact set. Let Wbe the closure of a set W∈W. Because of Assumption 3.1,we know that W∈Wholds. Due to the continuity of f,gw.r.t. uwe can also conclude that for any feasible (x,W)∈F, where F:={(x,W)∈X×W:f(x,u)≤f∗+∀u∈W, g(x,u)≤0∀u∈W,¯u∈W} holds, also (x,W)∈Fis feasible. Since we assumed that V(W1)≤V(W2)for any W1,W2∈Wwith W1⊆W2, we can reduce the search space of the original optimization problem to the space of closed elements of the cover space W.Asthe uncertainty set Uwas assumed to be compact, we reduce the search space to the space of compact elements of the cover space which is by definition ˜ W. In a second step, we show that the feasible set ˜ F:={(x,W)∈Xט W:f(x,u)≤f∗+∀u∈W, g(x,u)≤0∀u∈W,¯u∈W} 123 A unified approach to inverse robust optimization problems 129 Let ¯x∈Rndenote an optimal solution to a parameterized optimization problem with fixed parameter ¯u∈Uof the form min x∈Xf(x,¯u), where the set of feasible solutions is denoted by X⊆Rn. The solution ¯xis called stable if there exists a ρ>0 such that ¯xis -optimal, i.e. f(¯x,u)≤f(x,u)+for all feasible solutions x∈Xwith an ≥0, for all uncertainty scenarios u∈Bρ(¯u).The stability radius is given as the largest such value ρ. Altogether, it can be calculated for a given solution ¯x∈Xand a budget ≥0by (PSR)max ρ≥0ρ s.t. f(¯x,u)≤f(x,u)+∀x∈X,∀u∈Bρ(¯u). To compare this concept with the concept of inverse robustness, we let the uncertainty set be U:=Rmand define W:={W(d):=Bd(¯u)|d:=[0,∞)}. Instead of considering the volume vol(W(d)) we can simply consider the radius as merit function V(W(d)) =d. Further, we consider the so called regret (see e.g. Inuiguchi and Sakawa 1995). For a scenario u∈Ulet f∗(u):= minx∈Xf(x,u). If we now consider as an objective function f(x,u)−f∗(u)and consider an budget >0 then we obtain the following inverse robust optimization problem: (PIROP,SR)max x∈X,d≥0d s.t. f(x,u)−f∗(u)≤∀u∈W(d). The difference to the problem (PSR)is that we no longer consider a fixed point ¯x, but allow the problem to find a point such that the regret is minimal. If we denote the optimal solution of (PSR)by ρ∗and the optimal solution of (PIROP,SR)by x∗,d∗we obtain the following inequality: ρ∗≤d∗. To obtain an equality one could replace the feasible set Xby a set containing only the nominal solution ¯x. In this case we can exactly model the problem (PSR)as an inverse robust optimization problem. While the stability radius compares a fixed decision ¯xwith all other feasible choices x∈X,theresilience radius allows to change the former optimal decision to gain feasibility. For an introduction into this topic we also recommend (Weiß 2016). Given a budget w.r.t.the objective value, the resilience radius searches the biggest ball centered at a given uncertainty scenario that satisfies feasibility with respect to the original problem. If we denote the optimal solution of a parameterized optimization problem with fixed parameter ¯uagain by ¯x, then ¯xis called B-feasible for some budget B∈R and some scenario u∈Uif f(¯x,u)is lower than B. Then, the resilience ball of a B-feasible solution ¯xaround a fixed scenario ¯u∈U is defined as the largest radius ρ≥0 such that ¯xis B-feasible for all scenarios in 123 130 H. Berthold et al. this ball. Finally the resilience radius is the biggest radius of a resilience ball around some x∈Xand can be calculated by solving the following optimization problem: max x∈X,ρ≥0ρ s.t. f(x,u)≤B∀u∈Bρ(¯u). Letting as above W:={W(d):=Bd(¯u)|d:=[0,∞)}and V(W(d)) =d, the problem is directly equivalent to the following inverse robust optimization problem: max x∈X,d≥0d s.t. f(x,u)≤f(¯x,¯u)+∀u∈W(d), where :=B−f(¯x,¯u). 5.2 Radius of robust feasibility The radius of robust feasibility is a measure on the maximal ’size’ of an uncertainty set under which one can ensure the feasibility of the given optimization problem. It is discussed for example in the context of convex programs (Goberna et al. 2016), linear conic programs (Goberna et al. 2021) and mixed-integer programs (Liers et al. 2021). For a recent survey on the radius of robust feasibility, we refer to Goberna et al. (2022). The radius of robust feasibility ρRFF is defined as ρRFF:= sup{α≥0:(PRα)is feasible}, where (PRα)min x∈Rncx s.t. Ax ≤b∀(A,b)∈Uα, with Uα:=(¯ A,¯ b)+αZfor nominal values ¯ A∈Rm×n,¯ b∈Rmand Zbeing a compact and convex set. Since we are only interested in the feasibility of (PRα), we can replace its objective function by 0. Therefore, given a fixed, convex, compact set Zwe can compute the radius of robust feasibility by solving the following optimization problem: ρRFF := sup x∈Rn,α≥0 α s.t. Ax ≤b∀(A,b)∈Uα, with Uα:=(¯ A,¯ b)+αZ. To compare this concept to the concept of inverse robustness, we define W(d):= ¯u+dZ as subsets of U:=Rmn+mcharacterized by d∈ 123 A unified approach to inverse robust optimization problems 131 D:=[0,∞). Furthermore we let W:={W(d)|d∈[0,∞)}and use the merit function V(W(d)):=d. Since we do not consider an objective function, we drop the budget constraint (or have the always satisfied constrained 0 ≤0+). Thus, given a nominal scenario ¯u:=(¯ A,¯ b)∈Uand a function g(x,(A,b)):=Ax −b, we obtain the inverse robust problem sup x∈Rn,d≥0 d s.t. Ax ≤b∀(A,b)∈W(d). We see that this way to calculate the radius of robust feasibility can be interpreted as a special inverse robust optimization problem, where we are searching for sets of the form ¯u+αZand where we are not interested in the budget constraint. The radius of robust feasibility allows us to analyze problems without any pre-defined values such as the given budget ≥0 or the nominal solution f∗. But, the certain structure of the set Zis rather restrictive and we do not know how the objective value of a solution x with a large radius αdeviates from the nominal solution value. 6 A bi-criteria problem We have seen that some already existing concepts can be interpreted as specific inverse robust problems, such as the resilience radius and the radius of feasible stability. On the one hand, the concept of inverse robustness unites these approaches into a bigger framework allowing questions to be answered in a more generic context. On the other hand, new problem formulations arise easily as we will see in this final example. To this end, we consider a bi-criteria optimization problem with an inequality constraint as the original problem. We assume that both objectives as well as the constraint are influenced by an uncertainty for which we have distributional information. In detail, we focus on the problem min x∈R{f1(x,u):= − x+u,f2(x,u):=2x−u} s.t. g(x,u):=x(u−1)+exp(u)−1≤0. Please note that the constraint is linear with respect to the decision parameter x∈R, but nonlinear in the uncertainty u∈U, such that a solution for a nominal scenario can be easily computed, while the analysis of the behavior with respect to the uncertainty is not trivial. Fixing the nominal scenario u=0, we can compute the Pareto-front F∗ as F∗={t(−1,2),t≥0}. After considering the original problem using a fixed nominal scenario, we now state the inverse robust problem. We allow a generic budget =(1, 2)∈R2 ≥0and fix a point on the Pareto-front, i.e. f∗=(−2,4)∈F∗. 123 132 H. Berthold et al. Additionally, we assume that our uncertainty is given by a normal-distributed random variable u∼N(0,1). Consequently, we focus on the cover space W=B(R), where B(R)denotes the σ-algebra of Borel-measurable sets of R. We want to maximize the probability of uncertainties we can handle while not losing more than from our solution f∗, which leads to: sup x∈R,W∈B(R) P(u∈W) s.t. f1(x,u)≤f∗ 1+1∀u∈W, f2(x,u)≤f∗ 2+2∀u∈W, g(x,u)≤0∀u∈W, 0∈W. As this formulation is numerically challenging, we use the statements from Sect. 2 to reformulate it. Although all statements are formulated for only one objective, it is easy to check that they carry over to the case of multiple objectives and can be used to investigate the present example. As f1is increasing and f2is decreasing w.r.t.x, we can substitute X=Rby a compact interval ˜ Xdepending on the budget . According to Theorem 3.4 then an optimal solution (x∗,W∗)exists and we can replace the supremum of the last problem by a maximum. As B(R)is too large as a search space, we substitute it by the set of intervals W(d):=[d1,d2]defined by elements of the design space D:={d∈R2d1≤d2}. Since f1(x,·), f2(x,·), g(x,·)are convex functions w.r.t. u∈Rfor any x∈R, we can use Lemma 3.5. As the describing functions f1,f2,gare continuous w.r.t. uwe can use Lemma 3.6 and by Lemma 3.7 we focus on a bounded solution set as h(x,u)=max{f1(x,u), f2(x,u), g(x,u)}is a coercive function w.r.t. ufor any arbitrary x∈R. Consequently, the choice of designs W(d)=[d1,d2],d1,d2∈R to search for a convex, closed, bounded set in Ris appropriate and leads to the same solution as considering all W∈B(R). We collect this simplification in the following proposition a proof is given in the Appendix. Proposition 6.1 (Reduced problem reformulation) The inverse robust example problem can be simplified to the reduced inverse robust example problem given as: (Pred)max x∈R,d1,d2∈R2 P(u≤d2)−P(u≤d1) s.t. −x+d2≤−2+1, 2x−d1≤4+2, x(d2−1)+exp(d2)−1≤0, d1≤0, 0≤d2≤1, 0≤x. 123 A unified approach to inverse robust optimization problems 133 Fig. 1 Optimal objective value V(W∗)for different values 1, 2≥0 Furthermore, this problem is a convex optimization problem w.r.t. (x,d)∈X×D and has a solution for all ∈R2 ≥0. The solutions corresponding to the budgets i∈{0,0.5,1,...,5},i=1,2are visualized in Fig.1where the optimal objective values of (Pred)are shown. We see that without budget (meaning 1=2=0) the solution does not allow any uncertainty, i.e. W(d∗)={0}. If we allow to differ from the nominal values f∗ 1or f∗ 2, we gain more robustness by increasing 1at first. For each 2there is an  1such that for 1≥ 1the solution does not change anymore. A proof of this can be found in Proposition A.1 in the “Appendix”. For larger 2the objective value converges towards P(u≤1)≈0.842. We can understand this as on the one hand the decision xk=−k1−exp 1−1 k, d1,k=−k, d2,k=1−1 k is feasible for (Pred)with the budgets 1=0 and 2,k=−2k(1−exp(1−1 k)) +kfor large k∈N. On the other hand, P(u≤1)is an upper bound for IROP by the definition of the equivalent problem (Pred). This causes that the objective value has to converge towards P(u≤1)for 2→∞. Some of the optimal solution sets W∗and the robustified decisions x∗can be seen in Figs.2and3for different values of . In contrast to the resilience ball and stability radius approach, the solution sets of this inverse robust problem does not satisfy an ordering w.r.t. ⊆if increases component-wise. This behavior can be seen in Fig.2 123 134 H. Berthold et al. Fig. 2 Optimal arguments x∗as red line and W∗as blue area for different values 1while fixing 2:=0 Fig. 3 Optimal arguments x∗as red line and W∗as blue area for different for different values 2while fixing 1:=0 and is caused by a change of the decision x∗(). In return higher objective values are achievable. 7 Conclusion Given a parameterized optimization problem, a corresponding nominal scenario, and a budget, one can ask for a solution that is close to optimal with respect to the objective 123 A unified approach to inverse robust optimization problems 135 function value of the nominal optimization problem, while being feasible for as many scenarios as possible. In this article, we introduced an optimization problem to compute the best coverage of a given uncertainty set. In Sect.2we introduced the inverse robust optimization problem (IROP) and discussed some differences to worst-case robustness using two simple examples. In the next section we then investigated the existence of solutions and some structural properties of the solutions. In Sect.4we discussed different cover spaces that satisfy the assumptions needed for the given structural results of Sect.3. After comparing IROP with the stability radius, the resilience radius, and the radius of robust feasibility in Sect. 5, we provided an example in Sect.6that demonstrates the flexibility of the concept of inverse robustness. This flexibility could in future research be investigated in the light of other robustness concepts. Interesting examples are for example a comparison to Gammarobustness, or the application of the approach to adjustable robustness. As the last example showed, it should in principle also be possible to apply the concept in a multicriteria setting. In Sect.2we discussed the differences to a worst case robust optimization using two simple examples. In future research it will be interesting to compare worst-case robust optimization and inverse robustness using real-world examples. Author Contributions All authors contributed in the conceptualization and writing to the presented research. All authors read and approved the final manuscript. Funding Open Access funding enabled and organized by Projekt DEAL. Availability of data and materials Not applicable. Code Availability Not applicable. Declarations Conflict of interest The authors have no conflicts of interest to declare that are relevant to the content of this article. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. 123 136 H. Berthold et al. Appendix A: Properties of Example 6 Proof of Proposition 6.1 As discussed in Sect.6it is enough to consider bounded intervals. Thus, we know that the problem is equivalent to max x∈R,d1,d2∈R P(u∈[d1,d2]) s.t. −x+u≤−2+1∀u∈[d1,d2], 2x−u≤4+2∀u∈[d1,d2], x(u−1)+exp(u)−1≤0∀u∈[d1,d2], 0∈[d1,d2]. This problem can be reformulated by computing the maxima within the budget and feasibility constraints arg max u∈[d1,d2]−x+u={d2}, arg max u∈[d1,d2]2x−u={d1}, arg max u∈[d1,d2]x(u−1)+exp(u)−1={d2}. To determine the maximal argument in the feasibility constraint we used the identity ∂ug(x,u)=x+exp(u)and that 0 ∈[d1,d2]implies that g(x,0)=−x≤0is a necessary condition for a feasible choice of x. Therefore ∂ug(x,u)>0 holds for all feasible choices of xand u∈R. In a last step, we obtain the maximizer d2by considering g(x,u)=u d1∂ug(x,w)dw. The last constraint also shows that d2≤1. Otherwise if d2>1 we would violate the feasibility constraint with x≥0via x(d2−1)+exp(d2)−1>0. This means that we receive the following equivalent problem (Pred)max x∈R,d1,d2∈R2 P(u≤d2)−P(u≤d1), s.t. −x+d2≤−2+1,(A1) 2x−d1≤4+2,(A2) x(d2−1)+exp(d2)−1≤0,(A3) d1≤0, 0≤d2≤1, 0≤x. The objective function is concave in d1∈(−∞,0]and d2∈[0,∞). The nonlinear constraint is convex in xand d2,asx≥0 and d2∈[0,1]. Since all other constraints 123 A unified approach to inverse robust optimization problems 137 are linear w.r.t. (x,d)∈R3, the reduced problem is a convex optimization problem. The existence of a solution is guaranteed by Theorem 3.4. For the following proposition denote for a given budged the optimal solution of the reduced problem (Pred)by x∗(), d∗ 1() and d∗ 2() Proposition A.1 (Behavior w.r.t. increasing budgets) Fixing 0:=(0,0)leads to the solution x∗=2,d∗=(0,0)and therefore V (W(d∗(0))) =0. For any fixed 1≥0 we get: •lim2→∞ x∗() =∞, •lim2→∞ d∗ 1() =−∞, •lim2→∞ d∗ 2() =1. For any fixed 2≥0and 1≥¯1:=3the second budget constraint and the feasibility constraint are active. Since the feasibility constraint is independent of , it will not change w.r.t. an increasing budget and therefore we obtain •lim1→∞ x∗() =x∗(¯1, 2), •lim1→∞ d∗ 1() =d∗ 1(¯,2), •lim1→∞ d∗ 2() =d∗ 2(¯,2). Proof of Proposition A.1 (i) Case =(0,0). Given the budget :=(0,0),the reduced inverse robust example problem can be formulated as: max x∈R,d1,d2∈R P(u≤d2)−P(u≤d1) s.t. −x+d2≤−2,(A4) 2x−d1≤4,(A5) x(d2−1)+exp(d2)−1≤0, d1≤0, 0≤d2, 0≤x. Considering the budget constraints (A4) and (A5), we conclude x∈2+d2,2+d1 2. Since d1≤0,d2≥0 has to hold, it follows directly x=2∧d1=0∧d2=0. Since this is the only feasible point, it is also the optimal solution of the given problem. (ii) Case lim 2→∞. We have seen in Sect. 6that for 1=0 and 2going to infinity there is a sequence of feasible points such that the objective value 123 138 H. Berthold et al. converges towards P(u≤1). This means that for the optimal objective value we have lim 2→∞ P(u∈[d∗ 1(), d∗ 2()])=P(u∈(−∞,1]). This is only possible if lim 2→∞ d∗ 1() =−∞, lim 2→∞ d∗ 2() =1. Considering the feasibility constraint we receive x∗() ≥exp(d∗ 2()) −1 1−d∗ 2() . This shows that we have lim2→∞ x∗() =∞. iii) Case lim 1→∞. Let us fix an arbitrary 2≥0. If we analyze the reduced inverse robust example problem again, we can rewrite its first budget constraint as d2≤−2+1+x. As we know that the variable d2is bounded above by 1 and we already mentioned that a feasible xhas to satisfy x≥0. Consequently the first budget constraint is fulfilled for all 1≥3. Because 1just occurs in the first budget constraint of the reduced inverse robust example problem, we know that for 1≥3 the solution of the problem instance just depends on the choice of 2≥0 what proves the claim.  References Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math Program 99(2):351–376 Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization. Princeton series in applied mathematics, vol 28. Princeton University Press, Princeton Bertsimas D, Brown DB (2009) Constructing uncertainty sets for robust linear optimization. Oper Res 57(6):1483–1495 Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math Program 98(1–3):49–71 Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1):35–53 Bertsimas D, Pachamanova D, Sim M (2004) Robust linear optimization under general norms. Oper Res Lett 32(6):510–516 Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev 53(3):464–501 123