View of Numerical methods for solving unimodal multiple criteria optimization problems - a synthesis

Rev. Anal. Num´er. Th´eor. Approx., vol. 37 (2008) no. 1, pp. 59–70 ictp.acad.ro/jnaat

NUMERICAL METHODS FOR SOLVING UNIMODAL MULTIPLE CRITERIA OPTIMIZATION PROBLEMS – A SYNTHESIS^†

LIANA LUPS¸A^∗and IOANA CHIOREAN^∗

Abstract. In this paper we give a general method to approximate the set of all efficient solutions and the set of all weakly-efficient solutions for a multiple criteria optimization problem involving generalized unimodal objective functions on the feasible sets. This type of problems appear frequently in Economy, Math- ematics, sometimes in Medico-Economics studies, etc.

MSC 2000. 90C29, 90C10, 65H05, 66Y05.

Keywords. Generalized unimodal functions, minimum points, multiple criteria programming, efficient points, weakly efficient points, serial and parallel calculus.

1. INTRODUCTION

Starting with an overview of the existing algorithms, the present paper intends to give a general algorithm which compute the set of optimal solution of an optimization problem, when the set on which the function is unimodal is any compact subset of R(not necessarily interval or discreet set). A parallel approach for this algorithm is also given.

Let f = (f1, . . . , fm) : D → R^m (m ∈ N^∗, m = 2) be a vector-valued function defined on a nonempty setD⊂Rand S a subset ofD. Consider the multiple criteria optimization problem:

(M OP)

Minimize f(x) subject to x∈S, (1)

where the partial ordering in the image space of the objective function is under- stood to be induced by the standard ordering coneR^m+. More precisely, denot- ingI :={1, . . . , m}, we have for anyx= (x₁, . . . , x_m), y= (y₁, . . . , y_m)∈R^m:

x≤y ⇔ xi 5yi, for all i∈I, and ^X

i∈I

xi < ^X

i∈I

yi.

∗ “Babe¸s-Bolyai” University, Faculty of Mathematics and Computer Science, 400084, Cluj-Napoca, Romania, email: {llupsa,ioana}@math.ubbcluj.ro.

†This paper is supported by the scientific grant CEEX 125/31.07.2006.

Recall (see e.g. [6]) that the set of efficient solutions, called by us the efficient set, and the set ofweakly-efficient solutions, called by us the weakly- efficient set, of problem (1) are given, respectively, by:

Eff(S;f) := {x∈S |@y∈S such thatf(y)≤f(x)}, WEff(S;f) := {x∈S|@y∈Ssuch thatf(y)< f(x)}.

In what follows we give a general method to approximate the sets Eff(S;f) and WEff(S;f) in the hypothesis that the functionf is lower unimodal onS.

We mention that the generalization of “unimodal function” notion was made, until now, in the following three directions:

a) By replacing the real interval which was the definition domain of the unimodal property (see [5]) with an arbitrary set of real numbers (see [7]);

b) By working with multivariate functions, due to the fact that the do- main of definition for the unimodal property is a compact interval in Rⁿ (see [1] and [4]);

c) By replacing the real univariate functions with vectorial univariate function (see [8]). We mention, also, that the obtained results in the third case contain, as particular cases, properties already known from the first case. Analogously, the given algorithms in the case c) may be successfully used in the case a), too.

2. UNIMODAL VECTORIAL FUNCTIONS ON A SET AND SOME OF THEIR PROPERTIES

In the following we suppose thatDis a non empty subset of the real numbers set Rand m is a natural number,m=2.

Definition1. (see [8]) A function ϕ:D→Ris said to be lower unimodal onS ⊂D if there exist u, v∈S satisfying the following conditions:

(LU1) ϕ(u) =ϕ(v);

(LU2) ϕ(x)> ϕ(y) whenever x, y∈S, x < y5u;

(LU3) ϕ(x)< ϕ(y) whenever x, y∈S, v5x < y;

(LU4) S∩[u, v] ={u, v}.

