Potential Optimality in Multicriterial Optimization

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

Download Report