ISSN 09655425, Computational Mathematics and Mathematical Physics, 2014, Vol. 54, No. 3, pp. 429–438. © Pleiades Publishing, Ltd., 2014. Original Russian Text © V.V. Podinovski, 2014, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2014, Vol. 54, No. 3, pp. 415–424. Potential Optimality in Multicriterial Optimization V. V. Podinovski National Research University “Higher School of Economics,” Myasnitskaya 20, Moscow, 101000 Russia email: [email protected] Received May 28, 2013; in final form, October 3, 2013 Abstract—The relation between Pareto, Slater, Geoffrion, and potential optimality is investigated for basic classes of value functions in multicriterial optimization problems. DOI: 10.1134/S0965542514030154 Keywords: multicriterial optimization problems, Pareto optimality, potential optimality. 1. INTRODUCTION The concept of potential optimality was first introduced in the case of the existence of an additive value function, or utility function with unknown parameters and a finite set of solution variants (see, e.g., [1, 2]). The definition of potential optimality with the use of a family of value functions was proposed in [3]. In [4, 5] the concept of potential optimality was introduced without assuming the existence of a value function and without imposing any constraints on the cardinality of the set of variants and the properties of potentially optimal objects of an abstract set with a partial quasiorder were examined in detail. In this paper, we study potential optimality for Pareto optima in multicriteria decisionmaking prob lems. The main results were announced in [6]. 2. BASIC DEFINITIONS AND RESULTS FOR POTENTIAL OPTIMALITY Let the preferences of a decision maker (DM) be described by the nonstrict preference relation R on a set of objects A containing at least two objects: aRb holds if the DM believes that the object а is not less preferable than the object b. Objects a and b are comparable if aRb or bRa holds. The relation R is complete if any two objects are comparable. If R is not complete, it is called partial. The nonstrict preference relation R generates the (strict) preference (P) and indifference (I) relations on A: aPb holds if aRb holds, while bRa does not; alb holds if both aRb and bRa hold. The relation R is a quasiorder, i.e., it is reflexive and tran sitive. Then P is a strict partial order (it is irreflexive and transitive), while I is an equivalence relation (it is reflexive, symmetric, and transitive). Definition 1. An object a* is called optimal (with respect to R) if a*Ra holds for any a ∈ A. Definition 2. An object a0 is called nondominated (with respect to P) if there is no object a ∈ A such that aPa0 holds. Otherwise, a0 is a dominated object (with respect to P). Let A(R) and A( P ) be the set of optimal and nondominated objects, respectively. Note the following assertions: (i) if A(R) is not empty, then all the optimal variants are indifferent and A(R) = A( P ); and (ii) any two nondominated variants either are incomparable or indifferent. Definition 3. The set A( P ) is called externally stable if for any a ∈ A\A( P ) there is b ∈ A( P ) such that bPa holds. If A is a finite set, then A( P ) is externally stable (see, e.g., [7]). A quasiorder R ' (consistently) is said to extend a quasiorder R if R ' ⊃ R (whence I ' ⊇ I) and P ' ⊇ P. Relying on Szpilrajn’s theorem [8, 9] on the extension of a partial order to a linear order, we can state that any partial quasiorder R on A can be extended to a complete quasiorder R '. Let ℵ be the class (set) of all complete quasiorders on A that extend R, and let ℜ be a class (nonempty subset of ℵ) of such com plete quasiorders. Definition 4 (see [4, 5]). An object a* is potentially optimal for the class ℜ if there is a complete quasi order R ' ∈ ℜ for which a* is optimal. An object a* is potentially optimal if it is potentially optimal for the class ℵ. 429 430 PODINOVSKI According to Definition 4, an object a0 is not optimal, i.e., not potentially optimal for the class ℜ if and only if, for any quasiorder R '' ∈ ℜ, there is an object а such that aP ''a0 holds. An object optimal with respect to R is potentially optimal for any class ℜ of complete quasiorders that extend R (including for ℵ). Let A(ℵ) and A(ℜ) be the sets of objects that are potentially optimal (in the class ℵ) and potentially optimal in the class ℜ, respectively. Theorem 1 (see [4, 5]). Every object that is potentially optimal for the class ℜ is nondominated: A(ℜ) ⊆ A( P ). This embedding can be strict. An object is nondominated if and only if it is potentially optimal: A( P ) = A(ℵ). Let us present several new results concerning potential optimality. Definition 5. The set A(ℜ) of potentially optimal objects for the class ℜ is said to cover (a set A) (for this class) if for any object a ∉ A(ℜ) and any quasiorder R ' ∈ ℜ, there is an object a* ∈ A(R ') such that a*P 'a holds. The set of potentially optimal objects for the class ℵ that are covering for ℵ is called covering. The concept of a covering set for potential optimality is an analogue of the concept of an externally sta ble set for nondominance. Theorem 2. The following assertions are true: 2.1. If the set A(R) is not empty, then A(ℜ) = A(R) for any class ℜ. 2.2. Any two potentially optimal objects for the class ℜ are either incomparable or indifferent. 2.3. Suppose that a quasiorder R ' extends a quasiorder R, and let ℜ' and ℜ be the classes of complete quasiorders that extend R ' and R, respectively, and ℜ' ⊆ ℜ. Then A(ℜ') ⊆ A(ℜ). 2.4. If the set A( P ) of nondominated objects is externally stable (this condition holds if the set A is finite), then the set A(ℵ) of potentially optimal objects is covering. 2.5. The external stability of A( P ) does not guarantee the existence of potentially optimal objects for the class ℜ for ℜ ≠ ℵ. 2.6. The set of potentially optimal objects for the class ℜ can be covering even if the set A( P ) is not exter nally stable. The proofs of the theorems that are not presented in the basic text are relegated to the end of this paper. 3. BASIC DEFINITIONS AND SOME RESULTS FROM MULTICRITERIA OPTIMIZATION THEORY Let X be a nonempty set of alternatives (strategies, plans, …). A vector criterion f = ( f1, …, fm), m ≥ 2 is defined on this set. By the criterion fi, we mean a function defined on X and taking values in a set Zi ⊆ Re = (–∞, +∞). Assume that larger values of the criterion are preferable to its smaller values. The vector y = f(x) is called a criterial or vector estimate of an alternative x, and Y = f(X) is called the set of feasible criterial estimates. The set Z = Z1 × … × Zm is the set (of all) criterial estimates. It lies in the mdimensional arith metic space Rem, which is called a criterial space. In multicriterial optimization problems, a fundamental role is played by the (strong) Pareto relation R ≥, which is defined on the set Z as ≥ z'R z'' ⇔ z 'i ≥ z ''i , i = 1, …, m. Note that z'P ≥z'' if at least one of m nonstrict inequalities ≥ is strict, and z'I ≥z'' if all of them hold as equal ities (i.e., I ≥ is the equality relation for vectors from Z). Definition 6. A criterial estimate y0 ∈ Y that is nondominated with respect to the relation P ≥ is called Pareto optimal or effective. The Slater relation, or the weak Pareto relation P > on Z is defined as > z'P z'' ⇔ z i' > z '', i i = 1, …, m. Let R > be the union of P > and the equality relation for vectors from Z. Definition 7. A criterial estimate y0 ∈ Y that is nondominated with respect to the relation P > is called Slater optimal, or weakly Pareto optimal. COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS Vol. 54 No. 3 2014 POTENTIAL OPTIMALITY IN MULTICRITERIAL OPTIMIZATION 431 Definition 8. A Pareto optimal criterial estimate y0 ∈ Y is called Geoffrion optimal, properly Pareto opti 0 mal, or properly effective if there exists a positive number θ(y0) such that, for any estimate y ∈ Y, if yi > y i , 0 then there is an index j ∈ M = {1, …, m) such that yj < y j and 0 yi – yi 0 ≤ θ ( y ). 0 yj – yj Let Y ≥, Y ≥*, and Y > be the sets of criterial estimates that are Pareto, Geoffrion, and Slater optimal, respectively. We have the inclusions Y ≥* ⊆ Y ≥ ⊆ Y >; moreover, all of them can be strict. Note that if the Y is finite, then each Pareto optimal point is Geoffrion optimal [10]. Theorem 3 (see [10]). A criterial estimate y0 ∈ Y is Slater optimal if and only if 0 maxmin ( y i – y i ) = 0. (1) y∈Y i∈M For an arbitrary positive number ε < 1/m, consider vectors μi(ε) of the form ⎧ ε, i ∈ M, i ≠ j, j μi ( ε ) = ⎨ ⎩ 1 – ( m – 1 ), i = j and the corresponding polyhedral cone in Rem: ⎧ m Λ ε = ⎨ u ∈ Re ⎩ m ⎫ ∑ μ ( ε )u ≥ 0, j = 1, …, m ⎬⎭. j i i i=1 Let 0(m) = (0, …, 0) be a zero vector in Rem and 0 m 0 Y – y = { u ∈ Re u = y – y , y ∈ Y }. Theorem 4 (see [10]). A criterial estimate y0 ∈ Y is Geoffrion optimal if and only if there exists a positive number ε < 1/m such that 0 ( Y – y ) ∩ Λε = 0(m) . (2) m m The set Y is called effectively convex if its Edgeworth–Pareto hull Y≤ = Y – Re ≥ , where Re ≥ = {u ∈ m Re |u1 ≥ 0, …, um ≥ 0}, is convex. Theorem 5. Let the set Y be effectively convex. The following assertions hold. 5.1 (see [11, 12]). A criterial estimate y0 ∈ Y is Slater optimal if and only if there exist nonnegative numbers c1, …, cm not all zero such that m ∑ i=1 m 0 c i y i = max y∈Y ∑c y . (3) i i i=1 5.2 (see [13]). A criterial estimate y ∈ Y is Geoffrion optimal if and only if there are positive numbers c1, …, cm that satisfy (3). Remark. If the set Y is polyhedral (and, hence, effectively convex), then the set of Pareto optimal points is equal to the set of Geoffrion optimal points (see, e.g., [10]). 0 4. POTENTIAL OPTIMALITY OF CRITERIAL ESTIMATES ≥ > Let R Y and R Y be the restrictions of the relations R ≥ and R > to the set Y of feasible criterial estimates. ≥ > The relations R Y and R Y are partial quasiorders and can be extended to a complete quasiorder. Denote ≥ > ≥ > by ℜ Y and ℜ Y the classes of all complete quasiorders on Y that extend R Y and R Y , respectively. The fol lowing result is a direct consequence of Theorem 1. COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS Vol. 54 No. 3 2014 432 PODINOVSKI Theorem 6. A criterial estimate y0 ∈ Y is potentially optimal for the class of all complete quasiorders that ≥ ≥ > extend R Y ( R Y ) on Y if and only if it is Pareto optimal (Slater optimal): Y( ℜ ) = Y ≥ (Y(ℜ>) = Y >, respec tively). However, a Pareto optimal criterial estimate may not be potentially optimal for a certain class. A suit able example can be found in [14]. The function ϕ(z) is called increasing with respect to P ≥ (with respect to P >) on Z if z'P ≥z'' ⇒ ϕ(z') > ϕ(z'') (z'P >z'' ⇒ ϕ(z') > ϕ(z''), respectively). Each such function generates a complete quasiorder R ϕ on Z: ϕ z'R z'' ⇔ ϕ ( z' ) ≥ ϕ ( z'' ), so that the set of its maximizers on Y is equal to the set of points that are optimal with respect to the cor ϕ ϕ ϕ responding relation R Y , the restriction of R ϕ to Y. Let ℜ ≥ (respectively, ℜ > ) be the class (set) of complete quasiorders generated on Y by all functions ϕ continuous and increasing with respect to P ≥ (with respect to P >, respectively) on Z (and, hence, on Y). Such functions are extensively used in methods for solving ϕ multicriteria problems. Accordingly, an issue of practical interest is potential optimality for the classes ℜ ≥ ϕ ϕ ϕ ϕ ϕ and ℜ > . Note that ℜ ≥ ⊂ ℜ > . Let Y( ℜ ≥ ) and Y( ℜ > ) denote the sets of potentially optimal criterial esti ϕ ϕ mates for the classes ℜ ≥ and ℜ > , respectively. ϕ Theorem 7. A criterial estimate y0 ∈ Y is Slater optimal if and only if it is potentially optimal for the class ℜ > ; ϕ i.e., Y( ℜ > ) = Y >. By using the function ϕ Π ( z b ) = min ( z i – b i ), (4) i∈M where b ∈ Z, the lexicographic order R lex(b) on Z is defined as m ⎛ m ⎞ lex z'R ( b )z'' ⇔ [ ϕ Π ( z' b ) > ϕ Π ( z'' b ) ] ∨ ( ϕ Π ( z' b ) = ϕ Π ( z'' b ) ) ∧ ⎜ z i' ≥ z ''i ⎟ . ⎝i = 1 ⎠ i=1 ∑ ∑ The quasiorder R lex(b) is complete and extends R ≥ on Z. lex Theorem 8. A Pareto optimal criterial estimate y0 ∈ Y is optimal with respect to the quasiorder R Y (y0). This theorem is a constructive illustration of Theorem 1 as applied to multicriterial optimization prob lems. ϕ Theorem 9. A Pareto optimal criterial estimate may not be potentially optimal for the class ℜ ≥ ; i.e., the ϕ embedding Y( ℜ ≥ ) ⊆ Y ≥ can be strict. The validity of Theorem 9 is proved by the following example. Example 1. Let m = 2, Z = Re2, and Y be the set shown in Fig. 1. Note that y0 ∈ Y and z* ∉ Y. The point y0 is Pareto optimal. Let ϕ be an arbitrary fixed function that is continuous and increasing with respect to P ≥ on Re2. Assume that y0 is a maximizer of ϕ on Y. Since z*P ≥y0, we have ϕ(z*) > ϕ(y0). Since ϕ is continuous, there is a point y* ∈ Y such that ϕ(z*) – ϕ(y*) < ϕ(z*) – ϕ(y0). This implies the inequality ϕ(y*) > ϕ(y0), which contradicts the assumption that y0 is a maximizer of ϕ on Y. Since ϕ is an arbitrary fixed function that is continuous and increasing with respect to P ≥ on Re2, it follows that y0 is not potentially optimal for ℜ≥. In this example, the criterial estimate y0 is Pareto optimal but not Geoffrion optimal. This is not ran dom, since the following result is true. ϕ ϕ Theorem 10. A Geoffrion optimal criterial estimate is potentially optimal for the class ℜ ≥ ; i.e., Y ≥* ⊆ Y( ℜ ≥ ). This embedding can be strict. According to Theorem 10, a potentially optimal criterial estimate y0 ∈ Y for the class ℜ≥ may not be Geoffrion optimal. COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS Vol. 54 No. 3 2014 POTENTIAL OPTIMALITY IN MULTICRITERIAL OPTIMIZATION 433 z2 z* y* Y y0 z1 0 Fig. 1. The set Y. z2 2 1 ϕ(z) = 4/5 Y≥ Y y0 0 1 z1 Fig. 2. The set Y and a level line of the function ϕ. 2 2 2 2 Example 2. Let m = 2, Z = Re + = {z ∈ Re2|z1 ≥ 0, z2 ≥ 0}, and Y = {z ∈ Re + z 1 + z 2 ≤ 1} (see Fig. 2). 2 2 The point y0 = (1, 0) is Pareto optimal, but not Geoffrion optimal. The function ϕ(z) = 4z 1 + z 2 is con tinuous and increasing with respect to P ≥ on Z. Its level line through the point y0 is given by the equation 2 2 4z 1 + z 2 = 4 and is shown in Fig. 2. It is easy to see that ϕ reaches a maximum on Y at the single point y0. ϕ Therefore, this point is potentially optimal in the class ℜ ≥ . L L L L Let ℜ >0 ( ℜ ≥0 ) be the class of complete quasiorders R >0 ( R ≥0 , respectively) generated on Z by all functions m L(z c) = ∑c z , (5) i i i=1 where every ci > 0 (all ci ≥ 0 and at least one ci > 0, respectively): L z'R >0 z'' ⇔ L ( z' c ) ≥ L ( z'' c ) L (respectively z'R ≥0 z'' ⇔ L ( z' c ) ≥ L ( z'' c ) ). Each such function is increasing with respect to P ≥ (with respect to P >, respectively) and is continuous L L on Rem. Note that ℜ >0 ⊂ ℜ ≥0 . The result below is a direct consequence of Theorem 5. COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS Vol. 54 No. 3 2014 434 PODINOVSKI Theorem 11. Let the set Y be effectively convex. Then the following assertions hold: L 1. A criterial estimate y0 ∈ Y is Geoffrion optimal if and only if it is potentially optimal for the class ℜ >0 ; L L L i.e., Y ≥* = Y( ℜ >0 ). If the set Y is closed and bounded above, then Y( ℜ >0 ) is a covering set for ℜ >0 . L 2. A criterial estimate y0 ∈ Y is Slater optimal if and only if it is potentially optimal for the class ℜ ≥0 ; i.e., L L L Y > = Y( ℜ ≥0 ). If the set Y is closed and bounded above, then Y( ℜ ≥0 ) is a covering set for ℜ ≥0 . Theorem 12. Let the set Y be polyhedral. A criterial estimate is Pareto and Geoffrion optimal if and only if L L L it is potentially optimal for the class ℜ >0 ; i.e., Y > = Y ≥* = Y( ℜ >0 ). If the set Y is bounded above, then Y( ℜ >0 ) L is a covering set for ℜ >0 . 5. POTENTIAL OPTIMALITY OF ALTERNATIVES ≥ > On a set of alternatives X, the Pareto R ≥ and Slater R > relations generate relations R X and R X , which are called the same as before: ≥ ≥ x'R X x'' ⇔ f ( x' )R f ( x'' ); > > x'R X x'' ⇔ f ( x' )R f ( x'' ). If the criterial estimate f(x) of an alternative x is Pareto optimal (Slater optimal, or Geoffrion optimal) or potentially optimal for some class of functions, then the alternative x is called Pareto optimal (Slater opti mal, or Geoffrion optimal, respectively) or potentially optimal in this class. Let X ≥, X ≥*, and X > be the respective sets of Pareto, Geoffrion, and Slater optimal alternatives. The above results for criterial estimates can be extended to alternatives (see [10]). We introduce the fol lowing notation: ≥ ≥ > > ℜ X and ℜ X are the classes of all complete quasiorders on X that extend R X and R X , respectively. ≥ > X(ℜ≥) and X(ℜ>) are the sets of potentially optimal alternatives for the classes R X and R X , respectively. ϕ≥ ϕ> ϕ ϕ ϕ≥ ϕ> L L R X and R X are the complete quasiorders generated on X by the quasiorders R ≥ and R > , respec ϕ≥ ϕ ϕ> ϕ tively: x'R X x'' ⇔ f ( x' )R ≥ f ( x'' ) and x'R X x'' ⇔ f ( x' )R > f ( x'' ) . ϕ≥ ϕ> ϕ≥ ϕ> ℜ X and ℜ X are the classes of complete quasiorders R X and R X , respectively. ϕ≥ ϕ> X( ℜ ) and X( ℜ ) are the sets of potentially optimal alternatives for the classes ℜ X and ℜ X , respec tively. L >0 L ≥0 R X and R X are the complete quasiorders generated on X by the quasiorders R >0 and R ≥0 , respec L >0 L L≥ L tively: x'R X x'' ⇔ f ( x' )R >0 f ( x'' ) and x'R X x'' ⇔ f ( x' )R ≥0 f ( x'' ) . L >0 L >0 L >0 L ≥0 ℜ X and ℜ X are the classes of complete quasiorders R X and ℜ X , respectively. L >0 X( ℜ ) and X( ℜ respectively. L ≥0 L >0 ) are the sets of potentially optimal alternatives for the classes ℜ X L >0 and ℜ X , ≥ Theorem 13. An alternative is potentially optimal for the class of all complete quasiorders that extend ℜ X > ( ℜ X ) on X if and only if it is Pareto optimal (Slater optimal, respectively): X(ℜ≥) = X ≥ (X(ℜ>) = X >, respec tively). ϕ> Theorem 14. An alternative is Slater optimal if and only if it is potentially optimal for the class ℜ X , i.e., ϕ≥ X( ℜ ) = X >. COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS Vol. 54 No. 3 2014 POTENTIAL OPTIMALITY IN MULTICRITERIAL OPTIMIZATION 435 ϕ≥ Theorem 15. A Pareto optimal alternative may not be potentially optimal for the class ℜ X ; i.e., the embed ϕ≥ ding X( ℜ ) ⊆ X ≥ can be strict. ϕ≥ ϕ≥ Theorem 16. A Geoffrion optimal alternative is potentially optimal for the class X( ℜ ); i.e., X ≥* ⊆ X( ℜ ). This embedding can be strict. Theorem 17. Let the set X be convex and all the criteria fi be concave functions. Then the following asser tions hold: L >0 1. An alternative is Geoffrion optimal if and only if it is potentially optimal for the class ℜ X ; i.e., X ≥* = X( ℜ L >0 ). If the set X is compact and all the criteria fi are continuous functions, then X( ℜ for the class L >0 ) is a covering set L >0 ℜX . L >0 2. An alternative is Slater optimal if and only if it is potentially optimal for the class ℜ X ; i.e., X > = X( ℜ L ≥0 ). If the set X is compact and all the criteria fi are continuous functions, then X( ℜ for the class L ≥0 ) is a covering set L >0 ℜX . Theorem 18. Let the set X be polyhedral and all the criteria fi be linear functions. An alternative is Pareto L >0 and Geoffrion optimal if and only if it is potentially optimal for the class ℜ X ; i.e., the double equality X > = X ≥* = X( ℜ L >0 ) holds. If the set X is compact, then X( ℜ L >0 L >0 ) is a covering set for ℜ X . 6. PROOFS OF THE THEOREMS Proof of Theorem 2. First, we show the validity of assertion 2.1. Let A(R) ≠ ∅. Then it is easy to see that A(R) = A( P ). Therefore, in view of Theorem 1, A(ℜ) ⊆ A(R). It remains to prove the reverse inclusion A(ℜ) ⊇ A(R). Let a* ∈ A(R). Then, for any a ∈ R, it holds that a*Ra. Let R ' be any complete quasiorder that extends R. Then a*R 'a holds, so that a* is optimal with respect to R '. Therefore, a* is potentially optimal for any class ℜ; i.e., a* ∈ A(ℜ). To prove assertion 2.2, we assume that a and b are two potentially optimal objects for some class ℜ. The relation aPb cannot hold; otherwise, aP 'b would hold for any complete quasiorder from ℜ, which con tradicts the potential optimality of b. In a similar fashion, we can show bPa does not hold either. Then the following two possibilities stay: aIb and aNb. Now we prove assertion 2.3. Let a* ∈ A(ℜ'). This means that there is a complete quasiorder R " in the class ℜ' such that, for any a ∈ A, it holds that a*R ''a. Since R '' extends R ', while R ' extends R, it is easy to see that R '' extends R. Since ℜ' ⊆ ℜ, it follows that R '' ∈ ℜ. Therefore, a* ∈ A(ℜ). Let us prove assertion 2.4. Suppose that the set A( P ) is externally stable. Then, according to Definition 3, for any object a ∈ A\A( P ), there is b ∈ A( P ) such that bPa holds. Therefore, for any complete quasiorder R ' that extends R, we have bP 'a. By Theorem 1, A( P ) = A(ℵ). Therefore, according to Definition 5, A(ℵ) is a covering set. The validity of assertion 2.5 is proved by the following example. The set A = Y for a twocriteria problem with Z = Re2 is shown in Fig. 3: this is the curved triangle without vertices at y* and y**. The relation R is defined by the Pareto relation R ≥. Here, the set of nondominated points with respect to P ≥ is the arc with out the endpoints z* and z**. This set is externally stable. However, the set of potentially optimal points L for the class ℜ > is empty. The following example proves the validity of assertion 2.6. The set A = Y for a twocriteria problem with Z = Re2 is presented in Fig. 4: this is the curved triangle without the arc side with the endpoints y* and y**, which themselves belong to Y. The relation R is defined by the Pareto relation R ≥. Here, the set of non dominated points with respect to P ≥ consists of y* and y** and is not externally stable. These two points L make up the set of potentially optimal points for the class ℜ > . Obviously, this set is covering. COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS Vol. 54 No. 3 2014 436 PODINOVSKI z2 c'' y** c' Y z1 z* 0 Fig. 3. The set Y ≥ is externally stable. z2 c'' y** c' Y y* z1 0 Fig. 4. The set Y ≥ is not externally stable. Proof of Theorem 7. If y0 ∈ Y is a potentially optimal point for the class ℜ>, then, by Theorem 1, it is Slater optimal. Now let the point y0 ∈ Y be Slater optimal. The complete quasiorder R ϕ generated on Z by function (4) with b = y0 extends R > on Z. By Theorem 3, y0 is a maximizer of function (4) on Y. There ϕ fore, y0 is optimal with respect to R Y and, hence, potentially optimal for the class ℜ>. Proof of Theorem 8. Let y0 ∈ Y be a Pareto optimal point. Since R > ⊂ R ≥, it is also weakly Pareto opti 0lex 0 mal. Consider an arbitrary point y ∈ Y. Assume that yP Y y holds. By Theorem 3, the inequality ϕΠ(y|y0) > ϕΠ(y0|y0) cannot be satisfied. Therefore, ϕΠ(y|y0) = ϕΠ(y0|y0) = 0 and m m ∑y > ∑y . 0 i i i=1 (5) i=1 The equality ϕΠ(y|y0) = 0 implies that 0 yi ≥ yi , i = 1, …, m. (6) In view of (5), at least one of the inequalities in (6) is strict, which contradicts the assumption that y0 is lex 0 0 lex 0 Pareto optimal. Consequently, y P Y ( y )y holds. Therefore, y0 is optimal with respect to R Y ( y ) . Proof of Theorem 10. Let y0 ∈ Y ≥ be a Geoffrion optimal point. Then, by Theorem 4, there is a positive number ε < 1/m such that (2) holds. Consider the function m ϕ ( u μ ( ε ), b ) = min j∈M ∑ μ ( ε ) ( u – y ), j i i 0 i (7) i=1 COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS Vol. 54 No. 3 2014 POTENTIAL OPTIMALITY IN MULTICRITERIAL OPTIMIZATION 437 where ε < 1/m. It is continuous and increasing with respect to P ≥ on Z. Its level hypersurface defined by the equation ϕ(u|μ(ε), 0(m)) = 0 coincides with the boundary of the cone Λε. It is easy to see that y0 is a ϕ maximizer of function (7) on Y and, hence, optimal with respect to the complete quasiorder R Y gener ated on Y by this function. Therefore, the point y0 is potentially optimal for ℜ≥. Proof of Theorem 11. The first part of assertion 1 in Theorem 11 is a direct consequence of assertion 2 in Theorem 5. Let the set Y be closed and bounded above, and let y ∈ Y. The set {z ∈ Y|zR ≥y} is nonempty and compact. Therefore, for arbitrary fixed positive numbers c1, …, cm, function (5) reaches a maximum L on this set at some point y*. This point is optimal for the complete quasiorder R >0 generated on the indi L L L cated function; moreover, y*R >0 y holds. Therefore, Y( ℜ >0 ) is a covering set for the class ℜ >0 . The first part of assertion 2 in Theorem 11 is a direct consequence of assertion 1 in Theorem 5. The second part is proved in the same manner as the second part of assertion 1 in Theorem 11. Proof of Theorem 12. The remark made after Theorem 5 shows that Theorem 12 is a simple conse quence of assertion 1 in Theorem 11. Proof of Theorem 13. This theorem is a direct consequence of Theorem 6. Proof of Theorem 14. This theorem is a direct consequence of Theorem 7. Proof of Theorem 15. This theorem is a direct consequence of Theorem 9. Proof of Theorem 16. This theorem is a direct consequence of Theorem 10. Proof of Theorem 17. If the set X is convex and all the criteria fi are concave functions, then the set Y is effectively convex (see [10]). If the set X is compact and all the criteria fi are continuous functions, then the set Y is compact. Therefore, Theorem 17 is a direct consequence of Theorem 11. Proof of Theorem 18. If the set X is polyhedral and all the criteria fi are linear functions, then the set Y is polyhedral (see [15]). If the polyhedral set X is bounded, then it is compact. Therefore, Theorem 18 is a direct consequence of Theorem 12. 7. CONCLUSIONS Potential optimality is a fundamental concept in decision theory. It is operational, for example, in the analysis of multicriterial choice problems, including ones with a hierarchical criterial structure, by itera tive methods providing stepwise development of a mathematical preference model. The results obtained in this paper uncover the relation between nondominance and potential optimal ity in multicriterial optimization problems. Additionally, they show that methods for constructing sets of Pareto, Slater, or Geoffrion optimal alternatives can be used (with certain constraints) to construct sets of potentially optimal alternatives for corresponding classes of complete quasiorders, specifically, for con cave and linear multicriterial problems. ACKNOWLEDGMENTS This work was performed in the framework of the Program “Scientific Foundation of the National Research University Higher School of Economics” in 2013, project no. 12010059. REFERENCES 1. G. B. Hazen, “Partial information, dominance, and potential optimality in multiattribute utility theory,” Operat. Res. 34, 296–310 (1986). 2. E. S. Eum, K. S. Park, and S. H. Kim, “Establishing dominance and potential optimality in multicriteria deci sion analysis with imprecise weight and value,” Comput. Operat. Res. 28, 397–409 (2001). 3. D. J. White, “Notes in decision theory: Optimality and efficiency II,” Eur. Operat. Res. 4, 426–427 (1980). 4. V. V. Podinovski, “On the relation of the notions of potential optimality and nondominance,” Autom. Remote Control 73, 167–170 (2012). COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS Vol. 54 No. 3 2014 438 PODINOVSKI 5. V. V. Podinovski, “Nondominance and Potential Optimality for Partial Preference Relations,” Eur. Operat. Res. 229, 482–486 (2013). 6. V. V. Podinovski, “Potential optimality of Pareto optima,” Proc. Comput. Sci. 17, 1107–1112 (2013). 7. A. V. Lotov and I. I. Pospelova, Multicriterial Decision Making Problems (MAKS, Moscow, 2008) [in Russian]. 8. E. Szpilrajn, “Sur l’extension de l’ordre partiel,” Fundam. Math. 16, 386–389 (1930). 9. L. Fuchs, Partially Ordered Algebraic Systems (Pergamon, Oxford, 1963; Mir, Moscow, 1965). 10. V. V. Podinovski and V. D. Noghin, Pareto Optimal Solutions of Multicriterial Problems (Fizmatlit, Moscow, 1982) [in Russian]. 11. S. Karlin, Mathematical Methods and Theory in Games, Programming, and Economics (Dover, New York, 1959; Mir, Moscow, 1964). 12. P. L. Yu, “Cone convexity, cone extreme points, and nondominated solutions in decision problems with multi objectives,” J. Optim. Theory Appl. 14, 319–377 (1974). 13. A. M. Geoffrion, “Proper efficiency and the theory of vector maximization,” J. Math. Anal. Appl. 22, 618–630 (1968). 14. D. RiosInsua and S. French, “A framework for sensitivity analysis in discrete multiobjective decisionmak ing,” Eur. J. Operat. Res. 5, 176–190 (1991). 15. R. Rockafellar, Convex Analysis (Princeton Univ. Press, Princeton, 1970; Mir, Moscow, 1973). Translated by I. Ruzanova SPELL: OK COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS Vol. 54 No. 3 2014

© Copyright 2019 ExploreDoc