Rev. Anal. Num´er. Th´eor. Approx., vol. 33 (2004) no. 2, pp. 251–257 ictp.acad.ro/jnaat
LOCAL-GLOBAL EFFICIENCY PROPERTIES FOR MULTIOBJECTIVE MAX-MIN PROGRAMMING
S¸. T¸ IGAN∗and I. M. STANCU-MINASIAN†
Abstract. The purpose of this paper is to give sufficient conditions of general- ized concavity and convexity type for a local (weakly) max-min efficient solution to be a global (weakly) max-min efficient solution for an vector maxmin pro- gramming problem.
In the particular case of the vector max-min pseudomonotonic programming problem, we derive some characterizations properties of max-min efficient and properly max-min efficient solutions .
MSC 2000. 90C46, 90C29.
Keywords. Vector programming, pseudomonotonic programming, max-min ef- ficiency, proper max-min efficiency.
1. INTRODUCTION
The aim of this paper is to derive sufficient conditions of generalized con- cavity type for a local (weakly) max-min efficient solution to be a global (weakly) max-min efficient solution for an vector max-min set-valued pro- gramming problem.
LetX ⊂Rn Y ⊂Rmand Q:X×Y −→Rp be a vectorial function defined on X×Y.
The multiobjective max-min programming problem under consideration is formulated as
(VMMP.) Vmax-min Q(x, y), subject to x∈X, y∈Y,
where the vector maximin “Vmax-min” will be understood in the sense of efficiency that will be defined in different forms below in the next section.
The optimal solutions of theV M M P that we deal with include the concepts of efficient, weakly efficient, local efficient and properly efficient solutions that will be defined with respect to a semiorder relationship in Rp.
The paper is organized as follows. In Section 2 we introduce the notation and definitions, which will be used throughout of the paper.
∗Department of Medical Informatics, University of Medicine and Pharmacy “Iuliu Hat¸ieganu”, Cluj-Napoca, Romania, e-mail: [email protected].
†“Gheorghe Mihoc–Caius Iacob” Institute of Mathematical Statistics and Applied Math- ematics of the Romanian Academy, Bucharest, Romania, e-mail: [email protected].
In Section 3, we give sufficient conditions of generalized concavity type for a local (weakly) efficient solution to be a global (weakly) efficient solution of a V M M P.
In Section 4, for the particular case of the vector max-min pseudomonotonic programming problem, we obtain some characterizations properties of efficient and properly efficient solutions.
Some concluding remarks are made in the last section.
2. NOTATION AND DEFINITIONS
Next we recall some notations and concepts considered in [6] and introduce some max-min efficiency concepts.
Let a, b ∈ Rp be arbitrary vectors in Rp. Then we consider the following relations on the setRp:
(i) a≥b if and only ifai ≥bi,for anyi∈J ={1,2, ..., p},
(ii) a > bif and only if ai ≥bi, for anyi∈J and there isj∈J such that aj > bj,
(iii) abif and only if ai> bi,for anyi∈J.
Next, we consider some classes of generalized concave functions (see, e.g.
[4], [2], [3], [6]).
Definition 1. Let F :X−→Rp be a vector function, where X is a convex non-empty set in Rs. We say that F is:
a) quasiconcaveif for anyx0, x00∈X andt∈(0,1), we have F(tx0+ (1− t)x00)≥Min(F(x0), F(x00)),
b) semistrictly quasiconcave if for any x0, x00 ∈ X such that F(x0) 6=
F(x00), we have F(tx0+ (1−t)x00)> Min(F(x0), F(x00)), for each t∈ (0,1),
c) semiexplicitly quasiconcave if it is quasiconcave and semistrictly qua- siconcave,
d) strictly quasiconcave if for all x0, x00 ∈ X such that F(x0) 6= F(x00) , we haveF(tx0+ (1−t)x00) Min(F(x0), F(x00)), for each t∈(0,1), e) explicitly quasiconcave if it is quasiconcave and strictly quasiconcave,
f) quasiconvexe, semi strictly quasiconvex, semiexplicitly quasiconvex, strictly quasiconvex and explicitly quasiconvex if (−F) is quasicon- cave, semistrictly quasiconcave, semiexplicitly quasiconcave, strictly quasiconcave and explicitly quasiconcave respectively.
Obviously, from Definition 1,F is semiexplicitly quasiconcave if it is explic- itly quasiconcave. However, the converse is not true (see, e.g. [2]).
Definition 2. Let D be an open convex set D⊆Rn. i) A differentiable function f :D→R is pseudoconvex if
∇f(x)(y−x)≥0 =⇒f(y)≥f(x),∀x, y∈D, where ∇f(x) is the gradient of the function f on the point x.
ii) The differentiable functionf :D→R is called pseudomonotonic if f and−f are pseudoconvex.
Next we consider for Problem M SV P some efficiency concepts based on the semiorder relationships presented above (see, (i)–(iii)).
Definition 3. A point (x, y) ∈ X ×Y is said to be a max-min efficient solution to ProblemV M M P if there does not existx∈Xsuch that Q(x, y)>
Q(x, y)(that is, xis a maximum-efficient solution for Q(·, y) onX) and there does not exist y ∈ Y such that Q(x, y) > Q(x, y) (that is, y is a minimum- efficient solution for Q(x,·) on Y).
Let M mE denote the set of all efficient max-min solutions to Problem V M M P.
Definition 4. A point (x, y) ∈ X ×Y is said to be a weakly max-min efficient solution to Problem V M M P if there does not exist x ∈X such that Q(x, y)Q(x, y)(that isx is a weakly maximum-efficient solution forQ(·, y) on X) and there does not exist y∈Y such that Q(x, y) Q(x, y) (that is, y is a weakly minimum-efficient solution for Q(x,·) onY).
Let M mW E denote the set of all max-min efficient solutions to Problem V M M P.
Definition 5. i) A point (x, y) ∈X×Y is said to be alocal max-min efficient solutionto ProblemV M M P if there does not existx∈X∩U such that Q(x, y) > Q(x, y) (that is x is a local maximum-efficient solution forQ(·, y)onX) and there does not existy∈Y∩V such that Q(x, y) > Q(x, y) (that is y is a local minimum-efficient solution for Q(x,·) on Y), for some neighborhoods U of x and V of y.
ii) A point (x, y) ∈X×Y is said to be a local weakly max-min efficient solution to Problem V M M P if there does not exist x ∈ X∩U such that Q(x, y) Q(x, y) (that is x is a local weakly maximum-efficient solution for Q(·, y) on X) and there does not exist y ∈ Y ∩V such thatQ(x, y) Q(x, y) (that is, y is a local weakly minimum-efficient solution forQ(x,·) onY),for some neighborhoods U of x and V of y.
Let M mLE (M mLW E) denote the set of all local (weakly) max-min effi- cient solutions to Problem V M M P.
Definition6. LetQ(x, y) = (Q1(x, y), ..., Qp(x, y)),for any (x, y)∈X×Y.
A max-min efficient solution (x, y) ∈X×Y to Problem V M M P is said to be a properly max-min efficient solutionif there exists a scalarM >0such that:
i) for alli∈J and eachx∈X,for whichQi(x, y)> Qi(x, y), there exists j ∈ J − {i}, for which Qj(x, y) > Qj(x, y) and QQi(x,y)−Qi(x,y)
j(x,y)−Qj(x,y) ≤ M (that is,x is a properly maximum-efficient solution for Q(·, y) on X);
ii) for alli∈J and eachy∈Y,for whichQi(x, y)< Qi(x, y), there exists j ∈ J − {i}, for which Qj(x, y) > Qj(x, y) and QQi(x,y)−Qi(x,y)
j(x,y)−Qj(x,y) ≤ M (that is,y is a properly minimum-efficient solution for Q(x,·) onY).
Let M mP E denote the set of all properly efficient solutions to Problem V M M P.
From Definition 6, it follows that (x, y) ∈ X ×Y is a properly max-min efficient solution to ProblemV M M P if and only ifxis a properly maximum- efficient solution forQ(·, y) onXandyis a properly minimum-efficient solution forQ(x,·) onY.
Obviously, from Definitions 3–6, we have the following relationship between the different classes of optimal solutions of V M M P:
M mP E⊂M mE⊂M mW E, (1)
M mE⊂M mLE, (2)
M mW E⊂M mLW E, (3)
M mLE⊂M mLW E.
(4)
The efficiency notions given by Definitions 3-5 are analogous to that considered for vector real valued objective functions in refs. [2], [3]. The proper efficiency concept is a generalization of that introduced by Geoffrion [1].
3. SUFFICIENT CONDITIONS FOR LOCAL-GLOBAL EFFICIENCY PROPERTIES
We now generalize to vector max-min optimization problems a character- ization of local efficient solutions obtained in Refs. [2], [3] for usual vector optimization problems or for vector set-valued optimization problems [6]. A similar result is given for local weakly efficient solutions.
We mention that some local-global efficiency properties for minimum-risk problems was recently obtained by Tigan and Stancu-Minasian [5].
Given p ≥ 2 and X 6= ∅, X ⊆ Rnan arbitrary set, consider the function f :X →Rp, f(x) = (f1(x), f2(x), . . . , fp(x)),∀x ∈X, where fi :X → R, for any i∈J ={1,2, . . . , p}.
Next, we need the following property due to Weber [7] which provide suffi- cient conditions in order to a pseudo-monotonic multi-objective program has
“complete proper efficiency property”, that is any efficient solution to this problem is also properly efficient.
Lemma7. [7]Let fk (k∈ {1,2, . . . , p}be pseudo-monotonic functions twice continuously differentiable on the open subset D⊆Rn andX be a polyhedral set X ⊆ D. Then a point x0 ∈ X is maximum (minimum) efficient for the pseudo-monotonic function f = (f1, f2, . . . , fp) on X if and only if it is properly maximum (minimum) efficient.
Theorem 8. Let X ⊂ Rn and Y ⊂ Rm be given non-empty convex sets and Q : X×Y −→ Rp be a vector function such that: (i) Q(·, y) : X −→
Rp is semiexplicitly quasiconcave for any y ∈ Y; (ii) Q(x,·) : Y −→ Rp is semiexplicitly quasiconvex for anyx∈X. Then(x, y)∈X×Y is a local max- min efficient solution to Problem V M M P if and only if (x, y) is a (global) max-min efficient solution (i.e. M mE =M mLE).
Proof. From (2) we haveM mE⊂M mLE.To prove the converse inclusion, assume to the contrary that (x, y)∈X×Y is a local max-min efficient solution (with respect to the neighborhoodsU of x andV of y), which is not a global max-min efficient solution. This means that: (a) there existsx0∈Xsuch that Q(x0, y)> Q(x, y) or (b) there exists y0 ∈Y such thatQ(x, y0)< Q(x, y).In the case (a), since Q(·, y) is semiexplicitly quasiconcave, we have
(5) Q(tx0+ (1−t)x, y)> Q(x, y), for all t∈(0,1).
But for t sufficiently close to zero,x(t) =tx0+ (1−t)x will be in the neigh- borhoodU of x. But this shows by (5) and Definition 3 that (x, y) would not be a local max-min efficient solution, which is a contradiction.
In the case (b), sinceQ(x,·) is semiexplicitly quasiconvex, we have (6) Q(x, ty0+ (1−t)y)< Q(x, y), for allt∈(0,1).
But fort sufficiently close to zero, y(t) = ty0+ (1−t)y will be in the neigh- borhoodV of y. But this shows by (6) and Definition 3 that (x, y) would not be a local max-min efficient solution, which is a contradiction too.
Therefore, we proved that M mLE ⊂M mE, which toogether with (2) im-
plies the equality M mE=M mLE.
We supplement the result in Theorem 8 by a similar one for weakly efficient solutions.
Theorem9. Let X⊂Rn andY ⊂Rm be given non-empty convex sets and Q:X×Y −→Rp be a vector function such that:
(i) Q(·, y) :X −→Rp is explicitly quasiconcave for any y∈Y;
(ii) Q(x,·) : Y −→ Rp is explicitly quasiconvex for any x ∈ X. Then (x, y)∈X×Y is a local weakly max-min efficient solution to Problem V M M P if and only if (x, y) is a (global) weakly max-min efficient solution.
Proof. One can follow the lines of previous proof. To prove the nontrivial implication, assume to the contrary that (x, y) ∈ X ×Y is a local weakly max-min efficient solution (with respect to the neighborhoodsU ofxandV of y), which is not a global weakly max-min efficient solution. This means that:
(a) there existsx0 ∈X such thatQ(x0, y)Q(x, y) or (b) there existsy0∈Y such that Q(x, y0) Q(x, y). In the case (a), since Q(·, y) is semiexplicitly quasiconcave, we have
(7) Q(tx0+ (1−t)x, y)Q(x, y), for all t∈(0,1).
But for t sufficiently close to zero,x(t) =tx0+ (1−t)x will be in the neigh- borhoodU of x. But this shows by (7) and Definition 4 that (x, y) would not be a local max-min efficient solution, which is a contradiction.
In the case (b), sinceQ(x,·) is semiexplicitly quasiconvex, we have (8) Q(x, ty0+ (1−t)y)Q(x, y), for all t∈(0,1).
But fort sufficiently close to zero, y(t) = ty0+ (1−t)y will be in the neigh- borhoodV of y. But this shows by (8) and Definition 4 that (x, y) would not be a local max-min efficient solution, which is a contradiction too.
Theorem 10. Let X ⊂ Rn and Y ⊂ Rm be given non-empty convex sets and Q:X×Y −→Rp be a vector function such that:
(i) Qi(·, y) : X −→ R is pseudomonotonic twice continuously differen- tiable on the open subset D ⊆ Rn for any y ∈ Y and i = 1,2, ..., p, where X⊂D;
(ii) Qi(x,·) :Y −→Ris pseudomonotonic twice continuously differentiable on the open subset E ⊆ Rm for any x ∈ X and i = 1,2, ..., p, where Y ⊂E.
Then(x, y)∈X×Y is a max-min efficient solution to Problem V M M P if and only if (x, y) is a properly max-min efficient solution.
Proof. From (1) we have M mP E ⊂ M mE. In order to prove the con- verse inclusion, let (x, y)∈X×Y be a max-min efficient solution to Problem V M M P. Then, by Definition 3, it follows that x is a maximum-efficient so- lution for Q(·, y) on X and y is a minimum-efficient solution for Q(x,·) on Y. From hypothesis (i) and (ii), by Lemma 7, it follows that x is a properly maximum-efficient solution for Q(·, y) on X and y is a properly minimum- efficient solution forQ(x,·) onY.Then, by Definition 6, it result that (x, y) is a properly max-min efficient solution to Problem V M M P.
4. CONCLUSIONS
In this paper we obtained sufficient conditions implying generalized concav- ity and convexity assumptions of the objective functions, in order to a local (weakly) efficient solution be a global (weakly) efficient solution for an vector max-min programming problem.
In the particular case of the vector pseudomonotonic max-min programming problem, we derived some characterizations properties of efficient and properly efficient solutions.
REFERENCES
[1] Geoffrion, A. M., Proper efficiency and the theory of vector maximization,J. Math.
Anal. Appl.,22, no. 3, pp. 618–630, 1968.
[2] Luc, D. T.andSchaible, S.,Efficiency and generalized concavity, J. Optim. Theory Appl.,94, no. 1, pp. 147–153, 1997.
[3] Ruiz-Canales, P.andRufian-Lizana, A.,A characterization of weakly efficient points, Math. Progr.,68, pp. 205–212, 1995.
[4] Stancu-Minasian, I. M.,Metode de rezolvare a problemelor de programare fract¸ionar˘a, Editura Academiei Romˆane, Bucure¸sti, 1992 (in Romanian).
[5] Tigan, S.and Stancu-Minasian, I. M., Efficiency properties for stochastic multiob- jective programming,In Proceedings of “Tiberiu Popoviciu” Itinerant Seminar of Func- tional Equations, Approximation and Convexity, Cluj-Napoca, 2002, E. Popoviciu (eds.), pp. 271–290, Editura SRIMA, Cluj-Napoca, 2002.
[6] Tigan, S.andStancu-Minasian, I. M.,Efficiency and generalized concavity for multi- objective set-valued programming,Rev. Anal. Num´er. Th´eor. Approx.,32, no. 2, pp. 235–
242, 2003.
[7] Weber R.,Pseudomonotonic Multiobjective Programming. Discussion Paper, Institute of Operations Research, Department of Economics, University of Saarland, Saarbruecken, 1982.
Received by the editors: April 15, 2004.