Remark 2. (see [8])

1) By (LU1)–(LU2) it follows thatu5v, so (LU4) makes sense.

2) As a direct consequence of (LU1)–(LU4) we can easily deduce that for anyx, y∈S the following implications hold:

If x < y 5v then ϕ(x)=ϕ(y);

If u5x < y then ϕ(x)5ϕ(y).

Definition 3. (see [8]) A functionf = (f1, ..., fm) :D→R^m is said to be lower unimodal on S ⊂D if all its scalar components f_i, i ∈I = {1, ..., m}, are lower unimodal on S.

If f = (f₁, ..., f_m) : D → R^m is a lower unimodal function on S ⊆ D, by ui, vi we denote, for every i∈I, the pointsu and v from Definition 1.

In the following we remember some properties of the sets Eff(S;f) and WEff(S;f) in the circumstances that the function f is lower unimodal on S. The problem was studied in [9], where the authors showed that both the sets Eff(S;f) and WEff(S;f) can be completely determined by only using the numbersu1, v1, . . . , um, vm. As in mentioned paper, we denote:

u:= min

i∈I u_i, v:= min

i∈I v_i, u:= max

i∈I u_i and v:= max

i∈I v_i. Theorem 4. (see [9], Theorems 2.1, 2.2)

i) The set of weakly efficient solutions of problem(1)admits the following representation:

WEff(S;f) = [u, v]∩S.

(2)

ii) The set of efficient solutions of problem (1) is given by the following representation:

Eff(S;f) = [min{v, u},max{v, u}]∩S.

(3)

Other important properties of lower unimodal functions will be given in that follows. Let us suppose that S is a nonempty subset of D and f :D→ R^m, is a lower unimodal function on S.Ifc and dare elements ofS,we introduce the notations: I_c,d⁻ = {i ∈ I|f_i(c) < f_i(d)}, I_c,d⁰ = {i ∈ I|f_i(c) = f_i(d)}, I_c,d⁺ = {iI|f_i(c)> f_i(d)}.

Theorem5. Ifa, b, c, d∈S are such that a5c < d5b, a5u, and v5 b, and

(4) θ= inf{|x−y| |x, y∈[a, b]∩S, x6=y}, then the following sentences are true:

(i) If I_c,d⁻ 6=∅, then {u, v} ⊂[a, d−θ]∩S;

(ii) If I_c,d⁻ =∅ and I_c,d⁰ 6=∅, then {u, v} ⊂[c, d]∩S;

(iii) If I_c,d⁻ =∅ and I_c,d⁰ =∅, then {u, v} ⊂ [c+θ, b]∩S;

(iv) If I_c,d⁺ 6=∅, then {u, v} ⊂ [c+θ, b]∩S;

(v) If I_c,d⁺ =∅ and I_c,d⁰ 6=∅, then {u, v} ⊂[c, d]∩S;

(vi) If I_c,d⁺ =∅ and I_c,d⁰ =∅, then {u, v} ⊂[a, d−θ]∩S.

