# Multiobjective Optimization, Scalarization, and Maximal Elements of Preorders

Authors: Paolo Bevilacqua; Gianni Bosi; Magalì Zuanon
Journal: Abstract and Applied Analysis
 (2018)

---

## Abstract

We characterize the existence of (weak) Pareto optimal solutions to the classical multiobjective optimization problem by referring to the naturally associated preorders and their finite (Richter-Peleg) multiutility representation. The case of a compact design space is appropriately considered by using results concerning the existence of maximal elements of preorders. The possibility of reformulating the multiobjective optimization problem for determining the weak Pareto optimal solutions by means of a scalarization procedure is finally characterized.


---

## Body

## 1. Introduction

It is very well known thatmultiobjective optimization (see, e.g., Miettinen [1] and Ehrgott [2]) allows choosing among various available options in the presence of more than one agent (or criterion), and therefore it represents a popular and important tool which appears in many different disciplines. This is the case, for example, of design engineering (see, e.g., Das [3] and Pietrzak [4]), portfolio selection (see, e.g., Xidonas et al. [5]), economics and risk-sharing (see, e.g., Chateauneuf et al. [6] and Barrieu an Scandolo [7]), and insurance theory (see, e.g., Asimit et al. [8]).Themultiobjective optimization problem (MOP) is usually formulated by means of the standard notation (needless to say, this formulation of the multiobjective optimization problem is equivalent, “mutatis mutandis,” to minx∈X[f1(x),…,fm(x)]=minx∈Xf(x),m≥2; we use the approach with the maximum for the sake of convenience):(1)maxx∈Xu1x,…,umx=maxx∈Xux,m≥2,where X is thechoice set (or thedesign space), ui is thedecision function (in this case autility function) associated with the ith individual (or criterion), and u:X↦Rm is the vector-valued function defined by u(x)=(u1(x),…,um(x)) for all x∈X.An elementx0∈X is a(weak) Pareto optimal solution to problem (1), for every x∈X, if ui(x0)≤ui(x) for every i∈{1,…,m}; then ui(x0)=ui(x) for every index i (respectively, for every x∈X, if ui(x0)≤ui(x) for every i∈{1,…,m}; then ui(x0)=ui(x) for at least one index i). In this case, the point x0∈X is said to be(weakly) Pareto optimal or a(weakly) efficient point for (MOP). Usually, X is a subset of Rn and concavity restrictions are posed on the functions ui (see, e.g., Ehrgott and Nickel [9]). In this case, an appropriatescalarized problem can be considered to determine Pareto optimal solutions (see Miettinen [1, Theorems  3.4.5 and 3.5.4]). Further, robust multiobjective optimization has been also considered in the literature (see, e.g., Bokrantz and Fredriksson [10]).It should be noted that Pareto optimality can be also considered by starting from a family{≾i}i∈{1,…,m} of not necessarily total preorders on a set X (see, e.g., d’Aspremont and Gevers [11]).In this paper we approach the multiobjective optimization problem (1) by referring to the preorders which are naturally associated with this problem. This means that, for determining the Pareto optimal solutions, we introduce the preorder ≾u on X defined, for all x,y∈X, by (2)x≾uy⟺uix≤uiy∀i∈1,…,m,and, for determining the weak Pareto optimal solutions, we refer to the preorder ≾uw on X defined, for all x,y∈X, by (3)x≾uwy⟺uix=uiy∀i∈1,…,moruix<uiy∀i∈1,…,m.The consideration that an element x0∈X is a(weak) Pareto optimal solution to problem (1) if and only if x0∈X is a maximal element for the preorder ≾u (≾uw, respectively) and the observation that the function u=(u1,…,um):X↦Rm is a(Richter-Peleg) multiutility representation of the preorder ≾u (≾uw, respectively) allow us to present various results concerning the existence of solutions to the multiobjective optimization problem, also in the classical case when the design space is a compact topological space. We recall that the concept of a (finite) multiutility representation of a preorder was introduced and studied by Ok [12] and Evren and Ok [13], while Richter-Peleg multiutility representations were introduced by Minguzzi [14] and then studied by Alcantud et al. [15].The consideration of a compact design space allows us to use classical results concerning the existence of maximal elements for preorders on compact spaces (see Rodríguez-Palmero and García-Lapresta [16] and Bosi and Zuanon [17]). We also address the scalarization problem by using classical results inDecision Theory related topotential optimality of maximal elements (see Podinovski [18, 19]). In particular, we refer to a classical theorem of White [20], according to which every maximal element for a preorder is determined by maximizing an order-preserving function (provided that an order-preserving function exists). In particular, we show that when considering the multiobjective optimization problem (1) in order to determine the weak Pareto optimal solution, this problem can be reformulated as an equivalent one in a such a way that every weak Pareto optimal solution is determined by maximizing an objective function.It should be noted that the results presented are fairly general, and we do not impose any restrictions neither to the choice setX, which usually is assumed to coincide with Rn, nor to the real-valued functions ui that are usually assumed to be concave in the literature.


