• Nu S-Au Găsit Rezultate

View of Local-global efficiency properties for multiobjective max-min programming

N/A
N/A
Protected

Academic year: 2022

Share "View of Local-global efficiency properties for multiobjective max-min programming"

Copied!
7
0
0

Text complet

(1)

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¸ IGANand 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 xX, yY,

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].

(2)

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) ab if and only ifaibi,for anyiJ ={1,2, ..., p},

(ii) a > bif and only if aibi, for anyiJ and there isjJ such that aj > bj,

(iii) abif and only if ai> bi,for anyiJ.

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, x00X andt∈(0,1), we have F(tx0+ (1− t)x00)≥Min(F(x0), F(x00)),

b) semistrictly quasiconcave if for any x0, x00X 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, x00X 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 DRn. i) A differentiable function f :DR 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.

(3)

ii) The differentiable functionf :DR 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 existxXsuch that Q(x, y)>

Q(x, y)(that is, xis a maximum-efficient solution for Q(·, y) onX) and there does not exist yY 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 xX 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 yY 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 existxXU such that Q(x, y) > Q(x, y) (that is x is a local maximum-efficient solution forQ(·, y)onX) and there does not existyYV 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 xXU 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 yYV 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 alliJ and eachxX,for whichQi(x, y)> Qi(x, y), there exists jJ − {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);

(4)

ii) for alliJ and eachyY,for whichQi(x, y)< Qi(x, y), there exists jJ − {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 EM mEM mW E, (1)

M mEM mLE, (2)

M mW EM mLW E, (3)

M mLEM 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 iJ ={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 DRn andX be a polyhedral set XD. Then a point x0X 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 −→

(5)

Rp is semiexplicitly quasiconcave for any yY; (ii) Q(x,·) : Y −→ Rp is semiexplicitly quasiconvex for anyxX. 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 mEM 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 existsx0Xsuch that Q(x0, y)> Q(x, y) or (b) there exists y0Y 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 mLEM 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 yY;

(ii) Q(x,·) : Y −→ Rp is explicitly quasiconvex for any xX. 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 existsx0X such thatQ(x0, y)Q(x, y) or (b) there existsy0Y 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).

(6)

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 yY and i = 1,2, ..., p, where XD;

(ii) Qi(x,·) :Y −→Ris pseudomonotonic twice continuously differentiable on the open subset E ⊆ Rm for any xX and i = 1,2, ..., p, where YE.

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 EM 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.

(7)

[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.

Referințe

DOCUMENTE SIMILARE

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

P. In this paper numerous necessary and sufficient conditions will be given for a vector to be the unique optimal solution of the primal problem, as well as for that of the

The aim of this paper is to characterize the sets of weakly-efficient solutions and efficient solutions for multicriteria optimization problem involving generalized unimodal

The partic- ularity of this procedure is the fact that the max-min optimal solution of the original problem is obtained by solving a single linear reverse-convex pro- gram with

In Section 4, for the particular case of the vector maximization set-valued fractional programming problem, we obtain some characterizations properties of efficient and

We establish also a sufficient optimality condition and a weak duality theo- rern for a max-min problern involving symmetric pseudo-convex objective func- tions and

The notion of local superconvergence is used when on a set of interiorpoints Z* (orZ*¡ the approximate solution has a convergence order greater than the global

Our main objective in this paper is to study the sufficient conditions of the form (1.3) for meromorphically convex functions of order α and for functions in a family that are convex