Proof. (i) As I_c,d⁻ 6= ∅, there is an i ∈ I such that fi(c) < fi(d) and, in this case, Remark 2 implies ui, vi ∈ [a, d[∩S. Then vi < d and (4) implies θ5d−v_i orv_i 5d−θ. Asu_i 5v_i, we getu_i5d−θ. Therefore,

u5u_i 5d−θ and v5v_i 5d−θ.

These implyu∈[a, d−θ]∩S and v∈[a, d−θ]∩S, i.e. (i) holds.

(ii) AsI_c,d⁻ =∅, we have fi(c)=fi(d), for alli∈I. Then Remark 2 implies c 5 ui 5 vi, for all i ∈ I. Therefore, c 5u and c 5 v. On the other hand, as I_c,d⁰ 6= ∅, there is k ∈ I such that f_k(c) = f_k(d). In this case, Remark 2 givesc5u_k 5dand c5v_k5d. It follows that u5u_k 5dand v 5v_k 5d.

Therefore (ii) holds.

(iii) IfI_c,d⁻ ∪I_c,d⁰ =∅, then f_i(c)> f_i(d), for all i∈I. In this case, Remark 2 implies c < ui5vi 5b, for alli∈I. Then u5v 5b. Also, in view of (4), we have

θ5ui−c and θ5vi−c, for all i∈I.

These imply c+θ 5 u_i and c+θ 5 v_i, for all i ∈ I. Therefore, we have c+θ5u and c+θ5v. Hence (iii) holds.

In the same way we can prove that (iv)–(vi) are true.

We will use the above results in the next section to elaborate a general method for approximating the efficient set and the weakly-efficient set in a unimodal vectorial optimization problems (i.e. in the problem (MOP) when the functionf is lower unimodal onS).

3. THE (UMA) ALGORITHM

In what follows we suppose that:

H1. D⊆R;

H2. S is a nonempty, compact subset of D,and cardS =2;

H3. f = (f₁, ..., f_m) :D→R^m is a lower unimodal function on S, where mis a natural and not a null number.

The following algorithm permits to obtain two sets WEF and EF. These sets approximate the sets Eff(S;f) and WEff(S;f),with a given error ε >0.

We mention that an algorithm to approximate Eff(S;f) and WEff(S;f), in the case when the setS is a real compact interval, was given in [10] and other algorithm, in the some condition, but more performance, [3]. In the special case whenSis a discrete set, the first algorithm to determine the sets Eff(S;f) and WEff(S;f) was given in [9] and other algorithm, in the some condition, but more performance, in [8].

In the UMA Algorithm, we use the following notations:

I⁻_k for I_c⁻

k,d_k and I⁰_k for I_c⁰

k,d_k; I⁺_k forI⁺

ck,dk

and I⁰_k for I_c⁰

k,dk.

The serial (UMA) Algorithm Step 1. Set

k:= 0, h:= 0, sw:= 1, sw:= 1, S₁ :=S, S₁:=S, a₁ := min S, a1:= min S, b₁ := max S, b1 := max S, and proceed.

Step 2. If sw= 0, then go to step 12; else proceed.

Step 3. Increasekby 1 and proceed.

Step 4. Set µ_k := inf{|x−y| | x, y∈S_k, x6=y}, and proceed.

Step 5. Takec_k∈S_k and d_k∈S_k, such that (5)

a_k< c_k< d_k< b_k, if cardS_k>3, a_k=c_k< d_k< b_k, if cardS_k= 3, a_k=c_k< d_k=b_k, if cardS_k= 2, and proceed.

Step 6. Build the sets I⁻_k = {i∈I|fi(c_k)< fi(d_k)} and I⁰_k = {i∈I|f_i(c_k) =f_i(d_k)} and proceed.

Step 7. IfI⁻_k 6=∅then set S_k+1:=S_k∩ [a_k, d_k−µ_k],

a_k+1 := minS_k+1, b_k+1:= maxS_k+1, u_k :=c_k, v_k:=c_k, and go to step 10; else go to the next step.

Step 8. IfI⁰_k 6=∅ then set S_k+1:=S_k∩ [c_k, d_k], a_k+1 := minS_k+1,

b_k+1 := maxS_k+1, u_k := c_k, v_k := d_k,and go to step 10, else go to the next step.

Step 9. Set S_k+1 :=S_k∩ [c_k+µk, b_k], a_k+1:= minS_k+1, b_k+1:= maxS_k+1, u_k:=d_k, v_k:=d_k,and proceed.

Step 10. If b_k − a_k < ε/2,or cardS_k = 2,then proceed; else go to step 12.

Step 11. Set sw := 0, and proceed.

Step 12. If sw= 0, then go to step 22; else proceed.

Step 13. Increaseh by 1 and proceed.

Step 14. Set ν_h:= inf{|x−y| | x, y∈S_h, x6=y},and proceed.

Step 15. Takec_h ∈S and d_h∈S, such that (6)

a_h < c_h < d_h< b_h, if card S_h>3, a_h < c_h < d_h=b_h, if card S_h= 3, a_h =c_h < d_h=b_h, if card S_h= 2, and proceed.

Step 16. Build the sets I⁺_h = {i∈I|fi(ch)> fi(dh)}, and I⁰_h = {i∈I|f_i(c_h) =f_i(d_h)},and proceed.

Step 17. IfI⁺_h 6=∅then set S_h+1 :=S_h∩ [c_h+ν_h, b_h],

ah+1:= minSh+1, bh+1 := maxSh+1, uh :=dh, vh :=dh, and go to step 20, else proceed.

Step 18. IfI⁰_h 6=∅ then set S_h+1:=S_h∩ [c_h, d_h],

a_h+1:= minS_h+1, b_h+1 := maxS_h+1, u_h :=c_h, v_h:=d_h, and go to step 20, else proceed.

Step 19. Set S_h+1:=S_h∩ [a_h, d_h−ν_h],

a_h+1:= minS_h, b_h+1:= maxS_h+1, u_h :=c_h, v_h:=c_h,and proceed.

Step 20. Ifbh−ah < ε/2,or cardSh 52,then proceed; else go back to step 2.

Step 21. Set sw := 0.

Step 22. If sw6= 0, then go back to step 2.

Step 23. Set WEF :={x∈S |u_k5x5v_h} and proceed.

Step 24. Ifv_k 5u_h then set EF :={x∈S |v_k5x5u_h};

else set EF :={x∈S|uh5x5v_k}.

Step 25. Stop.

Theorem 6. In the hypotheses H1–H3, if k is a natural number and the numbers a₁, ..., a_k, b₁, ..., b_k, u₁, ..., u_k, v₁, ..., v_k are the points given by the UMA Algorithm, one have

(7) u, v∈S_j, for allj ∈ {1, ..., k}.

If, in addition, cardS_k 5 2, then

(8) u_k = u, v_k = v.

Proof. First we prove that (7) holds. The proof is by induction. Step 1 gives S₁ =S. As u, v ∈S, obviously u, v ∈ S₁. Therefore, if k = 1, then (7) is true. Let now consider k >1, and let be j ∈ {1, ..., k−1}. We prove that if u, v ∈S_j, then

(9) u, v ∈S_j+1.

From the algorithm it follows that b_i−a_i =ε/2, and card S_i >2, for all i∈ {1, ..., k−1}. Therefore cardS_j =3. If c_j and d_j are the points chosen at the j^th iteration, three cases are possible:

1)I⁻_j 6=∅; 2)I⁻_j =∅, andI⁰_j 6=∅; 3)I⁻_j =∅, andI⁰_j =∅.