## 2. Notation and Preliminaries

LetX be a nonempty set(decision space) and denote by ≾ apreorder (i.e., areflexive andtransitive binary relation) on X. If in addition ≾ isantisymmetric, then it is said to be anorder. As usual, ≺ denotes thestrict part of ≾ (i.e., for all x,y∈X, x≺y if and only if (x≾y)andnot(y≾x)). Furthermore, ~ stands for theindifference relation (i.e., for all x,y∈X, x~y if and only if (x≾y) and (y≾x)). We have that ~ is anequivalence relation on X. We denote by ≾|~ thequotient order on thequotient setX|~ (i.e., for all x,y∈X, [x]≾|~[y] if and only if x≾y, where [x]=z∈X:z~x is theindifference class associated with x∈X).For everyx∈X, we set(4)lx=z∈X∣z≺x,ix=z∈X∣x≾z.Given apreordered set(X,≾), a point x0∈X is said to be amaximal element ofX if for no z∈X it occurs that x0≺z. In the sequel we shall denote by XM≾ the set of all the maximal elements of a preordered set (X,≾). Please observe that XM can be empty.Denote by⋈ theincomparability relation associated with a preorder ≾ on a set X (i.e., for all x,y∈X, x⋈y if and only if not(x≾y)andnot(y≾x)).We recall that a functionu:(X,≾)↦(R,≤) is said to be(1)
isotonic or increasing if x≾y⇒u(x)≤u(y) for all x,y∈X;(2)
strictly isotonic ororder-preserving if it is isotonic and, in addition, x≺y⇒u(x)<u(y) for all x,y∈X.Strictly isotonic functions on(X,≾) are also calledRichter-Peleg representations of ≾ in the economic literature (see, e.g., Richter [21] and Peleg [22]).Definition 1.
A familyU={u1,…,um} of (necessarily isotonic) functions ui:(X,≾)↦(R,≤) is said to be (1)
afinite multiutility representation of the preorder ≾ on X if, for all x,y∈X,(5)x≾y⟺uix≤uiy,∀i∈1,…,m;(2)
afinite Richter-Peleg multiutility representation of the preorder ≾ on X if U is a finite multiutility representation and in addition every function ui∈U is a Richter-Peleg representation of ≾.Alcantud et al. [15, Remark 2.3] noticed that a (finite) Richter-Peleg multiutility representation U of a preorder ≾ on a set X also characterizes the strict part ≺ of ≾, in the sense that, for each x,y∈X,(6)x≺y⟺ux<uy,∀u∈U.Definition 2.
Consider the multiobjective optimization problem (1). Then a point x0∈X is said to be (1)
Pareto optimal with respect to the functionu=(u1,…,um):X↦Rm if for no x∈X it occurs that ui(x0)≤ui(x) for all i∈1,…,m and at the same time ui(x0)<ui(x) for at least one index i;(2)
weakly Pareto optimal with respect to the functionu=(u1,…,um):X↦Rm if for no x∈X it occurs that ui(x0)<ui(x) for all i∈{1,…,m}.Definition 3.
The set of all (weakly) Pareto optimal elements with respect to the functionu=(u1,…,um):X↦Rm will be denoted by XuPar (XuwPar, respectively).It is clear thatXuPar⊂XuwPar for every positive integer m, every nonempty set X, and every function u=(u1,…,um):X↦Rm.Definition 4.
Consider the multiobjective optimization problem (1). Then we introduce the preorders ≾u and ≾uw on X defined as follows for all x,y∈X:(1)
x≾uy⇔[ui(x)≤ui(y)foralli∈{1,…,m}].(2)
x≾uwy⇔[(ui(x)=ui(y)foralli∈{1,…,m})or(ui(x)<ui(y)foralli∈{1,…,m})].Remark 5.
Notice that the indifference relation~u and the strict part ≺u of the preorder ≾u, as well as the indifference relation ~uw and the strict part ≺uw of the preorder ≾uw, are defined as follows, for all x,y∈X:(7)x~uy⟺x~uwy⟺uix=uiy∀i∈1,…,m,x≺ux⟺uix≤uiy∀i∈1,…,mand  there  existsi∈1,…,msuch  thatuix<uiy,x≺uwy⟺uix<uiy∀i∈1,…,m.Definition 6.
A preorder≾ on a topological space (X,τ) is said to be (1)
upper semiclosed if i(x)=z∈X∣x≾z is a closed subset of X for every x∈X;(2)
upper semicontinuous if l(x)=z∈X∣z≺x is an open subset of X for every x∈X.While it is guaranteed that a preorder≾ on a compact topological space (X,τ) has a maximal element provided that ≾ is either upper semiclosed (see Ward Jr. [23, Theorem 1]) or upper semicontinuous (see the theorem in Bergstrom [24]), a characterization of the existence of a maximal element for a preorder on a compact topological space (X,τ) was presented by Rodríguez-Palmero and García-Lapresta [16].Definition 7 (see Rodríguez-Palmero and García-Lapresta [16, Definition  4]).
A preorder≾ on a topological space (X,τ) is said to betransfer transitive lower continuous if for every element x∈X which is not a maximal element of ≾ there exist an element y∈X and a neighbourhood N(x) of x such that y≺z implies that N(x)≺z for all z∈X.Theorem 8 (see Rodríguez-Palmero and García-Lapresta [16, Theorem  3]).
A preorder≾ on a compact topological space (X,τ) has a maximal element if and only if it is transfer transitive lower continuous.We recall that a real-valued functionu on a topological space (X,τ) is said to beupper semicontinuous if u-1(]-∞,α[)=x∈X:ux<α is an open set for all α∈R. A popular theorem guarantees that an upper semicontinuous real-valued function attains its maximum on acompact topological space.As usual, for a real-valued functionu on a nonempty set X, we denote by argmaxu the set of all the points x∈X such that u attains its maximum at x (i.e., argmaxu={x∈X:u(z)≤u(x)forallz∈X}).


