(PDF) Constrained optimization problems under uncertainty with coherent lower previsions

CONSTRAINED OPTIMIZATION PROBLEMS UNDER UNCERTAINTY WITH COHERENT LOWER PREVISIONS ERIK QUAEGHEBEUR, KEIVAN SHARIATMADAR, AND GERT DE COOMAN A BSTRACT. We investigate a constrained optimization problem with uncertainty about constraint parameters. Our aim is to reformulate it as a (constrained) optimization problem without uncertainty. This is done by recasting the original problem as a decision problem under uncertainty. We give results for a number of different types of uncertainty models— linear and vacuous previsions, and possibility distributions—and for two common but different optimality criteria for such decision problems—maximinity and maximality. We compare our approach with other approaches that have appeared in the literature. 1. I NTRODUCTION Consider the following optimization problem: maximize f (x) subject to x ⊳ Y , where f is a bounded real-valued objective function defined on a set X of optimization variables x, Y is an uncertain variable taking values in a set Y , and ⊳ is a relation on X × Y .1 Optimization problems of this type are encountered in many fields and applications. We give some practical examples in Section 7. To make this more concrete, consider the following toy problem. Suppose we know that Y is close to the real number c, and we are looking for the largest number x such that still x ≤ Y . This problem could be represented mathematically as follows. The linguistic information ‘Y is close to the real number c’ can, for example, be modeled by a possibility distribution π on the set R of real numbers with mode c,2 and we are looking for the solution of the following optimization problem: maximize x subject to x ≤ Y , which can be seen as a special case of the more general version, where f is the identity function, and ⊳ := ≤.3 The main difficulty with these problems is the uncertainty that appears in the constraint: because the value of Y is uncertain, it is uncertain for which values of x the constraint x ⊳ Y Key words and phrases. constrained optimization, maximinity, maximality, coherent lower prevision, linear prevision, vacuous prevision, possibility distribution. 1The boundedness of f is not an essential technical requirement, but we make it here in order to allow us to work with the more standard imprecise probability models [25], which require boundedness. For discussions of imprecise probability models without this limitation, we refer to [23, 24]. 2For a discussion of why this makes sense when modeling uncertainty with imprecise probability models, see [27]. 3The technical problem that the identity function is not bounded on the reals can be overcome, albeit somewhat artificially, by letting X be a bounded real interval that is large enough. Alternatively, we could extend the present discussion to include imprecise probability models that allow for unbounded gain functions, as discussed in [23, 24]. But this goes beyond the scope of this paper, which is intended as an exposition of ideas and first principles. 1 2 ERIK QUAEGHEBEUR, KEIVAN SHARIATMADAR, AND GERT DE COOMAN is satisfied, and therefore the domain over which f (x) has to be maximized is not well known. The optimization problem is therefore ill-posed: it is underspecified, as there is no unique way of interpreting what is meant by maximizing a function over an uncertain domain; it might also be over-specified, as it may be infeasible in some particular case. We will address this difficulty in Section 2 by reducing the optimization problem to a well-posed decision problem from which the uncertainties present in the description of the constraint have been eliminated. We mean by this that uncertain variables no longer appear in the problem; this is achieved by appropriately replacing the uncertain variables in the original formulation by their uncertainty models. For example, a naive way of doing this, when the uncertainty model is a classical probability distribution and Y ⊆ R, would consist of replacing the uncertain variable by its expectation. We then investigate what results can be obtained for different types of uncertainty models for the uncertain variable Y —expectation operators or probability measures in Section 3, intervals or vacuous previsions [see, e.g., 25] in Section 4, and possibility distributions [see, e.g., 7] in Section 5—and for two different optimality criteria for decision problems— maximinity and maximality [see, e.g., 22]. After this, in Section 6, we compare our approach with related work. The salient feature of our approach is that we use the same methodology and mathematical theory for solving all of these problems. Indeed, probability measures, intervals and (numerical) possibility measures can all be seen as special cases of a common and unifying uncertainty modeling framework: the theory of coherent lower previsions [see, e.g., 15, 25]. Since we are convinced that coherent lower previsions (and imprecise probability models in general) provide a useful interpretational framework for possibility distributions [see also our work on possibilistic lower previsions 4], we believe this paper establishes a novel approach to possibilistic optimization. It has the distinct advantage that the results we derive have a clear and useful behavioral interpretation. In the remainder of this Introduction we provide some further background information. In Section 1.1, we give a brief introduction to coherent lower previsions and how they (mathematically) generalize both probability and possibility distributions as uncertainty models. In Section 1.2, we do the same for decision making with coherent lower previsions. We deal with some odds and ends in Section 1.3. 1.1. Coherent lower and upper previsions. Consider an uncertain variable Y that can take values in a set Y . The uncertainty of an agent dealing with Y is described using an uncertainty model. The uncertainty model allows the agent to draw inferences about Y and functions thereof and make decisions in problems involving Y . The classical uncertainty model is the probability distribution; in this context Y is usually called a random variable. Working with probability distributions or probability measures is equivalent to working with expectation operators [28]. We use the terminology of de Finetti [6] and call such expectation operators linear previsions. A linear prevision is a real functional P defined on the space G (Y ) of bounded real-valued functions on Y , that satisfies the following three so-called coherence conditions: Positivity: Homogeneity: Additivity: P(g) ≥ inf g, (P1) P(λ g) = λ P(g), (P2) P(g + h) = P(g) + P(h), (P3) for all bounded real-valued functions g, h on Y and all real λ . In the interpretation of de Finetti [6], the real-valued functions g = g(Y ) are seen as gambles about Y and their CONSTRAINED OPTIMIZATION PROBLEMS UNDER UNCERTAINTY WITH COHERENT LOWER PREVISIONS 3 previsions P(g) are seen as fair prices: the agent is prepared to sell a gamble g(Y ) for any price higher than P(g) and buy it for any lower price. Given a linear prevision P, the relationship with the corresponding (finitely additive) probability measure—also denoted by P—defined on the set of all events 2Y is given by P(A) := P(IA ), where IA is the indicator of A—it takes the value 1 on A and is 0 elsewhere. Probability measures P consequently satisfy three coherence conditions: Positivity: P(A) ≥ 0, (P1’) Unit Norm: P(Y ) = 1, (P2’) Additivity: (P3’) P(A ∪ B) = P(A) + P(B), where A, B ⊆ Y are disjoint. There is a one-to-one correspondence between probabilities and linear previsions (their expectation operators). An important alternative—even orthogonal, one could say—uncertainty model is the possibility distribution. In this paper, we consider possibility distributions π : Y → [0, 1] that are normal, meaning that sup π = 1. One can equivalently work with possibility measures Π defined for events A of Y , and by extension—using the Choquet integral—with possibility operators Π defined for gambles g on Y [5]: Π (A) := sup π(y), Π (g) := inf g + y∈A Z sup g inf g Π ({y ∈ Y : g(y) ≥ t}) dt. (1) The necessity measure N conjugate to Π is defined by N(A) = 1 − Π (Ac ) for events A, and more generally by N(g) = −Π (−g) for gambles g. Necessity and possibility measures N and Π —and therefore also the operators derived from them—can, as a class onto themselves, be characterized by the following conditions: Positivity: Normality: Maxitivity: N(A) ≥ 0, Π (A) ≥ 0, (Π 1) N(0) / = 0, Π (Y ) = 1, (Π 2) [ (Π 3) \ N( A ) = inf N(A), A∈A Π( A ) = sup Π (A), A∈A where A ⊆ 2Y , and if A = 0/ the infimum is one and the supremum is zero by definition. Both types of uncertainty model, in the incarnations described above, are special cases of the much more general coherent upper and lower previsions [see, e.g., 15, 25, for details and terminology]. These conjugate operators P and P, defined for all gambles g on Y and related by P(g) = −P(−g), are characterized by the following three conditions:4 Positivity: Positive Homogeneity: Super/Sub-additivity: P(g) ≥ inf g, P(g) ≤ sup g, (P1) P(λ g) = λ P(g), P(λ g) = λ P(g), (P2) P(g + h) ≥ P(g) + P(h), P(g + h) ≤ P(g) + P(h), (P3) where g, h ∈ G (Y ) and λ > 0. Their restriction to (indicators of) events are called coherent lower and upper probabilities. In the behavioral interpretation of Walley [25], who follows the lead of de Finetti [6] in this regard, lower and upper previsions for gambles are again seen as prices: respectively the agent’s supremum acceptable buying price and infimum acceptable selling price. 4The assumption that P and P are defined on the whole of G (Y ) is not a trivial one in general: so-called natural extension from a partial specification requires solving a linear programming problem [25, Ch. 3]. However, for the cases looked at in this paper, natural extension just requires calculating a (Choquet) integral in the most complex case, which is far less computationally demanding. 4 ERIK QUAEGHEBEUR, KEIVAN SHARIATMADAR, AND GERT DE COOMAN When the lower prevision coincides with the upper prevision, they are linear previsions [see, e.g., 25]. Possibility operators are a special type of coherent upper previsions and necessity operators are similarly special coherent lower previsions [for more details about their relation, see 3, 5, 16, 26, 27]. In this paper, we use the theory of coherent lower (and upper) previsions as a unifying framework for linear previsions and possibility/necessity operators. All the uncertainty models we deal with fall into either category, but thanks to this framework, we can treat constrained optimization problems with uncertain variables described by both types in the constraint specification in a unified way and with a unified interpretation. It also leaves the door open to similarly deal with problems involving other types of uncertainty models under the coherent lower prevision umbrella. It will also be useful to shed some light on the link between coherent lower previsions on the one hand, and sets of linear previsions (or probabilities) on the other. Given a coherent lower prevision P, we can consider its set of dominating linear previsions: M (P) := {P : (∀g ∈ G (Y ))P(g) ≥ P(g)} This set is non-empty, convex, and closed (in the topology of point-wise convergence [see, e.g., 25]). Moreover, it turns out that P is the lower envelope of the set M (P): P(g) = min{P(g) : P ∈ M (P)} for all gambles g on Y . (2) These correspondences tell us that, at least from a mathematical point of view, working with a coherent lower prevision is equivalent to working with a convex closed set of linear previsions (or probabilities). We close this section with some properties that all coherent lower and upper previsions have, and which we use further on in the paper: Constant additivity: Mixed super-additivity: P(g + µ) = P(g) + µ, (P4) P(g + h) ≥ P(g) + P(h), (P5) where g, h ∈ G (Y ) and µ ∈ R. 1.2. Decision making with coherent lower previsions. We now turn to decision making, and consider a subject who may choose between a number of acts, or decisions, x in a set X , the outcome of which depends on the uncertain variable Y . To be more specific, we assume that with each possible decision x there is associated a gain function gx on Y , with the following interpretation: if an agent makes decision x, then the corresponding outcome of this decision depends on the actual value y that Y assumes, and then has corresponding utility gx (y). We will assume that each gx is a bounded real-valued function, a gamble on Y . Making decisions in the face of uncertainty about Y is in this sense taking gambles on the value of Y . We will also assume that all utilities are expressed in units of some linear utility scale [for more details, see 25]. If our agent has beliefs about Y expressed in terms of a coherent lower prevision P—and therefore supremum buying prices for gambles about Y —we can use these beliefs to induce a binary relation on the set X of all decisions. We say that he strictly prefers decision x1 to decision x2 , and we write x1 ≻ x2 , if he is willing to pay some strictly positive price in order to exchange gx2 for gx1 : x1 ≻ x2 ⇔ P(gx1 − gx2 ) > 0. (3) This definition gives an elegant and useful behavioral interpretation to the relation ≻, a strict partial order (irreflexive and transitive) on X . Using Equation (2) and the properties CONSTRAINED OPTIMIZATION PROBLEMS UNDER UNCERTAINTY WITH COHERENT LOWER PREVISIONS 5 of linear previsions, we see that the equivalence (4) x1 ≻ x2 ⇔ (∀P ∈ M (P))P(gx1 ) > P(gx2 ) also allows us to give a robustness interpretation to this strict partial order: x1 ≻ x2 if and only if x1 has a strictly higher expected utility than x2 for all the probabilities that are compatible with the lower prevision P. It is important to realize that, unless P is a linear prevision, ≻ is not necessarily a total order: there may be x1 and x2 that are incomparable in the sense that neither x1 ≻ x2 nor x2 ≻ x1 . Given a set of decisions X , we should aim for those decisions that are as high as possible in the order ≻; we are looking for those decisions x that are maximal, or undominated, in that no decision z is considered better: x is maximal ⇔ (∀z ∈ X )z ⊁ x ⇔ (∀z ∈ X )P(gz − gx ) ≤ 0 ⇔ (∀z ∈ X )P(gx − gz ) ≥ 0 ⇔ inf P(gx − gz ) ≥ 0. (5) z∈X When P is a linear prevision P, we see that x1 ≻ x2 ⇔ P(gx1 ) > P(gx2 ); in this case the order ≻ is a total strict order. Therefore a decision x is maximal if and only if it has the highest expected gain P(gx ), i.e., we maximize expected utility: x is maximal ⇔ x ∈ argmax P(gz ). z∈X This leads us to consider an alternative, albeit less well justified criterion for optimality of a decision under a coherent lower prevision P: x is maximin ⇔ x ∈ argmax P(gz ), (6) z∈X or, in other words, if it maximizes the lower expected gain. Maximin solutions can be seen as resulting from worst-case reasoning; the solutions resulting from the best-case reasoning analogue are called maximax solutions and are obtained by replacing P by P in Equation (6). Any maximin solution is automatically also maximal, since it follows from the mixed super-additivity (P5) of P that: P(gx − gz ) ≥ P(gx ) + P(−gz ) = P(gx ) − P(gz ). Whether or not there are maximal and maximin solutions depends on the behavior of infz∈X P(gx − gz ) and P(gx ) as functions of x on X . For more details, properties and further interpretation of criteria for optimal decision making with imprecise probabilities, we refer to [22]. 1.3. Some odds and ends. We work with general spaces X and Y and relations ⊳, and give illustrations for the particular case where X = Y := R and ⊳ := ≤. In case a general treatment is too involved, we will restrict attention to this particular case. Some useful (abuse of) notation: x ⊳ := {y ∈ Y : x ⊳ y}, B ⊳ := [ x ⊳, B ⊳ := [ y∈A x ⊳, x∈B x∈B ⊳ y := {x ∈ X : x ⊳ y}, ⊳ A := \ ⊳ y, ⊳ A := \ ⊳ y, (7) y∈A where, as needed, x ∈ X , y ∈ Y , B ⊆ X , and A ⊆ Y . Similar definitions can be used for the complementary relation ⋪ instead of ⊳. Note that B ⊳ ⊆ B ⊳ and ⊳ A ⊆ ⊳ A. 6 ERIK QUAEGHEBEUR, KEIVAN SHARIATMADAR, AND GERT DE COOMAN 2. R EFORMULATION AS A DECISION PROBLEM UNDER UNCERTAINTY Let us have a fresh look at the original optimization problem, now with the decision making approach described in Section 1.2 in mind: maximize f (x) subject to x ⊳ Y . What is clear is that calling some x the solution to this problem corresponds to deciding that x is optimal in some sense. What is not yet clear is the gain function associated to each possible decision x in X . The gain functions we propose are based on the reformulation of the original optimization problem as an unconstrained one: maximize f (x)I⊳Y (x) + LI⋪Y (x). In this expression, I⊳Y and I⋪Y are the indicator functions (cf. Section 1.1) of the sets ⊳ Y and ⋪ Y of optimization variables x that respectively do and do not satisfy the constraint (cf. Section 1.3); as Y is an uncertain variable, these are uncertain sets. Furthermore, L is the penalty value, a real number that should be chosen strictly smaller than inf f to make sure that breaking the constraint is penalized, i.e., leads to an objective function value that is inferior to any value that can be obtained when not breaking the constraint. To see the intuition behind this reformulation, consider the case that Y = y and the illustration below, in which X = Y := R and ⊳ := ≤: f (x)I⊳y (x) + LI⋪y (x) f (x) sup f |⊳y sup f |⊳y L ⋪y ⊳y y x y x We used the notation f |B to denote restriction of f to the subset B of its domain. If—as in this illustration—there is no uncertainty about Y , then the unconstrained problem is equivalent to the original one due to the restriction placed on the penalty value. In case there is uncertainty about Y , the objective function of the unconstrained problem provides us with a gain function Gx (Y ) := f (x)I⊳Y (x) + LI⋪Y (x) for each possible decision x in X . Given that I⊳Y (x) = Ix⊳ (Y ), we can write: Gx = f (x)Ix⊳ + LIx⋪ = L + f (x) − L Ix⊳ = f (x) + L − f (x) Ix⋪ . (8) By associating this form of gain function with the original optimization problem and by choosing a decision criterion, we give meaning to the original optimization problem under uncertainty. Next to its intuitive appeal, we think this choice of gain function is reasonable, because—together with either maximality or maximinity as the decision criterion—(i) it results in the standard constrained optimization problem when there is no uncertainty about Y , (ii) the penalty value L allows us to quantify the impact of breaking the constraint (which would not be possible when just replacing Y with an expected value of some sort in the original optimization problem), and (iii) it is quite simple. More complex gain functions could also have advantages, but the complexity of the resulting decision problems may be practically prohibitive. Now, given our choice of gain function and given that our uncertainty about Y is quantified by a coherent lower prevision P, what becomes of the two decision criteria we are considering? By using Equation (8) and the constant additivity (P4) and positive homogeneity (P2) CONSTRAINED OPTIMIZATION PROBLEMS UNDER UNCERTAINTY WITH COHERENT LOWER PREVISIONS 7 of P, we see—using the shorthand P(x ⊳) := P(Ix⊳ ) (cf. Section 1.1)—that P(Gx ) = P L + f (x) − L Ix⊳ = L + f (x) − L P(x ⊳). (9) Plugging this into the maximinity criterion (6), we find that the set of maximin solutions is given by (10) argmax P(Gx ) = argmax( f (x) − L)P(x ⊳), x∈X x∈X since an additive constant has no impact on the location of the maximum. For the maximality criterion (5), no immediate simplifications are possible; plugging in the gain function from Equation (8) shows that some x in X is maximal if and only if (11) inf P(Gx − Gz ) = inf P f (x) − L Ix⊳ − f (z) − L Iz⊳ ≥ 0. z∈X z∈X In the next three sections, we investigate what becomes of the gain function Gx -specific criteria (10) and (11) when considering different types of coherent lower previsions P. So the main difficulty will be to find practical expressions for P(x ⊳) and infz∈X P(Gx − Gz ), and using those to find sufficiently explicit expressions for the sets of maximin and maximal solutions, respectively. Before starting with that, we quickly look at the generality of the problem we consider. 2.1. Generality of the considered problem. It is good to realize that the optimization problem we consider is quite general, as problems with uncertain variables in the objective function can be reduced to it (making abstraction of possible interpretational issues): maximize f (x,Y ) subject to x ⊳ Y is formally equivalent to a problem that is of the same form as the original one, maximize x0 subject to x0 ≤ f (x,Y ) and x ⊳ Y , where x0 ∈ R. We have moved from x ∈ X to (x0 , x) ∈ R × X as the optimization variable. We need to check whether this generalization is a correct one in the sense that it gives rise to the same maximin and maximal solutions for the original problem with an objective function f that does not depend on Y . The gain function—cf. Equation (8)—now becomes G(x0 ,x) = L + x0 − L Ix0 ≤ ( f (x))Ix⊳ . So the set of maximin solutions is argmax P(G(x0 ,x) ) = argmax (x0 − L)Ix0 ≤ ( f (x))P(x ⊳) (x0 ,x)∈R×X x0 ∈R,x∈X ( ( f (z), z) : z ∈ argmaxx∈X ( f (x) − L)P(x ⊳) = R×X if supx∈X P(x ⊳) > 0, if supx∈X P(x ⊳) = 0. Ignoring the circumventable technical difference in case supx∈X P(x ⊳) = 0, this is the same as found in Equation (10). Similarly, for the maximal solutions—cf. Equation (11)—we see inf (z0 ,z)∈R×X P(G( f (x),x) − G(z0 ,z) ) = inf P(G( f (x),x) − G( f (z),z) ) = inf P(Gx − Gz ). z∈X z∈X Because x0 < f (x) implies P(G( f (x),x) − G(x0 ,x) ) = f (x) − x0 P(x ⊳) > 0 if P(x ⊳) > 0 and thus ( f (x), x) ≻ (x0 , x) by Equation (3), we can only have a (technical) difference whenever P(x ⊳) = 0 for some x in X such that ( f (x), x) is maximal, which can be circumvented by just positing that x0 < f (x) ⇒ ( f (x), x) ≻ (x0 , x). 8 ERIK QUAEGHEBEUR, KEIVAN SHARIATMADAR, AND GERT DE COOMAN 3. L INEAR PREVISIONS When the uncertainty about Y is described by a linear prevision (or expectation operator) P, for which both criteria reduce to maximizing expected utility, the set of optimal solutions is argmax P(Gx ) = argmax( f (x) − L)P(x ⊳). x∈X (12) x∈X For our prototypical particular case X = Y := R and ⊳ := ≤. So for any x in X we see that then x ⊳ = [x, +∞). Define the distribution function of P by FP (x) := P((−∞, x]) for any x in X . Then the set of optimal solutions for linear previsions P with continuous distribution functions is argmaxx∈X f (x) − L 1 − FP (x) , which is straightforward to find using analytical or numerical methods. 4. VACUOUS PREVISIONS In this section, we consider vacuous previsions, which express ignorance relative to a non-empty subset of the possible parameter values. The general case consists of a vacuous prevision relative to a subset A of Y and for a given function g, so P(g) := inf g|A and P(g) := sup g|A . It provides a model for the available information when we know that Y assumes a value in A but nothing more. This is corroborated by the fact that M (P) = {P : P(A) = 1} (13) is the set of linear previsions (probabilities) associated with this vacuous prevision. For our particular case, we will consider a vacuous prevision relative to an interval [a, b] ⊂ R, so then A := [a, b]. 4.1. Maximinity. For maximinity in the general case, we combine the vacuous prevision’s definition with Equation (10); the optimal x in X are those that maximize (14) P(Gx ) = L + f (x) − L inf Ix⊳ |A . So, by evaluating the expression inf Ix⊳ |A , we see that ( f (x), A ⊆ x ⊳, P(Gx ) = L, otherwise. (15) The expression A ⊆ x ⊳ can be expanded to (∀y ∈ A)x ⊳ y and from this and Equation (7), we can deduce it is equivalent to x ∈ ⊳ A. So, maximizing P(Gx ) is in the end the same as maximizing f |⊳A and the set of optimal solutions is argmax f (x). (16) x∈⊳A Notice that this set does not depend onT L. In our particular case, as ≤ [a, b] = y∈[a,b] {x ∈ X : x ≤ y} = (−∞, a] by Equation (7), this set of solutions is argmaxx≤a f (x). If f is the identity (or, more generally, strictly increasing), then the maximin solution is a: the largest number (in the sense of maximinity) smaller than Y , when all we know is that a ≤ Y ≤ b, is a. CONSTRAINED OPTIMIZATION PROBLEMS UNDER UNCERTAINTY WITH COHERENT LOWER PREVISIONS 9 4.2. Maximality. For maximality in the general case, we combine the vacuous prevision’s definition with Equation (11); the optimal x in X are those for which P(Gx − Gz ) = P f (x) − L Ix⊳ − f (z) − L Iz⊳ (17) = sup f (x) − L Ix⊳ (y) − f (z) − L Iz⊳ (y) ≥ 0 y∈A for all z in X . We look for an explicit expression for P(Gx − Gz ) graphically, by considering all the possible positions A can be in relative to x ⊳ and z ⊳. For this, we first divide X 2 in quadrants: We consider all positions of A relative to these quadrants. When A x ⊳∩z ⊳ x ⊳∩z ⋪ intersects some quadrant, it is shaded; so we need to consider all 24 − 1 = 15 possible non-empty shadings and calculate P(Gx − Gz ) x ⋪∩z ⊳ x ⋪∩z ⋪ for each of these shadings using the expression in Equation (17). We find:   , , , , , , , , f (x) − L,     0, , ,  P(Gx − Gz ) = max{0, f (x) − f (z)}, , ,    f (x) − f (z), , ,    L − f (z), .   f (x) − L, A ∩ x ⊳ ∩ z ⋪ 6= 0, /     0, A ∩ x ⊳ = 0/ ∧ A ∩ z ⋪ 6= 0, /  = max{0, f (x) − f (z)}, A ∩ x ⊳ ∩ z ⋪ = 0/ ∧ A ∩ x ⊳ 6= 0/ ∧ A ∩ z ⋪ 6= 0, /    f (x) − f (z), A ∩ x ⊳ 6= 0/ ∧ A ∩ z ⋪ = 0, /    L − f (z), A ∩ x ⊳ = 0/ ∧ A ∩ z ⋪ = 0. / The first three cases are always non-negative, the fourth one can be both positive and negative, and the last one is always negative. Therefore, only the last two cases are important when checking the condition for an x in X to be maximal, i.e., to avoid its being non-maximal: inf P(Gx − Gz ) ≥ 0 z∈X ⇔(∀z ∈ X ) ¬(A ∩ x ⊳ = 0/ ∧ A ∩ z ⋪ = 0) / ∧ (A ∩ x ⊳ 6= 0/ ∧ A ∩ z ⋪ = 0) / ⇒ f (x) − f (z) ≥ 0 ⇔(∀z ∈ X ) A ∩ x ⊳ 6= 0/ ∨ A ∩ z ⋪ 6= 0/ ∧ A ∩ x ⊳ = 0/ ∨ A ∩ z ⋪ 6= 0/ ∨ f (x) ≥ f (z) ⇔(∀z ∈ X ) A ∩ z ⋪ 6= 0/ ∨ A ∩ x ⊳ 6= 0/ ∧ A ∩ x ⊳ = 0/ ∨ f (x) ≥ f (z) ⇔(∀z ∈ X ) A ∩ z ⋪ 6= 0/ ∨ A ∩ x ⊳ 6= 0/ ∧ f (x) ≥ f (z) ⇔(∀z ∈ X ) (A ∩ z ⋪ 6= 0/ ∨ A ∩ x ⊳ 6= 0) / ∧ A ∩ z ⋪ 6= 0/ ∨ f (x) ≥ f (z) ⇔(∀z ∈ X )(A ∩ z ⋪ 6= 0/ ∨ A ∩ x ⊳ 6= 0) / ∧ (∀z ∈ X ) A ∩ z ⋪6= 0/ ∨ f (x) ≥ f (z) ⇔ A ∩ x ⊳ 6= 0/ ∨ (∀z ∈ X )(A ∩ z ⋪ 6= 0) / ∧ (∀z ∈ X ) A ∩ z ⋪ = 0/ ⇒ f (x) ≥ f (z) / ∧ (∀z ∈ X ) z ∈ ⊳ A ⇒ f (x) ≥ f (z) ⇔(x ∈ ⊳ A ∨ ⊳ A = 0) ⇔⊳ A = 0/ ∨ (x ∈ ⊳ A ∧ f (x) ≥ sup f |⊳A ). (18) 10 ERIK QUAEGHEBEUR, KEIVAN SHARIATMADAR, AND GERT DE COOMAN So, if ⊳ A = 0, / then all elements of X are maximal; otherwise, only those x in ⊳ A such that f (x) ≥ sup f |⊳A are. Notice that the set of maximal solutions does not depend on L either. In our particular case, as ≤ [a, b] = (−∞, a] and similarly ≤ [a, b] = (−∞, b] by Equation (7), we see that those x ≤ b such that f (x) ≥ sup f |(−∞,a] are maximal. Comparing them to those we found to be optimal under maximinity in the previous section, we see that now more elements can be optimal and that all maximin solutions are also maximal solutions. For instance, when f is the identity map, the set of all maximal elements is [a, b]: any element of [a, b] is a largest number (in the sense of maximality) smaller than Y , when all we know is that a ≤ Y ≤ b. This suggests that the maximality criterion generally leads to a more robust solution, as was intended from the outset: see also Equation (4). 5. P OSSIBILITY DISTRIBUTIONS In this section, we consider possibility distributions. The general case consists of a possibility distribution π on Y , so for a subset A of Y , P(A) := sup π|A and P(A) := 1 − sup π|Ac . For any function h on Y , we can use the Choquet integral [see, e.g., 3, 17, for motivation] to associate a coherent upper prevision with this upper probability: P(h) := inf h + Z sup h inf h P({y ∈ Y : h(y) ≥ t}) dt = inf h + Z sup h inf h sup π|{y∈Y :h(y)≥t} dt. (19) For our prototypical example, we will consider a continuous fuzzy number—i.e., quasiconcave—π with leftmost mode c ∈ R. 5.1. Maximinity. For maximinity in the general case, we combine the possibility distribution’s definition with Equation (10); the optimal x in X are those that maximize P(Gx ) = L + f (x) − L (1 − sup π|x⋪ ), (20) because P(x ⊳) = 1 − P(x ⋪) = 1 − sup π|x⋪ . So, maximizing P(Gx ) corresponds to maximizing f (x) − L (1 − sup π|x⋪ ) and the set of optimal solutions is argmax f (x) − L (1 − sup π|x⋪ ). (21) x∈X Notice that this set generally depends on L. In our particular case, as sup π|x6≤ = π(min{x, c}), argmax( f − L)(1 − π)|<c is the set of solutions. When f is the identity map and π increases linearly from 0 in a to 1 in c > a, the L+c minimax solution is given by max{a, L+c 2 }, where 2 < c because L is small with respect to f -values, i.e., a and c. 5.2. Maximality. For maximality in the general case, we combine the possibility distribution’s definition with Equation (11); the optimal x ∈ X are those for which P(Gx − Gz ) = inf(Gx − Gz ) + Z sup(Gx −Gz ) inf(Gx −Gz ) P({y ∈ Y : Gx (y) − Gz (y) ≥ t}) dt ≥ 0 (22) for all z in X . To calculate a more explicit expression, we need to be able to determine the level set appearing as an argument of P for every t in the range of Gx − Gz .  ∆xz := f (x) − f (z), y ∈ x ⊳ ∩ z ⊳,     ∆ := f (x) − L, y ∈ x ⊳ ∩ z ⋪, xL Gx (y) − Gz (y) =  := −∆ L − f (z), y ∈ x ⋪ ∩ z ⊳,   zL  0, y ∈ x ⋪ ∩ z ⋪. CONSTRAINED OPTIMIZATION PROBLEMS UNDER UNCERTAINTY WITH COHERENT LOWER PREVISIONS11 We furthermore need to know the relative order of these four possible values: ∆xL is the largest, −∆zL is the smallest, and the relative order of 0 and ∆xz depends on the relative order of f (x) and f (z). So there are two cases:   x ⊳ ∪ z ⋪, −∆zL < t ≤ 0,   if f (x) ≥ f (z) then x ⊳, 0 < t ≤ ∆xz ,        x ⊳ ∩ z ⋪, ∆xz < t ≤ ∆xL , {y ∈ Y : Gx (y) − Gz (y) ≥ t} =      x ⊳ ∪ z ⋪, −∆zL < t ≤ ∆xz ,   if f (x) ≤ f (z) then z ⋪, ∆xz < t ≤ 0,   x ⊳ ∩ z ⋪, 0 < t ≤ ∆xL . We see that in both cases the integrand is piecewise constant, and the integral is therefore a weighted sum of three terms: ( ∆zL P(x ⊳ ∪ z ⋪) + ∆xz P(x ⊳) + ∆zL P(x ⊳ ∩ z ⋪), f (x) ≥ f (z), P(Gx − Gz ) = −∆zL + ∆xL P(x ⊳ ∪ z ⋪) − ∆xz P(z ⋪) + ∆xL P(x ⊳ ∩ z ⋪), f (x) ≤ f (z). (23) Using the above expression to derive the maximal solutions turns out to be quite cumbersome in general. We investigate whether we can obtain some results in our particular case, for which x ⊳ ∩ z ⋪ = [x, z), x ⊳ = [x, +∞), and z ⋪ = (−∞, z). So z x=z the relative location of x, y, and c—the fuzzy number π’s leftmost mode—will determine the values of P(x ⊳ ∩ z ⋪) = sup π|[x,z) , (c, c) P(x ⊳) = sup π|[x,+∞) , and P(z ⋪) = sup π|(−∞,z) . These upper probx abilities are constant on the partitioning of (x, z)-space delineated by x = z, x = c, and z = c shown on the right. We find π (x) 1 P(x ⊳ ∩ z ⋪) = , π (z) 0 π (x) 1 0 P(x ⊳) = 0 1 π (x) 1 1 P(z ⋪) = , 1 1 . π (z) π (x) π (z) π (z) (24) Because of the maxitivity of possibility measures, we also find 1 1 P(x ⊳ ∪ z ⋪) = max{P(x ⊳), P(z ⋪)} = 1 (25) , 1 1 π (x) ⌣ π (z) where π(x) ⌣ π(z) := max{π(x), π(z)}. Calculating P(Gx − Gz ) for general objective functions f still results in quite complicated expressions. Therefore we further restrict ourselves to strictly increasing objective functions. After combining (23) with the expressions (24)–(25) above and some manipulations of the expressions so obtained—among them ∆xz = ∆xL − ∆zL —, we find π (x)∆xL ∆xL P(Gx − Gz ) = ∆xL − 1 − π (z) ∆zL ∆xz π (x)∆xz π (x)∆xL − π (x) + 1 − π (x) ⌣ π (z) ∆zL , (26) 12 ERIK QUAEGHEBEUR, KEIVAN SHARIATMADAR, AND GERT DE COOMAN where the regions for which P(Gx − Gz ) is not uniformly non-negative have been shaded light gray. So for strictly increasing f , we find that (27) x ≤ c is maximal ⇔ sup 1 − π(z) ∆zL ≤ ∆xL , x<z<c x ≥ c is maximal ⇔ sup π(x) + 1 − π(x) ⌣ π(z) ∆zL ≤ π(x)∆xL . (28) z<c To compare this solution with the one we obtained in the vacuous case of Section 4.2, assume π has the interval [a, b] as support. Then it follows from Equations (27) and (28) that no x outside [a, b] can be maximal under π: z := a dominates x < a and z := b dominates x > b. This should not surprise us, as the beliefs embedded in the possibility distribution π tell us at the very least that a ≤ Y ≤ b. To illustrate that possibility distributions generally do provide more useful information, consider the case where f is the identity map and π increases linearly from 0 in a to 1 in c > a, which we considered at the end of Section 5.1 and for which we found a maximin solution max{a, µ} with µ := L+c 2 . Equation (27)’s right-hand condition can be rewritten as c−µ µ −a x ≥ max{a, c−a L + c−a µ}, from which it can also be verified that the maximin solution is maximal, as L < µ. 6. A SELECTED OVERVIEW OF THE RELATED LITERATURE Of course we are not the first to consider constrained optimization problems under (nonprobabilistic) uncertainty, where the uncertainty is present in the constraint. Let us give a brief selected overview of the related literature and compare our approach to the ones found there. We describe results and approaches from the literature as much as possible in the language and notation of this paper, to simplify comparisons. 6.1. Vacuous previsions. Soyster [21] investigates so-called ‘inexact’ linear programming problems: maximize c′ x subject to Y x ≤ b and x ≥ 0, where X := Rn , Y := Rm×n , c ∈ Rn (primes indicate transposition), b ∈ Rm , and the lower prevision describing the uncertain matrix Y is vacuous relative to a convex subset A := ×nj=1 A j of matrices, where each A j is a convex subset of Rm . The implicit decision criterion used is maximinity, so this is a special case of Section 4.1 where, in Equation (16) we now have that ⊳ A = {x ≥ 0 : ȳx ≤ b}, where ȳ is the matrix with components ȳi j := supy∈A yi j . Soyster’s approach can be seen as a special case of robust optimization [see, e.g., 2], in which the uncertainty about the parameters is expressed using an ‘uncertainty set’ of possible values for what we call the uncertain variable Y . The optimization problem is then transformed in a new one by requiring that the constraints are satisfied for all possible values at the same time. This is still a special case of our approach in which the uncertainty is expressed using vacuous previsions and where the optimality criterion used is maximinity (cf. Section 4.1). The work discussed above fits in the large body of literature that deals with optimization problems involving uncertainty of a kind that is formalized by vacuous previsions in this paper. Most of the work we have come across essentially uses maximinity as the optimality criterion; the results we derive for the maximality case (cf. Section 4.2) seem not to have appeared before. (Interesting related work has also been done in which the notion of optimality criterion as we use it does not appear [see, e.g., 8, Ch. 3 and 4].) Vacuous CONSTRAINED OPTIMIZATION PROBLEMS UNDER UNCERTAINTY WITH COHERENT LOWER PREVISIONS13 previsions are of course very simple uncertainty models. From there, a next step up in complexity are models using possibility distributions, which we deal with next. 6.2. Possibility distributions. With the increased complexity of possibility distributions comes an increased importance of the interpretation attached to the uncertainty models using them. We use the behavioral interpretation of Walley [25] discussed in Section 1.1. This in combination with the type of optimization problem that is the subject of this paper is something we have not come across yet in the literature. Nevertheless, it may be interesting to do a comparison with approaches inspired by other interpretations. To discuss the approach based on the ideas of Bellman and Zadeh [1] concerning decision making in a fuzzy context, consider the following modification of our original problem: maximize f (x) ˜ y, subject to x ⊳ in which no uncertainty is assumed to be present in the parameters (viz. the constant y ∈ Y replacing Y ), but where the constraints themselves are assumed to be fuzzy (indicated with a tilde). Mathematically, this fuzziness is expressed using a possibility distribution π⊳y on X that expresses to what degree the constraints are satisfied. The maximization itself is also taken to be fuzzy, which is expressed mathematically using a possibility distribution π f ,⊳y ˜ on X that expresses to what degree the objective function or goal f is maximized; the ˜ y is meant to indicate that (the support of) π⊳y first needs to be known to give subscript ⊳ an informed definition of π f ,⊳y ˜ . The fuzzy constrained optimization problem then gives rise to a fuzzy decision that is some conjunction—e.g., minimization—π f ,⊳y ˜ ∧ π⊳y of the goal and constraint possibility distributions. So compared to our approach, the uncertainty or fuzziness is here not expressed on Y but on X , but as in our approach, the important conceptual step in solving the problem is the reformulation as a decision problem. As related by Kaymak and Sousa [12, Sec. 3], in the tradition of Zimmermann [29] an additional step is taken by removing the fuzzy nature of the solution using an extra maximization, i.e., argmaxx∈X π f ,⊳y ˜ (x) ∧ π⊳y (x) is called optimal. This contrasts with our approach when using the maximality criterion, where we explicitly do not try to obtain a unique optimal solution. The Bellman and Zadeh [1]-based approach sketched here is but one end of the spectrum of optimization problems involving possibility distributions in their mathematical formulation [see, e.g., 10, 13, 20]. At the other end of the spectrum, it is not the constraints and the maximization that are fuzzified, but the parameters, i.e., Y is replaced by a fuzzy set ỹ, or, mathematically, a possibility distribution π on Y . Jamison and Lodwick [11] are two of many to do this for linear programming problems; we translate the for this discussion relevant ideas of their paper to our context. As we did in Section 2, their idea is also to first move to an unconstrained optimization problem, but now with a variable penalty factor: maximize f (x) − L⋪ỹ (x)I⋪ỹ (x), where L⋪ỹ is a real-valued function on X that gives the larger a penalty the more severely the constraint is broken. Then a fuzzy number—a possibility distribution on R—G̃x := f (x) − L⋪ỹ (x)I⋪ỹ (x) is associated with every x in X using the extension principle; these can be seen as fuzzy gains. They define the solutions of the problem to be those x with a maximal R mid-point average 12 01 max Gx (t)−min Gx (t) dt, where Gx (t) := {r ∈ R : G̃x (r) ≥ t} is the level set at t. This optimality criterion lies qua idea in between maximinity and maximaxity, but not qua execution, as the way in which we use possibility distributions to express uncertainty differs markedly. 14 ERIK QUAEGHEBEUR, KEIVAN SHARIATMADAR, AND GERT DE COOMAN 7. P RACTICAL EXAMPLES The type of optimization problem we have considered is encountered in many fields and applications. In this section, we give one general practical example problem and two specific ones from the literature. Linear programming problems. This classical optimization problem falls into our standard form in case the constraints’ coefficients are parametrized: maximize cT x subject to A(Y )x ≤ b(Y ), n n where X := R , c ∈ R , b : Y → Rm , and A : Y → Rm×n . Finite element analysis – the loaded beam problem [see, e.g., 14]: minimize the production cost of a beam of length L and cross-section area a by maximizing the amount of less expensive material used, while guaranteeing it can still bear a prescribed load F. We give an illustration with 6 elements: maximize x2 + x4 + x6 subject to ∑6i=1 xi = L, x Da , ∑6i=1 Yii < FL L Y1 Y2 Y3 Y4 Y5 Y6 x1 x2 x3 x4 x5 x6 a F )6 , Y where x is a vector of component lengths in X := (R>0 is an uncertain vector of Young’s moduli taking values in Y ⊂ (R>0 )6 , and D is a limit imposed on the beam’s elongation under maximum design load F. The less expensive material is shown in light gray. Graph theory – the shortest path problem [see, e.g., 18]: find the shortest route between the source and destination nodes s and d in a weighted directed graph—with a set of nodes V and an adjacency matrix A—in which there is uncertainty about the weight attached to some of the edges. Formally, minimize ∑(u,v)∈V 2 Yuv xuv subject to xuv Auv = xuv for all (u, v) in V 2 , ∑v∈V xwv − ∑u∈V xuw = δws − δdw for all w in V , where the optimization variable x belongs to the set of adjacency matrices {0, 1}n×n and Y is an uncertain matrix of edge weights taking values in Y := (R≥0 )n×n . The uncertainty appears in the goal function; we can remedy this by introducing an auxiliary optimization variable component x0 such that X := R≤0 × {0, 1}n×n , leading to an equivalent reformulation in the standard form (cf. Section 2.1): maximize x0 subject to x0 ≤ − ∑(u,v)∈V 2 Yuv xuv and the constraints listed above. 8. C ONCLUSIONS In this paper, we have looked at a specific, but nevertheless very general class of constrained optimization problems and investigated how uncertainty about parameters appearing in the constraints can be dealt with. We have shown that the way forward consists in reformulating the—due to this uncertainty—non-well-posed problem into a well-posed decision problem. We have then restricted our attention to forms of uncertainty that can be represented using coherent lower and upper previsions and presented the general form of the resulting decision problems, one for each of two typical optimality criteria—maximinity and maximality—used in conjunction with such previsions. CONSTRAINED OPTIMIZATION PROBLEMS UNDER UNCERTAINTY WITH COHERENT LOWER PREVISIONS15 Once these two decision problem templates were in place, the question became for which specific types of coherent lower and upper previsions we could solve them to a sufficient degree so as to obtain a constrained optimization problem without uncertainty. We showed that this is generally the case for linear previsions and vacuous previsions. It became clear that using maximinity results in less complicated mathematical problems as compared to the maximality criterion. This observation is given more weight by the fact that, when modeling uncertainty using a possibility distribution, it was straightforward to obtain a general result for maximinity but not for maximality. We encountered similar differences in complexity in preliminary investigations of other popular types of coherent lower previsions, such as those associated with p-boxes [17], and those that are independent products [25] of vacuous and linear previsions as uncertainty models. However, the maximinity criterion can also result in quite complicated expressions, as we encountered when looking at linear-vacuous [25] previsions. Ongoing work [9, 19] consists in investigating whether general results can be found for these and other uncertainty models when we restrict the generality of the initial constrained optimization problem, e.g., to linear programming problems, and testing them on numerical examples. ACKNOWLEDGEMENTS During part of his research on this topic, Erik Quaeghebeur was supported by a Fellowship of the Belgian American Educational Foundation. This research was supported by the IWT SBO project 60043, “Fuzzy Finite Element Method”. We wish to thank the area editor for extensive and useful comments, suggestions, and pointers to the related literature and the reviewers for pointing out where the exposition could be clarified. We also wish to thank Nathan Huntley for alerting us to the possibility of interpretational issues arising when moving uncertainty from the objective function to the constraints. R EFERENCES [1] R. E. Bellman and L. A. Zadeh. Decision-making in a fuzzy environment. Management Science, 17(4):B–141–B–164, 1970. doi:10.1287/mnsc.17.4.B141. [2] Ahoren Ben-Tal and Arkadi Nemirovski. Robust optimization – methodology and applications. Mathematical Programming, 92(3):453–480, 2002. doi:10.1007/s101070100286. [3] Gert de Cooman. Integration and conditioning in numerical possibility theory. Annals of Mathematics and Artificial Intelligence, 32(1):87–123, 2001. [4] Gert de Cooman. A behavioural model for vague probability assessments. Fuzzy Sets and Systems, 154:305–358, 2005. doi:10.1016/j.fss.2005.01.005. With discussion. [5] Gert de Cooman and Dirk Aeyels. Supremum preserving upper probabilities. Information Sciences, 118:173–212, 1999. [6] Bruno de Finetti. Theory of Probability. Wiley, 1974–1975. 2 Volumes. [7] Didier Dubois and Henri Prade. Théorie des possibilités. Masson, 2nd edition, 1988. [8] M. Fiedler, Jiri Nedoma, Jaroslav Ramík, Jiri Rohn, and Karel Zimmermann. Linear Optimization Problems with Inexact Data. Springer, 2006. [9] Nathan Huntley, Rolando Quiñones, Keivan Shariatmadar, Erik Quaeghebeur, Gert de Cooman, and Etienne Kerre. Implementation of maximin and maximal solutions for linear programming problems under uncertainty. Submitted to FLINS 2012. 16 ERIK QUAEGHEBEUR, KEIVAN SHARIATMADAR, AND GERT DE COOMAN [10] Masahiro Inuiguchi and Jaroslav Ramík. Possibilistic linear programming: a brief review of fuzzy mathematical programming and a comparison with stochastic programming in portfolio selection problem. Fuzzy Sets and Systems, 111(1):3–28, 2000. doi:10.1016/S0165-0114(98)00449-7. [11] K. David Jamison and Weldon A. Lodwick. Fuzzy linear programming using a penalty method. Fuzzy Sets and Systems, 119(1):97–110, 2001. doi:10.1016/S01650114(99)00082-2. [12] Uzay Kaymak and João M. C. Sousa. Weighting of constraints in fuzzy optimisation. Constraints, 8:61–78, 2003. [13] Weldon Lodwick and Katherine Bachman. Solving large-scale fuzzy and possibilistic optimization problems. Fuzzy Optimization and Decision Making, 4:257–278, 2005. doi:10.1007/s10700-005-3663-4. [14] Daryl L. Logan. A first course in the finite element method. Chris Carson, 2007. [15] Enrique Miranda. A survey of the theory of coherent lower previsions. International Journal of Approximate Reasoning, 48:628–658, 2008. [16] Enrique Miranda and Gert de Cooman. Epistemic independence in numerical possibility theory. International Journal of Approximate Reasoning, 32:23–42, 2003. doi:10.1016/S0888-613X(02)00087-7. [17] Enrique Miranda, Matthias C. M. Troffaes, and Sébastien Destercke. Generalised pboxes on totally ordered spaces. International Journal of Advances in Soft Computing, pages 235–242, 6 2008. doi:10.1007/978-3-540-85027-4_29. [18] Roberto Montemanni and Luca Maria Gambardella. The robust shortest path problem with interval data via Benders decomposition. 4OR: A Quarterly Journal of Operations Research, 3(4):315–328, 2005. doi:10.1007/s10288-005-0066-x. [19] Erik Quaeghebeur, Nathan Huntley, Keivan Shariatmadar, and Gert de Cooman. Maximin and maximal solutions for linear programming problems with possibilistic uncertainty. Submitted to IPMU 2012. [20] Heinrich Rommelfanger. Fuzzy linear programming and applications. European Journal of Operational Research, 92(3):512–527, 1996. doi:10.1016/0377-2217(95)000089. [21] A. L. Soyster. Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research, 21(5):1154–1157, 9–10 1973. URL http://www.jstor.org/stable/168933. [22] Matthias C. M. Troffaes. Decision making under uncertainty using imprecise probabilities. International Journal of Approximate Reasoning, 45(1):17–29, 5 2007. doi:10.1016/j.ijar.2006.06.001. [23] Matthias C. M. Troffaes and Gert de Cooman. Extension of coherent lower previsions to unbounded random variables. In Proceedings of IPMU 2002, pages 735–742. 2002. [24] Matthias C. M. Troffaes and Gert de Cooman. Lower previsions for unbounded random variables. In P. Grzegorzewski, O. Hryniewicz, and M. Ángeles Gil, editors, Soft Methods in Probability, Statistics and Data Analysis, pages 146–155. PhysicaVerlag, New York, 2002. [25] Peter Walley. Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London, 1991. [26] Peter Walley and Gert de Cooman. Coherence of rules for defining conditional possibility. International Journal of Approximate Reasoning, 21:63–107, 1999. doi:10.1016/S0888-613X(99)00007-9. CONSTRAINED OPTIMIZATION PROBLEMS UNDER UNCERTAINTY WITH COHERENT LOWER PREVISIONS17 [27] Peter Walley and Gert de Cooman. A behavioral model for linguistic uncertainty. Information Sciences, 134(1-4):1–37, 2001. doi:10.1016/S0020-0255(01)00090-1. [28] Peter Whittle. Probability via Expectation. Springer, 3rd edition, 1992. Description and optimization of fuzzy [29] Hans-Jürgen Zimmermann. systems. International Journal of General Systems, 2:209–215, 1975. doi:10.1080/03081077608547470. E-mail address, Erik Quaeghebeur:

URL, Erik Quaeghebeur: http://users.UGent.be/~equaeghe E-mail address, Keivan Shariatmadar:

URL, Keivan Shariatmadar: http://users.ugent.be/~kshariat E-mail address, Gert de Cooman:

URL, Gert de Cooman: http://users.UGent.be/~gdcooma (Keivan Shariatmadar, Erik Quaeghebeur & Gert de Cooman) G HENT U NIVERSITY , SYST E MS R ESEARCH G ROUP , EESA D EPARTMENT , FACULTY OF E NGINEERING , T ECHNOLOGIEPARK -Z WIJNAARDE 914, 9052 Z WIJNAARDE , B ELGIUM