If I⁻_j 6=∅, from Step 7 we have S_j+1 := S_j∩[a_j, d_j−µj]. On the other hand, Theorem 5 gives u, v∈[a_j, d_j−µ_j]∩S. But, in view of the induction hypothesis, we have u, v ∈ S_j. Therefore (9) holds. By analogy, it can be proved that (9) is true, in the other two cases. Therefore, because (7) is true forj= 1,by induction, we can conclude that (7) holds for all j∈ {1, ..., k}.

Now we prove that, if, in addition, cardS_k= 2, then u_k=u and v_k=v.

First we mention that, from (7), we get u, v ∈ S_k. As cardS_k = 2, Step 5 gives c_k = a_k and d_k = b_k. Therefore S_k = {a_k, b_k}. Three cases may appear: I⁻_k 6= ∅; I⁻_k = ∅ and,I⁰_k 6= ∅; I⁻_k = ∅, andI⁰_k = ∅.

If I⁻_k 6= ∅, in view of Theorem 5 we have {u, v} ⊆ [a_k, d_k[∩S_k = {a_k}.

Then, we get u = v = a_k. On the other hand, Step 7 gives u_k = v_k = c_k. As c_k = a_k, equality (8) holds.

In the second case, as I⁰_k 6= ∅, there is i∈I such that ui =ck =ak and vi =dk =bk. Thereforeu =ak. For alli∈I\I⁰_k we haveui =vi=dk=bk. Hence, vi =d_k=b_k for alli∈I. Therefore v =b_k. On the other hand, Step 8 gives u_k = c_k=a_k and v_k = c_k =b_k.Again, (8) holds.

If I_c⁻

k,d_k =∅ and I_c⁰

k,d_k = ∅, Theorem 5 gives {u, v} ⊆]c_k, b_k]∩S ={b_k}.