## 3. Existence of Maximal Elements and Pareto Optimality

A finite familyU={u1,…,um} of real-valued functions on a nonempty set X gives rise to a preorder ≾ on X which admits precisely the (Richter-Peleg) multiutility representation U. It is easy to relate the maximal elements of such a preorder ≾ to the solutions of the associated multiobjective optimization problem (1).Theorem 9.
Let≾ be a preorder on a set X. Then the following statements hold: (1)
If≾ admits a finite multiutility representation U={u1,…,um} then XuPar=XM≾.(2)
If≾ admits a finite Richter-Peleg multiutility representation U={u1,…,um} then XuwPar=XM≾.Proof.
Assume that the preorder≾ on X admits a finite (Richter-Peleg) multiutility representation U={u1,…,um}. In order to show that XuPar⊂XM≾(XuwPar⊂XM≾), consider, by contraposition, an element x0∈XM≾. Then there exists an element x∈X such that x0≺x, or equivalently ui(x0)≤ui(x) for all i∈{1,…,m} with an index i∈{1,…,m} such that ui(x0)<ui(x) (respectively, ui(x0)<ui(x) for all i∈{1,…,m}). Then we have that x0 is not (weakly) Pareto optimal. In a perfectly analogous way it can be shown that XM≾⊂XuPar (XM≾⊂XuwPar). Hence, the proof is complete.The following proposition is an immediate consequence of Definition4.Proposition 10.
Consider the multiobjective optimization problem (1). Then U={u1,…,um} is a finite (Richter-Peleg) multiutility representation of the preorder ≾u (≾uw, respectively).From Theorem9 and Proposition 10, we immediately arrive at the following proposition.Proposition 11.
Consider the multiobjective optimization problem (1). The following conditions are equivalent on a point x0∈X:(i)
x0 is (weakly) Pareto optimal with respect to the function u=(u1,…,um).(ii)
x0 is maximal with respect to the preorder ≾u (≾uw) on X.


## 4. Multiobjective Optimization on Compact Spaces

