An Application of the Maximum Theorem in Multi-Criteria Optimization, Properties of Pareto-Retract Mappings, and the Structure of Pareto Sets ()
1. Introduction
The Berge Maximum Theorem, shortly the Maximum Theorem, has become one of the most useful and powerful theorems in optimization theory, mathematical economics and game theory. The original variant of the Maximum Theorem is as follows:
Theorem 1 [1] [2, Theorem 9.14]. Let
and
,
be a continuous function, and
be a compact-valued and continuous multifunction. Then, the function
defined by
is continuous on X, and the multifunction
defined by
is compact-valued and upper semi-continuous on X.
The Maximum Theorem is often used in a special situation when the multifunction D is convex-valued and the function u is quasi-concave or concave in its second variable in addition to the hypotheses of Theorem 1.
Now, we give a presentation of the classical variant of the Maximum Theorem.
Theorem 2 [2, Theorem 9.17 and Corollary 9.20]. Let
and
,
be a continuous function, and
be a compact-valued and continuous multifunction. Define m and S as in Theorem 1.
(a) Then m is a continuous function on X, and S is a compact-valued and upper semi-continuous multifunction on X.
(b) If
is quasi-concave in y for each
, and D is convex-valued, then S is convex-valued.
(c) If
is strictly quasi-concave in y for each
, and D is convex-valued, then S is a continuous function on X.
(d) If u is concave on
, and D has a convex graph, then m is a concave function on X and S is a convex-valued multifunction on X.
(e) If u is strictly concave on
, and D has a convex graph, then m is a strictly concave and continuous function on X, and S is a continuous function on X.
Remark 1. It is important to note the following two facts [2, Example 9.15 and 9.16]:
(1) S is only upper semi-continuous, and not necessarily also lower semi-continuous.
(2) The continuity of u on
cannot be replaced with one of separate continuity, i.e., that
is continuous on X for each fixed
and that
is continuous on Y for each fixed
.
Let us consider Theorem 2. It is possible to have
for all
. Obviously, the following theorem is true.
Theorem 3. Let
and
,
be a continuous function, and
be a compact-valued and continuous multifunction. Define m and S as in Theorem 1. If
for all
, then m and S are two continuous function on X.
2. Basic Concepts and Definitions
It is easy to show that Theorems 1, 2 and 3 imply the following two theorems.
Theorem 4. Let
,
be a continuous function, and
be a continuous multifunction. Then, the function
defined by
is continuous on X, and the multifunction
defined by
is upper semi-continuous on X.
Theorem 5. Let
,
be a continuous function, and
be a continuous multifunction. Define m and S as in Theorem 4. If
for all
, then m and S are two continuous function on X.
Now we will apply these two theorems to multi-criteria optimization.
The general form of the multi-criteria unconstrained optimization problem is to find a variable
,
, so as to maximize
subject to
, where the feasible domain X is nonempty and compact,
is the index set,
,
is a given objective continuous function for all
.
Now we will introduce several solution concepts for our multi-criteria optimization problem.
Definition 1.
(a) A point
is called an ideal Pareto-optimal solution if and only if
for all
and all
. The set of the ideal Pareto-optimal solutions of X is denoted by
and is called an ideal Pareto-optimal set.
(b) A point
is called a Pareto-optimal solution if and only if there does not exist a point
such that
for all
and
for some
. The set of the Pareto-optimal solutions of X is denoted by
and is called a Pareto-optimal set. Its image
is called a Pareto-front set.
(c) A point
is called a strictly Pareto-optimal solution if and only if there does not exist a point
such that
for all
and
. The set of the strictly Pareto-optimal solutions of X is denoted by
and is called a strictly Pareto-optimal set.
The above definition qualifies Pareto-optimal solutions in the global sense.
In literature, the term Pareto-optimal is frequently used synonymously with efficient, non-inferior and non-dominated.
In our optimization problem, it can be shown that:
is nonempty, but
and
may be empty;
and
, see also [3-5].
Remark 2. It is well-known that
when
is nonempty [6].
Usually, a Pareto-optimal solution is not necessarily uniquely determined, but there are several Pareto-optimal solutions.
For a better understanding of this paper, we recall some useful notations and definitions.
To be precise, we introduce the following notations: for every two vectors
,
means
for all
,
means
for all
(weakly component-wise order),
means
for all
(strictly component-wise order), and
means
for all
and
for some
(component-wise order).
Remark 3. Let X and Y be two topological spaces. A homotopy between two continuous functions
is defined to be a continuous function
such that
and
for all
. Note that we can consider the homotopy H as a continuously deformation of f to g [7].
Definition 2.
(a) The set
is a retract of X if and only if there exists a continuous function
such that
for all
. The function r is called a retraction of X to Y.
(b) The set
is a deformation retract of X if and only if there exist a retraction
and a homotopy
such that
and
for all
.
Remark 4. From a more formal viewpoint, a retraction is a function
such that
for all
, since this equation says exactly that r is the identity on its image. Retractions are the topological analogs of projection operators in other parts of mathematics. It is true that every deformation retract is a retract, but in generally the converse does not hold [7].
Applications of retractions in multi-criteria optimization have been discussed by several authors [3,8-12].
We are now ready to define:
1) A multifunction
by
for all
.
2) A multifunction
by
for all
.
3) A function
by
for all
.
Note that, for each
,
is equal to the intersection of all the upper contour sets and
is equal to the intersection of all the level sets. Clearly,
for all
.
Remark 5. From Definition 1 it is easy directly verify that for
:
(1)
is equivalent to
(or equivalently
).
(2)
is equivalent to
.
Choose
and consider an optimization problem with a single objective function as follows: 1) Maximize
subject to
or 2) maximize
subject to
. By letting x vary over all of X we can identify different Pareto-optimal solutions. This optimization technique will allow us to find the whole Paretooptimal set and analyze its structure.
Remark 6. It is known that
for all
[6].
The above remark allows us to present a new definition.
Definition 3.
(a) A multifunction
is a called Pareto-retract (Pareto-retract point-to-set mapping) if and only if
for all
.
(b) A function
is called a Paretoretract (Pareto-retract point-to-point mapping) if and only if
for all
.
Thus we introduce the concept of the Pareto-retract mappings. Here the fundamental idea is based on the observation that for any
which is not Paretooptimal there exists at least one other
such that
for all
and strictly inequality holds at least once.
According to Remark 6, one can see that there exists a Pareto-retract multifunction, but an open problem is its continuity (lower or upper semi-continuous).
3. Assumptions and Theorems in the General Case
In this section, we will discuss the role of the following assumptions that affect the characteristics of a Paretoretract mapping (Pareto-retract multifunction and Paretoretract function) if the feasible domain X is compact:
Assumption 1.
is lower semi-continuous on X.
Assumption 2a.
for all
.
Assumption 2b. There exists
such that
for all
.
Note that if Assumption 2a holds, then there exists a Pareto-retract function, see also Remark 6. Again, an open problem is its continuity.
These assumptions allow us to present our theorems of this section.
Theorem 6.
is upper semi-continuous on X.
Proof. We will prove that if
and
are a pair of sequences such that
and
for all
, then there exists a convergent subsequence of
whose limit belongs to
.
The assumption
for all
implies
for all
. From the condition
it follows that there exists a convergent subsequence
such that
. Therefore, there exists a convergent subsequence
such that
and
. Thus, we find that
for all
. Taking the limit as
we obtain
, i.e.
. This means that
is upper semi-continuous on X.
The theorem is proven.
We are now ready to prove the following basic theorem.
Theorem 7. If Assumption 1 holds, then:
(a)
is continuous on X.
(b) There exists an upper semi-continuous Pareto-retract multifunction.
(c)
and
are compact.
Proof.
(a) Assumption 1 and Theorem 6 imply that
is continuous on X.
(b) According Remark 6 we are in a position to construct a multifunction
such that
for all
. It is easy to show that
for
. This means that
.
The function s is continuous and the multifunction
is compact-valued and continuous. Now applying Theorem 4, we conclude that
is an upper semi-continuous multifunction on the compact domain X.
(c) We recall that X is compact; therefore, part (b) implies that
is compact too. Trivially,
is compact.
The theorem is proven.
Remark 7. Let Assumption 1 be satisfied. Remark 1 shows that the multifunction
is not necessarily lower semi-continuous.
Theorem 8. If Assumption 2a or 2b holds, then
.
Proof. It is well-known that
.
Let
and assume that
. From the fact that
it follows that there exists
such that
for all
and
. Hence,
.
There are two cases:
(1) If Assumption 2a holds, then there exists a unique
such that
for all
. But we get that
and
. This means that
,
and
for all
. As a result we obtain
for all
and
for some
. This leads to a contradiction.
(2) If Assumption 2b holds, then there exists a unique
such that
for all
. But we know that
for all
and
. This means that
,
for all
and
. This leads to a contradiction too.
Finally, we obtain
.
The theorem is proven.
Remark 8. While studying the proof of Theorem 8, one can see that if
and
, then
.
Theorem 9. If Assumptions 1 and 2a (or 1 and 2b) hold, then:
(a) There exists a continuous Pareto-retract function.
(b)
is homeomorphic to
.
Proof. (a) First, let Assumptions 1 and 2a be satisfied. In this case, we construct a function
such that
for all
. From Theorems 5, 7 and 8, and Remark 6 it follows that r is a continuous Pareto-retract function.
For the second part of this proof, let Assumptions 1 and 2b be satisfied. Now we construct a function
such that
for all
. From Theorems 5, 7 and 8, and Remark 8 it follows that r is a continuous Pareto-retract function.
(b) Recalling that the function
is continuous; therefore, a restriction
of f is continuous too. From Remark 5 and Theorem 8 we have that the function h is bijective. Consider the inverse function
of h. We proved in Theorem 7 that
is compact; therefore,
is continuous too [13]. As a result we conclude that the function h is homeomorphism.
The theorem is proven.
Remark 9. From Theorem 9 we can easily check the following:
(1) For each
,
is nonempty compact and
.
(2) If
and
, then
.
(3)
.
(4) By Assumption 2a, for each
we have
and
for all
.
(5) By Assumption 2b, for each
we have
and
for all
.
4. Structure of Pareto Sets
The structure of Pareto sets is very important, from an algorithmic point of view.
Let
be the Euclidean metric in
and
be the topology induced by
. In a topological space
, for
we now recall some general topological definitions.
Definition 4. A property is called a topological property if and only if an arbitrary topological space X has this property, then Y has this property too, where Y is homeomorphic to X.
Definition 5.
(a) The set Y is connected if and only if it is not the union of a pair of nonempty sets of
, which are disjoint.
(b) The set Y is path-wise connected if and only if for every
there exists a continuous function
such that
and
. The function p is called a path.
(c) The set Y is simply connected if and only if it is path-wise connected and every path between two points can be continuously deformed into every other.
(d) The set Y is contractible (contractible to a point) if and only if there exists a point
such that
is a deformation retract of Y.
Remark 10. Recalling that the following statements are true:
(1) Convexity implies contractibility, contractibility implies simply connectedness, simply connectedness implies path-wise connectedness, and path-wise connectedness implies connectedness. However, in general the converse does not hold.
(2) Contractibility, simply connectedness, path-wise connectedness and connectedness are topological properties of sets.
(3) Compactness, path-wise connectedness and connectedness of sets are preserved under a continuous function.
(4) Compactness, connectedness, path-wise connectedness, simply connectedness and contractibility of sets are preserved a under retraction.
(5) The image of a simply connected set under a continuous function need not to be simply connected.
(6) The image of a convex set under a retraction need not to be convex.
Remark 11. We now focus our attention to contractibility of sets. Let
. Remark 10 has shown that if Y is a retract of X and X is contractible, then Y is contractible too. The converse does not hold in generally. But for every deformation retract the following statement is true: “If Y is a deformation retract of X, then Y is contractible if and only if X is contractible.”
Definition 6.
(a) The topological space Y is said to have the fixed point property if and only if every continuous function
from this set into itself has a fixed point, i.e. there is a point
such that
.
(b) The topological space Y is said to have the Kakutani fixed point property if and only if every upper semi-continuous multifunction
from this set into itself has a fixed point, i.e. there is a point
such that
.
(1) Remark 12. We will use the following statements for each compact set:
Convexity implies the fixed point properties (fixed point property and Kakutani fixed point property).
(2) The fixed point properties of sets are topological properties.
(3) The fixed point properties of sets are preserved under retraction.
(4) A set having the fixed point property is equivalent to this set having the Kakutani fixed point property.
Now we focus our attention on the compactness, connectedness, contractibility and fixed point properties of the Pareto sets. Compactness of these sets is studied in [3,8,12,14-16]. Connectedness is considered in [3,6,8, 16-24]. Contractibility of Pareto sets is discussed in [9, 10,12,25]. Fixed point properties have been addressed in [10,12,26].
Corollary 1. If Assumptions 1 and 2a (or 1 and 2b) hold, then:
(a) If X is convex, then
and
are contractible and have the fixed point properties.
(b) If X is contractible, then
and
are contractible.
(c) If X is simply connected, then
and
are simply connected.
(d) If X is path-wise connected, then
and
are path-wise connected.
(e) If X is connected, then
and
are connected.
(f) If X has the fixed point properties, then
and
have the fixed point properties.
Proof. Directly, from Theorem 9, Remarks 10 and 12 imply the proof.
5. Convex Case
We often use the Maximum Theorem under convexity as a mathematical tool in convex optimization. Here we will present two special variants of this theorem and their applications to convex multi-criteria optimization.
In this section, we are going to study our optimization problem when the functions
are concave and a function
of
is strictly quasi-concave on the compact and convex domain X.
Concavities of the objective functions play a central role in optimization theory, for more information see [27] and [28]. We will use the definitions of quasi-concave and concave functions in the usual sense.
Definition 7. A real function g on a convex subset
is called to be:
(a) Quasi-concave on X if and only if for any
and
, then
.
(b) Strictly quasi-concave on X if and only if for any
,
and
, then
.
(c) Concave on X if and only if for any
and
, then
.
Now, from Theorems 2 and 4 we get the first special variant of the Maximum Theorem under convexity.
Theorem 10. Let
,
be a continuous function, and
be a continuous multifunction. Define m and S as in Theorem 4. If u is quasiconcave on X and D is convex-valued, then S is a convex-valued and upper semi-continuous multifunction on X.
Remark 13. If
are all quasi-concave and one of them is strictly quasi-concave, then
[3,6].
We are ready to prove the first theorem in this section.
Theorem 11. Let
be all concave on the compact and convex domain X. Then:
(a)
is convex-valued and continuous on X. In particular, Assumption 1 holds.
(b) There exists an upper semi-continuous Pareto-retract multifunction.
(c)
and
are compact.
(d)
is convex when
.
(e)
for all
.
(f) There exists a continuous function
such that
. In particular,
is path-wise connected.
Proof. (a) Define a multifunction
such that
for all
. It is easy to show that the multifunction
is convex-valued.
We will prove continuity of
on X using a two-step procedure.
Step 1. We will prove that if
and
are a pair of sequences such that
and
for all
, then there exists a convergent subsequence of
whose limit belongs to
.
The assumption
for all
implies
for all
. From the condition
it follows that there exists a convergent subsequence
such that
. Therefore, there exists a convergent subsequence
such that
and
. Thus, we find that
for all
. Taking the limit as
we obtain
. As a result we have
. In other words,
is upper semi-continuous on X.
Step 2. We will prove that if
is a sequence convergent to
and
, then there exists a sequence
such that
for all
and
.
There are two cases:
(1) Suppose that
.
We get that
, i.e.
. In this case let
.
(2) Suppose that
.
In this case, we will consider two possibilities:
(2.1) Suppose that
.
From
implies
. Without loss of generally we can study the case when
. As a result we obtain
and let
.
(2.2) Suppose that
.
From the fact that
is continuous and concave on the compact and convex domain X, we deduce that
is nonempty, convex and compact. Denote the distance between
and
by
. Clearly,
and there exists a unique
such that
. Consider a linear segment
and a restriction
of
. From the definition of b it follows that: 1) If
and
, then
, 2) if
and
, then
for all
, i.e.
implies
. It is easy to show that b is bijective and continuous on
; therefore, there exists a unique
such that
and
is continuous. We obtain:
,
,
,
,
.
As a result we get a sequence
such that
for all
and
. This means that
is lower semi-continuous on X.
In summary,
is continuous on X.
Now, define a multifunction
such that
for all
. By analogy, we prove that
is convex-valued and continuous on X.
This procedure is repeated until all objective functions have been considered. At the end, define a multifunction
such that
for all
. Similarly, we prove that
is convex-valued and continuous on X.
Observe that
. Hence,
is continuous on X and Assumption 1 holds.
(b) The proof follows directly from Theorems 7(b) and 11(a).
(c) This is immediate from Theorems 7(c) and 11(a).
(d) If
is nonempty, then
. In fact
is nonempty and convex, we deduce that
is convex.
(e) It is obvious that
for all
.
We will prove that if
, then
.
There are two possibilities:
(1) Suppose that
.
The statement is trivially true.
(2) Suppose that
.
Let
,
,
and
. In fact,
is convex, it follows that
and s (z) = s (y1) = s (y2). But for each
there is
. By using this result we derive that
. Since
implies
. This means that
for all
and all
, i.e.
for all
. Thus, we get
for all
, i.e.
.
Finally, according to this result and Remarks 5 and 6 we conclude that
for all
.
(f) Consider the multifunction
from Theorem 7(b). Theorem 11(e) allows us to define a function
by
. The function b is continuous on X because ρ is upper semicontinuous on X and f is continuous on
. Clearly,
.
So, we get the continuous function b and we know that X is path-wise connected; therefore,
is pathwise connected too.
The theorem is proven.
Note that convexity plays an essential role in pathwise connectedness of the Pareto-front set.
We give the second special variant of the Maximum Theorem under convexity. It follows immediately from Theorems 2, 4 and 5.
Theorem 12. Let
,
be a continuous function, and
be a continuous multifunction. Define m and S as in Theorem 4. If u is strictly quasi-concave on X and D is convex-valued, then S is a continuous function on X.
Continuing with this analysis we have the following theorem.
Theorem 13. Let
be all concave on the convex domain X and
be strictly quasi-concave on X. Then:
(a) Assumptions 1, 2a and 2b hold.
(b) There exists a continuous Pareto-retract function.
(c)
and
are contractible and have the fixed point properties
(d)
.
(e)
is infinite and uncountable when
.
(f)
when
.
Proof. (a) Since Theorem 11(a) implies that Assumption 1 holds.
Let us fix an arbitrary point
. It is obvious that
. Let us assume that
. Hence, there exist
such that
. According to Theorem 11(e) we derive
. But
is strictly quasi-concave; therefore,
. This leads to a contradiction; therefore,
. Thus, we prove that Assumption 2a holds.
In fact,
is strictly quasi-concave on X, we have that Assumptions 2b holds.
(b) It follows from Theorems 12 and 13(a).
(c) We recall that X is convex; therefore, it is contractible and has the fixed point properties. Part (b) implies the proof.
(d) It follows from Theorems 8 and 13(a).
(e) Part (c) implies that
is path-wise connected and
implies that
. From this, we obtain that
is infinite and uncountable.
(f) Of course, from Theorem 11 and strictly quasiconcavity of
we have
.
The theorem is proven.
Remark 14. We can easy verify that the Pareto-optimal set
is not convex in general; see also Theorems 13(c) and (e).
Remark 15. It is interesting to note that for
the existence of a Pareto-retract multifunction does not necessarily imply the existence of a Pareto-retract function.
To answer the problem of the above remark, we give the following theorem.
Theorem 14. If
are concave on the convex domain X and
, then Assumptions 1 and 2a hold. In particular, there exists a continuous Pareto-retract function.
Proof. From Theorem 11 it follows that Assumption 1 holds.
Let us assume that
. In the proof of Theorem 13(a) we have that if
and
, then
. This leads to a contradiction; see also Remark 5.
The theorem is proven.
6. Conclusions
We have shown an application of the Maximum Theorem to multi-criteria optimization for the construction of the Pareto-retract mappings and the role of these mappings to analyze the structure of the Pareto-optimal and the Pareto-front sets. Here, we made our considerations in two cases—A general case and a convex case. It is important to note that, in this work, we introduced the concepts of the Pareto-retract multifunction and the Paretoretract function in a multi-criteria optimization problem. By means of these concepts, we have seen how one can use these mappings to analyze the topological properties of the Pareto sets.
The authors see three directions for future research related to this article: One would look for general conditions on the objective functions without the assumption of their concavity; one would analyze specific types of concave or quasi-concave objective functions; and one would study the relationship between the first two.