On the other hand, Step 9 givesu_k = v_k = d_k=b_k. Hence (8) holds, too.

In the same manner we can prove:

Theorem 7. In the hypotheses H1–H3, if h is a natural number and the numbers a1, ..., ah, b1, ..., bh, u1, ..., uh, v1, ..., vh are the points given by the UMA Algorithm, then u, v ∈ [a_j, b_j], for all j ∈ {1, ..., h}. If, in addition, cardS_h 5 2, thenu_h = u, v_h = v.

The following results come easily:

Remark8. Ifµ(S) > 0 andε 5µ(S),then the UMA Algorithm stops after a finite number of iterations, Eff(S;f) = EF and WEff(S;f) = W EF.

Remark9. If cardS_k>2, for all natural numberk, and there is a conver- gent sequence (δ_k)_k∈N^∗ such that

k→+∞lim δ_k = 0 and b_k−a_k 5 δ_k, for allk∈N^∗, then the sequences (u_k)_k∈N^∗ and (v_k)_k∈N^∗ are convergent and lim

k→+∞u_k = u, lim

k→+∞v_k = v.

Similarly results can be given for the sequences (uh)_h∈N^∗, and (vh)_h∈N^∗. IfA and B are two real intervals, we set:

lng(A\B) = 0, if A\B = ∅;

lng (A\B) =w₂−w₁, if A\B= [w₁, w₂];

lng(A\B) =w₂−w₁ + w₄−w₃, if A\B = [w₁, w₂]∪[w₃, w₄].

Remark 10. In the hypotheses H1–H3, if ε > 0 and the sets EF and WEF are built with the UMA algorithm, then lng(WEF\WEff(S;f)) 5 ε, lng(WEff(S;f)\WEF) 5 ε,lng (EF\Eff(S;f)) 5 ε,and lng (Eff(S;f)\EF)

5 ε.

4. PARTICULAR CASES

In what follows, we show how, from the UMA algorithm, one can obtain the methods given in [3], [8], [9] and [10].

4.1. S is a compact interval. In view of [9], Remark 1.1, when S is a compact interval and the function f : [a, b] → R^m is lower unimodal on S, then u_i = v_i = xi, for all i ∈ {1, ..., m}, where {x_i} = Arg min

x∈S fi(x).

Therefore u= v and u =v. Also, it is known that, if S = [a, b], then, for each natural numbersk=1,we have cardS_k>3. Therefore, one can choose the points c_k, d_k ∈ S_k satisfying the conditions: a_k < c_k < d_k < b_k and

c_k−a_k = b_k−d_k.For this, one takes as t_k any real numbers satisfying the conditions 0 < t_k < 1/2 and put

(10) c_k = a_k+t_k(b_k−a_k), d_k = b_k−t_k(b_k−a_k).

Then

(11) b_k+1−a_k+1 = (1−t_k)(b_k−a_k).

In view of the UMA algorithm, we haveu=v∈[a_k, b_k], andu_k, v_k ∈[a_k, b_k].

Therefore, if (t_k)^m_k=1 is a finite sequence of real numbers with 0< t_k<1/2, for each k∈ {1, ..., m}, and if the sequence of sets (S_k)^m_k=1 is constructed by the UMA algorithm, where we takec_k and d_k using (10), then

|u−u_k| 5 (1−t_k−1)(b_k−1−a_k−1) =

= (1−t_k−1)(1−t_k−2)(b_k−2−a_k−2)