The following theorem provides a characterization of the existence of Pareto optimal solutions to the multiobjective optimization problem (1) in terms of compactness of the choice set and appropriate semicontinuity conditions of the strict parts of the naturally associated preorders.Theorem 12.
Consider the multiobjective optimization problem (1). The following conditions are equivalent:(i)
XuPar(XuwPar) is nonempty.(ii)
There exists a compact topologyτ on X and an upper semiclosed preorder ≾ on X such that ≺u⊂≺(≺uw⊂≺).(iii)
There exists a compact topologyτ on X such that ≾u(≾uw) is upper semicontinuous.Proof.
(i)⇒ (ii). Since XuPar (XuwPar) is nonempty, we have that XM≾u(XM≾uw) is nonempty by Proposition 11. Therefore, condition (ii) is verified by Bosi and Zuanon [17, Corollary 3.2, (i) ⇒ (ii)].
(ii)⇒ (i). Since ≾ is an upper semiclosed preorder on compact topological space (X,τ), ≾ has a maximal element from Ward Jr. [23, Theorem 1]. Therefore, also ≾u (≾uw) has a maximal element due to the fact that ≺u⊂≺ (≺uw⊂≺).
(i)⇔ (iii). See Alcantud [25, Theorem 4, (a) ⇔ (b)].
Hence, the proof is complete.Corollary 13.
Consider the multiobjective optimization problem (1) where X is endowed with a compact topology τ. Then XuPar is nonempty provided that there exist a positive integer n and a function u′=(u1′,…,un′):X↦Rn with all the real-valued functions ui′(i∈{1,…,n}) upper semicontinuous, such that the following condition is verified: (i)
For allx,y∈X, x≺uy implies that ui(x)≤ui(y) for all i∈{1,…,n} and there exists i∈{1,…,n} such that ui(x)<ui(y).Proof.
By Theorem9 and Proposition 11, we have that XuPar=XM≾u is nonempty provided that there exists an upper semiclosed preorder ≾ on (X,τ) such that ≺u⊂≺. Let u′=(u1′,…,un′):X↦Rn be a function with the indicated properties. Define a preorder ≾ on X by (8)x≾y⟺ui′x≤ui′y∀i∈1,…,nx,y∈X.The preorder ≾ is upper semiclosed on (X,τ) since ui′ is upper semicontinuous for all i∈{1,…,n} and U={u1,…,un} is a (finite) multiutility representation of ≾. Condition (i) precisely means that ≺u⊂≺. Hence, Theorem 12, (ii) ⇒ (i), applies, and the corollary is proved.Corollary 14 (see Ehrgott [2, Theorem  2.19]).
Consider the multiobjective optimization problem (1) where X is endowed with a compact topology τ and the real-valued functions ui(i∈{1,…,m}) are all upper semicontinuous. Then XuPar is nonempty.Proof.
This is a particular case of the above Corollary13, when m=n and u′=u.As an application of Theorem8, let us finally present a characterization of the existence of Pareto optimal solution to the multiobjective optimization problem (1) on a compact space. In case that ≾ is a preorder on a set X, x is an element of X, and A is a subset of X, the scripture “A≾x”  (“A≺x”) stands for “z≾xfor allz∈A” (respectively “z≺xfor allz∈A”).Theorem 15.
Consider the multiobjective optimization problem (1) where X is endowed with a compact topology τ. Then XuPar is nonempty if and only if for every element x∈X which is not Pareto optimal there exist an element y∈X and a neighbourhood N(x) of x such that, for all z∈X, if y≺uz, then y′≺uz for all y′∈N(x).


## 5. Scalarization and the Representation of All Pareto Optimal Elements