= ... =

k−1

Q

j=1

(1−t_j)·(b−a) and

|v−v_k| 5 (1−t_k−1)(b_k−1−a_k−1) =

= (1−t_k−1)(1−t_k−2)(b_k−2−a_k−2)

= ... =

k−1

Q

j=1

(1−t_j)·(b−a).

Analogously, if (t_h)^m_h=1 is a finite sequence of real numbers with 0< t_h< ¹₂, for each h∈ {1, ..., m}, and if the sequence of sets (S_h)^m_h=1 is constructed by the UMA algorithm, where

(12) c_h = a_h+t_h(b_h−a_h), d_h = b_h−t_h(b_h−a_h), then we have

|u−uh| 5

h−1

Y

j=1

(1−tj)·(b−a) and |v−vh| 5

h−1

Y

j=1

(1−tj)·(b−a).

Hence, if we put WEF = [u_k, v_h]∩S, then we have lng(WEF\WEff(S; f))5 (Π^k−1_j=1(1−t_j) + Π^h−1_j=1(1−tj)·(maxS−minS) and lng(WEff(S; f)\WEF)5 (Π^k−1_j=1(1−t_j) + Π^h−1_j=1(1−t_j)·(maxS−minS).A similar result can be obtained for the setsEF and Eff(S;f).In order to decrease the number of computations for the values off, one may choose t_k such thatd_k+1 = c_k, if (I⁻_k ^SI⁰_k)6=∅, and c_k+1 = d_k, if (I⁻_k ∪I⁰_k) =∅.Therefore, we have either

b_k+1−t_k+1(b_k+1−a_k+1) = c_k, or a_k+1+t_k+1(b_k+1−a_k+1) = d_k. Then the numbers t_k, k∈N, have to satisfy the condition

(13) (1−t_k+1)(1−t_k) = t_k.

Analogously, we may choose the sequence (t_h)_h∈N^∗ such that (14) (1−t_h+1)(1−t_h) = t_h.

By choosing particular values for the sequence (t_k)_k∈N^∗, such that (13) is satisfied, and particular values for the sequence (t_h)_h∈N^∗ such that (14) is satisfied, we obtain a particular type of methods, which, by analogy with the real case, we call the methods of successive section. Two important sub-cases are given further on.

Case I.If t_k =t, for eachk∈N^∗, and t_h =t, for each h∈N^∗, then (13) and (14) imply (1−t)² = t, i.e. t²−3t+ 1 = 0. The above equation has two solutions. If we choose

t_k = ³⁻

√ 5

2 , t^h = ³⁻

√ 5

2 , for each h∈N^∗,

then we call the resulting method, the method of the “gold section”.

Case II. It is known that the Fibonacci numbers Fk, k ∈ N^∗, satisfy the following recurrence formula

F_k+1 = F_k + Fk−1, for eachk∈N^∗, k=3, F₁ = F₂ = 1.

Let m∈N^∗. It is easy to see that, if we choose (15) t_k = tk = ^F_F^m−k+1

m−k+3, for eachk∈ {1, ..., m}, then

(1−t_k+1)(1−t_k) = (1−t_h+1)(1−t_h) = ^F_F^m−k+1

m−k+3 = t_k, ∀k∈ {1, ..., m−1}.

As

0 < ^F_F^m−k+1

m−k+3 = _F ^Fm−k+1

m−k+2+Fm−k+1 < _2F^Fm−k+1

m−k+1 = ¹₂,

the numbers t_k, t_k, k ∈ {1, ..., m}, given by (15), satisfy condition (13) and (14). The method of successive section obtained using (15) is known as the

“Fibonacci’s method” (see [3]).

4.2. S is a finite set. Let be S = {x₁, ..., x_n}, where n ∈ N, n = 2, and x1 < x2 < ... < xn. In this case, in the first step of the UMA algorithm, we have a =x₁ and b = xn, and, therefore, a₁ =a₁ = x₁ and b₁ = b₁ =xn. Then S₁ = S₁ = {x₁, ..., x_n}. Therefore card S₁ = cardS₁ = n, and, in each iterations, card S_k ∈ N^∗ and card S_h ∈N^∗. We suppose that, at each iteration,k,we rewrite the elements of the set Sk, such that

S_k = {x^k₁, ..., x^k_nk}, and x^k₁ < x^k₂ < ... < x^k_nk, where n_k= card S_k.Two cases may appear: n_k = 2, or n_k > 3.

If at the k iteration we have nk > 3, then we may choose c_k = x^k_m and d_k = x^k_m+1, wherem = [nk/2], in the step 5 of the UMA algorithm.

If at thekiteration we have nk = 2, then we may choose dk = x^k₂ in the step 5 of the UMA algorithm.

Analogously, in each iteration, we may choose the points ch anddh. These specifications being done, the UMA algorithm is the same as the algorithm given in [8].

Table 1. Results of the UMA Algorithm

it a_k b_k c_k d_k u_k v_k sw a_k b_k c_k d_k u_k v_k sw 1 0 1 ¹₄ ¹₂ ¹₄ ¹₄ 1 0 1 ¹₄ ¹₂ ¹₂ ¹₂ 1 2 0 ¹₂ ¹₈ ¹₄ ¹₈ ¹₈ 1 ¹₄ 1 ¹₂ 1 ¹₂ ¹₂ 1 3 0 ¹_{4 16}^{1 1}₈ ¹₈ ¹₈ 1 ¹₄ ¹₂ ¹₄ ¹₂ ¹₂ ¹₂ 0

4 ₁₆^{1 1}_{4 16}^{1 1}₈ ¹₈ ¹₈ 1 0

5 ¹₈ ¹₄ ¹₈ ¹₄ ¹₈ ¹₈ 0 0

4.3. S is an infinite set, but not a real interval. The UMA algorithm can also be used in the case when the setS is infinite but not a real interval, situation which could not be accomplished by the other cited methods.

Example11. Let be S = {₂¹n|n∈N}∪{0} and f = (f₁, f₂) : [0,1]→R² the function given by

f₁(x) =|x−1/2|, f₂(x) =|x−1/6|, for allx∈[0,1].

Obviously, f is lower unimodal on S. If we apply the UMA algorithm, taking ε= 1/100, we have to make 5 iterations, in order to compute the sets WEF and EF, as can be seen in Table 1.

Therefore

W EF ={¹₈,¹₄,¹₂}, EF ={¹₈,¹₄,¹₂}.

5. THE PARALLEL UMA ALGORITHM

The presented UMA Algorithm is thought for a serial implementation. Due to the fact that its second part (Steps 11–20) contains the same type of in- structions as the first part (Steps 2–10), the time of execution can be reduced by using parallel calculus.

There are several way of using more that one processor, but we shall consider a parallel execution of Master-Slave type (see [2]). In the created network, we have a Master processor, with the identification number (ID) equal with 1, and three Slaves processors, with IDs equal to 2, 3 and 4. All the proces- sors memorize the whole program, but each of them will perform exactly the instructions needed, according with its ID number.

A possible parallel algorithm is the following:

IfID= 1 then let {Master execution}

k= 0; h= 0;

a₁= minS; a₁ = minS; b₁= maxS; b₁ = maxS;

bool= 0; {for the points of minimum}

Repeat k=k+ 1;

µ_k= inf{|x−y| |x, y∈[a_k, b_k]∩S};

Send Message to Slaves (a_k, b_k, bool)

Receive Message from Slaves (flag);

Iff lag = 0 thena_k+1=a_k;

b_k+1= max{[a_k, d_k−µ_k]∩S}

Iff alg = 1 thena_k+1=c_k; b_k+1=d_k; u_k =c_k; v_k=d_k;

Iff lag = 2 thena_k+1= min{[c_k+µ_k, b_k]∩S};

b_k+1=b_k; u_k=d_k; v_k=d_k Until b_k−a_k< ε

2; or card[a_k, b_k]∩S = 2;

bool= 1;{for the points of maximum}

Repeat h=h+ 1;

ν_h = inf{|x−y| |x, y∈[a_h, b_h]∩S};

Send Message to Slaves (a_h, b_h, bool);

Receive Message from Slaves (flag);

Iff lag = 0 thenah+1 = min{[c_j+νh, bh]∩S};

b_h+1 =b_h; u_h =d_h; v_h =d_h; Iff lag = 1 thena_h+1 =c_h; b_h+1 =d_h; u_h=c_h;

v_h=d_h;

Iff lag = 2 thena_h+1 =a_h; b_h+1= max{[a_h, d_h−ν_h]∩S};

u_h =d_h; v_h =d_h Until b_h−a_h< ε

2 or card[a_h, b_h]∩S ≤2;

Compute (WEF);

Compute (EF) else Ifbool= 0 then

Receive Message from Master (a_k, b_k, bool){Slaves execution}

ForID= 2,4 in parallel do Verify (card[a_k, b_k]∩S);

Take (c_k, d_k);

Compare (f(c_k), f(d_k), f lag);

End For;

Send Message to Master (flag) else

ifbool= 1 then

Receive Message from Master (a_h, b_h, bool);

ForID= 2,4 in parallel do Verify (card[a_h, b_h]∩S);

Take (c_h, d_h);

Compare (f(c_h), f(d_h), f lag);

End For

Send Message to Master (flag);

Remark 12. The cell named “flag” takes values corresponding with the cases enounced in Theorem 2.3, so

f lag=







0; ifI_c,d⁻ 6=∅orI_c,d⁺ 6=∅

1; if (I_c,d⁻ =∅ andI_c,d⁰ 6=∅) or (I_c,d⁺ =∅and I_c,d⁰ 6=∅) 2; else

.

Remark 13. Using this type of parallel execution, the amount of com- putation, and consequently the execution time, reduces at least three times,

compared with the serial algorithm.

REFERENCES

[1] Bj¨orklund, H.,Sandberg, S.,Vorobyov, S.,An Experimental Study of Algorithms for Completely Unimodal Optimization. Technical report 2002-030, October 2002. De- partment of Information Technology. Uppsala University.

[2] Chiorean, I.,Parallel calculus, Cluj-Napoca, Editura Microinformatica, 2000 (in Ro- manian).

[3] Chiorean, I.,Lupsa, L. andPopovici, N.,A Fibonacci type method for determine the set of efficient points of an unimodal multicriteria optimization, Creative Math. & Inf., 16, pp. 114–123, 2007.

[4] Demaine, E.D., Langerman, St., Optimizing a 2D Function Satisfying Unimodality Properties,www.eurocg.org/www.us.es/ewcg04/Articulos/demaine.ps

[5] Karmanov, V. G.,Programmation math´ematique, Editions Mir, Moscou, 1977.

[6] Luc, D. T.,Theory of Vector Optimization, Springer-Verlag, Berlin, 1989.

[7] Lups¸a, L. andBlaga, L. R.,Optimum points and integer unimodal functions, Automa- tion Computers Applied Mathematics,13, no. 1, pp. 121–130, 2004.

[8] Lups¸a, L., Popovici, N., A new algorithm for solving multicriteria unimodal opti- mization problems. Ann. Tiberiu Popoviciu Sem. Functional Equations, Approximation Convexity,3, pp. 123–130, 2005.

[9] Lups¸a, L.,Popovici, N.,Generalized Unimodal Multicriteria Optimization, Rev. Anal.

Num´er. Th´eor Approx.,35, pp. 65–70, 2006.

[10] Popovici, N.,Multicriteria optimization with unimodal objective functions, Approxima- tion and Optimization, Proceedings of the International Conference on Approximation and Optimization, Romania, ICAOR, Cluj-Napoca, July 29 - August 1, Vol.1, pp. 341–

344, 1996.

Received by the editors: February 12, 2008.