In this paragraph we address the scalarization of the multiobjective optimization problem under fairly general conditions.The following theorem was proved by White [20]. Given any maximal element x0 relative to a preorder ≾ on a set X, it guarantees the existence of some order-preserving function u attaining its maximum at x0.Theorem 16 (see White [20, Theorem  1]).
Let(X,≾) be a preordered set and assume that there exists an order-preserving function u′:(X,≾)↦(R,≤). If XM≾ is nonempty, then for every x0∈XM≾ there exists a bounded order-preserving function u:(X,≾)↦(R,≤) such that argmaxu=[x0]={z∈X:z~x0}.The following corollary is an easy consequence of Theorem16.Corollary 17.
Consider the multiobjective optimization problem (1). The following conditions are equivalent on a point x0∈X:(i)
x0∈XuPar(x0∈XuwPar).(ii)
There exists a bounded real-valued functionux0 on X which is order-preserving for the preorder ≾u(≾uw) on X such that argmaxux0(x)=[x0]~u(argmaxux0(x)=[x0]~uw).Proof.
Without loss of generality, we can assume that the functionsui appearing in the multiobjective optimization problem (1) are all bounded. Since U={u1,…,um} is a finite (Richter-Peleg) multiutility representation of the preorder ≾u (≾uw, respectively) by Proposition 10, it is easily seen that the function u∗≔∑h=1m‍uh is order-preserving for the preorder ≾u (≾uw, respectively). Then we are ready for applying Theorem 16.The simple proof of the following lemma is left to the reader.Lemma 18.
For any two functionsu=(u1,…,um):X↦Rm and u′=(u1′,…,um′):X↦Rm, if ≾u=≾u′(≾uw=≾u′w), then XuPar=Xu′Par(XwParu=XwParu′).As usual, ifA is any nonempty subset of X, we denote by |A| thecardinality of A.Theorem 19.
Consider the multiobjective optimization problem (1). Then the following conditions are equivalent: (i)
There exist a positive integerp≤m and a function u′=(u1′,…,up′,up+1′,…,um′):X↦Rm satisfying the following conditions:
(a)
XuwPar=Xu′wPar=⋃i=1parg⁡max⁡ui′;(b)
arg⁡max⁡ui′∩arg⁡max⁡uj′=∅ for all i≠j(i,j∈{1,…,p}).(ii)
p=|XM|~uw≾uw|≤m.Proof.
The implication “(i)⇒ (ii)” is clear. Let us show that also the implication “(ii) ⇒ (i)” holds true. Let p=|XM|~uw≾uw|≤m and XM|~uw≾uw={[xh]}h∈{1,…,p}. Following the proof of White [20, Theorem 1], we can define, for every h∈{1,…,p} and x∈X,(9)uh′x=uhxifnotx~uwxh,supuhx+δhifx~uwxh,where δ1,…,δp are positive real numbers. Further, define uk′=uk for k=p+1,…,m. In this way, the p real-valued functions u1′,…,up′ are all order-preserving for ≾uw such that arg⁡max⁡uh′=[xh] for h=1,…,p.
It is clear thatarg⁡max⁡ui′∩arg⁡max⁡uj′=∅ for all i≠j(i,j∈{1,…,p}) and that XuwPar=⋃i=1parg⁡max⁡ui′. It remains to show that XuwPar=Xu′wPar. To this aim, by Lemma 18 it suffices to show that ≾uw=≾u′w or equivalently that the following property holds for all elements x,y∈X: (∗)
[uh(x)≤uh(y)forallh∈{1,…,m}]⇔[uh′(x)≤uh′(y)forallh∈{1,…,m}].
Three cases have to be considered.(1)
x∈X∖XM≾uw and y∈X∖XM≾uw. We have that, for every h∈{1,…,m}, uh′(x)=uh(x) and uh′(y)=uh(y). Hence, the above property (∗) is obviously verified.(2)
x∈XM≾uw and y∈X∖XM≾uw. In this case there exists h∈{1,…,p} such that x∈[xh], y∉[xh], and therefore we have that uhy=uh′(y)<uh′(x)=supuh(X)+δh. On the other hand, from the fact that x≾uwy is contradictory, we have that there exists k∈1,…,p such that uk(y)<uk(x). Hence, property (∗) is verified also in this case.(3)
x∈XM≾uw and y∈XM≾uw. Clearly, we must have that either (x~uwy) or (not(x≾uwy)andnot(y≾uwx)). In the first case, it is clear that property (∗) holds with all equalities on both sides of the equivalence. In the second case, since x⋈uwy, there exist h,k∈{1,…,m} such that uh(x)<uh(y) and uk(y)<uk(x). On the other hand, the definition of the function u′ implies the existence of h∈{1,…,p} such that x∈arg⁡max⁡uh, and, therefore, for that h, we have that uh′(y)<uh′(x). Analogously, there exists k∈{1,…,p} such that y∈arg⁡max⁡uk, and, therefore, for that k, we have that uk′(x)<uk′(y). This consideration completes the proof.


## 6. Conclusions

We approach the multiobjective optimization problem by using the preorders which are naturally associated with the concepts of Pareto optimal and, respectively, weakly Pareto optimal solutions, in the sense that the Pareto optimal and the weakly Pareto optimal solutions are precisely the maximal elements of these preorders. This interpretation gives us the possibility of using all the theorems concerning the maximal elements of the preorders (in particular on compact spaces) in order to guarantee the existence of solutions to the multiobjective optimization problem. This reinterpretation allows us to state a scalarization result under fairly general conditions. Our analysis does not require any particular requirement concerning the functions appearing in the multiobjective optimization problem or the choice set.



---

*Source: 3804742-2018-01-28.xml*