Optimality Conditions and Geometric Properties of a Linear Multilevel Programming Problem with Dominated Objective Functions: [1]

Abstract

In this paper, a model of a linear multilevel programming problem with dominated objective functions (LMPPD(l)) is proposed, where multiple reactions of the lower levels do not lead to any uncertainty in the upper-level decision making. Under the assumption that the constrained set is nonempty and bounded, a necessary optimality condition is obtained. Two types of geometric properties of the solution sets are studied. It is demonstrated that the feasible set of LMPPD(l) is neither necessarily composed of faces of the constrained set nor necessarily connected. These properties are different from the existing theoretical results for linear multilevel programming problems.

journal of optimization theory and applications: Vol. 123, No. 2, pp. 409429, November 2004 ( 2004)Optimality Conditions and Geometric Properties of a

Linear Multilevel Programming Problem withDominated Objective Functions1G. Z. Ruan,2 S. Y. Wang,3 Y. Yamamoto,4 and S. S. Zhu5Communicated by H. P. BensonAbstract. In this paper, a model of a linear multilevel programming

problem with dominated objective functions (LMPPD(l)) is proposed,

where multiple reactions of the lower levels do not lead to any uncertainty in the upper-level decision making. Under the assumption that

the constrained set is nonempty and bounded, a necessary optimality condition is obtained. Two types of geometric properties of the

solution sets are studied. It is demonstrated that the feasible set of

LMPPD(l) is neither necessarily composed of faces of the constrained

set nor necessarily connected. These properties are different from the

existing theoretical results for linear multilevel programming problems.Key Words. Bilevel programming, multilevel programming, upper

semicontinuity, connectedness.1. IntroductionAs an extension of the Stackelberg games, Candler and Norton

(Refs. 12) proposed multilevel programming models for decentralized1This work was supported by NFSC, MADIS, and CAS. The authors are grateful to Professor Benson and two anonymous referees for helpful comments and suggestions.2Professor, Department of Mathematics, Xiangtan University, Xiangtan, Hunan, China.

3Professor, Institute of Systems Science, Academy of Mathematics and Systems Sciences,

Chinese Academy of Sciences, Beijing, China. He is also with the School of Business

Administration, Hunan University, Changsha, Hunan, China.4Professor, Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba,

Japan.5Lecturer, Department of Management Science, School of Management, Fudan University,

Shanghai, China. He is also with the Institute of Systems Science, Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences, Beijing, China.

4090022-3239/04/1100-0409/0 2004 Springer Science+Business Media, Inc.410 JOTA: VOL. 123, NO. 2, NOVEMBER 2004decision-making problems in 1977. This type of problems is characterized by multiple decision makers at various hierarchical levels, each

independently dominating a subset of the decision variables with different

and often conicting objectives.Multilevel programming has been studied extensively since the 1980s,

especially for the bilevel case (e.g., Refs. 311). The three-level case was

studied by Bard (Ref. 12), Wen and Bialas (Ref. 13), and White (Ref. 14).

The l-level, l> 3, programming problems were investigated by Bard (Ref.15), Benson (Ref. 16), White (Ref. 17), and Ruan and Zuo (Ref. 18). Multilevel programming has been applied widely to many decision situations,

for example, water quality problems (Ref. 19), trafc planning (Ref. 20),

tax credits determination (Ref. 21), and pollution control policy (Ref. 22).

Vicente and Calamai (Ref. 23) presented a bibliographic review, in which

they summarized the main developments of algorithms and applications of

multilevel programming up to 1994.Wang and Feng (Ref. 24) proposed a special class of bilevel programming problems, called bilevel programming problems with dominated

objective functions. In their model, the lower-level decision maker reports

only the value of his/her objective function to his/her upper-level decision

maker. In this paper, we suggest a general model for an l-level programming problem with dominated objective functions (MPPD(l)).In the decision-making process of a multilevel system MPPD(l), the

decision maker of level 1 dominates the vector of decision variables x1;

he/she chooses values for the variables x1 rst in an attempt to maximize his/her objective function f1(x1,f2(x2,f3(x3,... ))). For given values

of x1, the decision maker of level 2 chooses values for x2, in an attempt

to maximize his/her objective function f2(x2,f3(x3,...)). Similarly, values

of x3,...,xl are to be chosen by the decision makers of level 3 to level

l, respectively and orderly, in an attempt to maximize their own objective

functions. To share the common resources, all the levels must be restricted

by a common constraint. Thus, a general model of MPPD(l) can be formulated as follows:maxx1f1(x1,f2(x2,f3(x3,... ))), where x2 solvesf2(x2,f3(x3,f4(x4,... ))), where x3 solvesfl1(xl1,fl(xl)), where xl solves

maxxlfl (xl ),s.t. g(x1,...,xl ) 0.maxx2..maxxl1JOTA: VOL. 123, NO. 2, NOVEMBER 2004 411Without loss of generality, it is assumed that the objective functions

of two successive levels are opposite, i.e., fi is a strictly decreasing function of fi+1,i = 1,...,l 1. Otherwise, these two levels could be aggregated. In particular, if the two objective functions f1 and f2 in MPPD(2)

satisfy f1 =f2, then this is a maxmin problem. The original bilevel programming models proposed in the 1970s and the early 1980s consider

only the case that the two levels are restricted by a common constraint.

Later on, however a few authors considered multilevel programming models where each level contains a local restriction, except for the common

one; see for example Vicente and Calamai (Ref. 23) and Benson (Ref. 16).

Although the local constraints can be treated generally as the common

constraints, this type of MPPD(l) may deserve further investigation due to

its particular structure.Most of the publications on multilevel programming make the crucial

assumption that the reactions of each lower level are unique; i.e., for any

given and permissible values of the decision variables dominated by the

upper-level decision makers, the lower-level decision making problem has a

unique optimal solution. However, this is not always the case. But without

this questionable assumption, some uncertainty of the upper-level decision making process may occur. Multiple reactions in multilevel programming have been investigated by several authors such as Bard and Moore

(Ref. 25), Hansen et al. (Ref. 26), Wang and Wang (Ref. 27), Loridan

and Morgan (Ref. 28), Wang et al. (Ref. 29), and Dempe (Ref. 30). In

their papers, methods are used to deal with this type of uncertainty, for

instance, the maxmin method in pessimistic decision making and the cooperation principle in game theory. Fortunately, in MPPD(l), the multiple

reactions of the lower level do not lead to any uncertainty of the upperlevel decision making, since the lower-level decision maker reports only the

value of his/her objective function to his/her upper-level decision maker.

Because it is not required to assume that the reactions of the lower level

are unique, the relation of variable-value selections between the upper level

and the lower level of MPPD(l) is a point-to-set mapping, whereas it is a

point-to-point mapping under that assumption made in most of the publications. If the reactions of the lower levels of MPPD(l) are all unique,

then the linear case of MPPD(l) is a special case of the model proposed

by Bard (Ref. 15) and Ruan and Zuo (Ref. 18). But MPPD(l) differs from

the model investigated by Benson (Ref. 16). In the Benson model, the

objective of each level is a function of the decision variables controlled

only by the local decision maker himself/herself, expect the rst one.This paper is organized as follows. In Section 2, we present the model

of a linear l-level programming problem with dominated objective functions (LMPPD(l)) and introduce some concepts. In Sections 3 and 4,412 JOTA: VOL. 123, NO. 2, NOVEMBER 2004we study the necessary optimality conditions and geometric properties of

LMPPD(l); two examples are given to illustrate the results. Finally, we

give some conclusions in Section 5.2. Model and DenitionsIn this paper, we consider the following problem LMPPD(l):maxf1(x1,...,xl ) = c

T

1 x1 + a1f2(x2,...,xl),where x2 solvesx1maxf2(x2,...,xl ) = c

T

2 x2 + a2f3(x3,...,xl),where x3 solvesx2..maxT

l1xl1 + al1fl(xl),where xl solvesxl1fl1(xl1,xl) = cmax

xlfl (xl ) = cT

l xl ,s.t. A1x1 + A2x2 ++ Alxl b,where xi ,ci Rni , Ai Rmni , i = 1,...,l,aj R, aj < 0, j = 1,...,l 1,

b Rm, and fi is linear for i = 1,...,l.Denote the constrained set of LMPPD(l)as S, i.e.,S [defines] [braceleftBig](x1,...,xl ) R[summationtext]l

i=1 ni |A1x1 + A2x2 ++ Alxl b[bracerightBig].Assumption 2.1. The constrained set S is nonempty and bounded.DenoteXk [defines] [braceleftBig] (

x1,...,

xk) R[summationtext]

k

i=1 ni |(xk+1,...,xl) such that(

x1,...,

xk,xk+1,...,xl) S[bracerightBig],k = 1,...,l 1.From Assumption 2.1, it is clear that Xk is nonempty and bounded. Based

on the above notations, we dene the solution sets of LMPPD(l)ina

backward way beginning with level l. To facilitate the discussion, we present these denitions in a form that may be different from the previous

ones employed by other researchers. However, they are consistent essentially with each other.After the decisions of level 1 to level l 1 are made, the values

of variables x1,...,xl1 are given. For given ( x1,...,

xl1) Xl1, theJOTA: VOL. 123, NO. 2, NOVEMBER 2004 413decision making problem of level l is equivalent to the following linear

programming problem:maxcT

l xl |Alxl b A1

x1 Al1

xl1[bracerightbig].Based on this linear program, we give the following denitions.xlDenition 2.1. The setJl (

x1,...,

xl1) [defines] [braceleftBig](

x1,...,

xl1,xl) R[summationtext]l

i=1 ni |(

x1,...,

xl1,xl) S[bracerightBig]

is called the permissible set of level l of LMPPD(l) with respect to(

x1,...,

xl1), whileJl [defines] [uniondisplay](

x1,...,

xl1)Xl1Jl (

x1,...,

xl1)is called the permissible set of level l of LMPPD(l); the setZl (

x1,...,

xl1) [defines] [braceleftBig] [parenleftbig]

x1,...,

xl1,x

l[parenrightbig] R[summationtext]l

i=1 ni |x

larg[braceleftbig]maxfl (xl ) :(

x1,...,

xl1,xl) Jl(

x1,...,

xl1)[bracerightbig][bracerightBig]

is called the feasible set of level l of LMPPD(l) with respect to ( x1,...,xl

xl1), whileZl [defines] [uniondisplay](

x1,...,

xl1)Xl1Zl (

x1,...,

xl1)is called the feasible set of level l of LMPPD(l).It is obvious thatZl Jl = S.Furthermore, for given (

x1,...,

xl2)Xl2, LMPPD(l) reduces to LMPPD(2),

which is equivalent to the following problem:maxT

l1xl1 + al1fl(xl),s.t. ( x1,...,

xl2,xl1,xl) Zl.For the above optimization problem, we have the following denitions.xl1,xlfl1(xl1,xl) = c414 JOTA: VOL. 123, NO. 2, NOVEMBER 2004Denition 2.2. The setJl1(

x1,...,

xl2)[defines] [braceleftBig](

x1,...,

xl2,xl1,xl)

R[summationtext]l

i=1 ni |(

x1,...,

xl2,xl1,xl) Zl[bracerightBig]

is called the permissible set of level l 1 of LMPPD(l) with respect to

( x1,...,

xl2), while the setJl1 [defines] [uniondisplay]

(

x1,...,

xl2)Xl2Jl1(

x1,...,

xl2)is called the permissible set of level l 1 of LMPPD(l); the setZl1(

x1,...,

xl2)Zl1(

x1,...,

xl2)is called the feasible set of level l 1 of LMPPD(l).It is obvious thatZl1 Jl1 = Zl.For level k + 1, k = l 3,..., 1, the corresponding concepts of solution sets

can be dened similarly as follows.Denition 2.3. The setJk+1(

x1,...,

xk)[defines] [braceleftBig](

x1,...,

xk,xk+1,...,xl) R[summationtext]l

i=1 ni |(

x1,...,

xk,xk+1,...,xl) Zk+2[bracerightBig]

is called the permissible set of level k + 1 of LMPPD(l) with respect to

( x1,...,

xk), while the setJk+1 [defines] [uniondisplay](

x1,...,

xk )XkJk+1(

x1,...,

xk)fl1(xl1,xl):(

x1,...,

xl2,xl1,xl) Jl1(

x1,...,

xl2)[bracerightbig][bracerightBig]

is called the feasible set of level l 1 of LMPPD(l) with respect to

( x1,...,

xl2), while the setZl1 [defines] [uniondisplay]

(

x1,...,

xl2)Xl2[defines] [braceleftBig] [parenleftbig] x1,...,

xl2,x

l1,x

l1,x

l[parenrightbig] R[summationtext]l

i=1 ni | [parenleftbig]x

l[parenrightbig] arg[braceleftbig]maxxl1,xlJOTA: VOL. 123, NO. 2, NOVEMBER 2004 415is called the permissible set of level k + 1 of LMPPD(l); the setZk+1(

x1,...,

xk)[defines] [braceleftBig](

x1,...,

xk,x

k+1,...,x

l ) R[summationtext]l

i=1 ni |(x

k+1,...,x

l )argmax[braceleftbig]fk+1(xk+1,...,xl) :(

x1,...,

xk,xk+1,...,xl) Jk+1(

x1,...,

xk)[bracerightbig][bracerightBig]

is called the feasible set of level k + 1 of LMPPD(l) with respect to

( xk+1,..., xlx1,...,

xk), while the setZk+1 [defines] [uniondisplay](

x1,...,

xk )XkZk+1(

x1,...,

xk)is called the feasible set of level k + 1 of LMPPD(l).It is clear thatZk Jk = Zk+1,k =2,...,l 2.Denition 2.4. The set(l) [defines] [braceleftBig](x1,...,xl ) R[summationtext]l

i=1 ni |(x1,...,xl) Z2[bracerightBig]

is called the feasible set of LMPPD(l).It is clear that(l) = J1 = Z2.In Section 3, we rewrite (l) as J1 for compactness of notations. J1 is said

also to be the feasible set or the permissible set of level 1, whereas whenk> 1, the permissible set and the feasible set are denoted by Jk and Zk

respectively, since they are not the same sets.Denition 2.5. Letx

1 ,...,x

l[parenrightbig] (l). For any given (x1,...,xl ) (l),iff1x

1 ,...,x

l[parenrightbig] f1(x1,...,xl ),thenis called an optimal solution of LMPPD(l).Generally, for given (

x1,...,

xk) Xk, LMPPD(l) reduces to a linear(l k)-level programming problem LMPPD(l k). The two sets dened byx

1 ,...,x

l[parenrightbig]416 JOTA: VOL. 123, NO. 2, NOVEMBER 2004the components (xk+1,...,xl) of Jk+1(

x1,...,

xk) and Zk+1(

x1,...,

xk) are

respectively the feasible set and the optimal solution set of LMPPD(l k).

See the examples in Section 4 for an intuitive understanding of the above

concepts.Finally, we recall two denitions that are useful in the discussion on

geometric properties (see Section 4).Denition 2.6. See Section 18 of Ref. 31. Let C0 be a convex subset

of a closed convex set C. If every closed line segment in C with a relative interior point in C0 has both endpoints in C0, then C0 is called a face

of C.Denition 2.7. See Ref. 32. Let T Rm and X Rn. The point-to-set

mapping F from T to 2X is said to be upper semicontinuous at t T ,if

{tk} T, tk t, xk F(tk), and xk x, k +, imply that x F(t).3. Optimality ConditionsOptimality conditions for bilevel programming problems have been

studied by many authors such as Bard (Refs. 5, 7), Bialas (Ref. 6), Ye

(Ref. 9), and Yezza (Ref. 10). Benson (Ref. 16) and Ruan and Zuo

(Ref. 18) investigated the optimality conditions for their multilevel programming models. In this section, we present a necessary optimality condition for LMPPD(l). First, we quote a lemma on optimality conditions

for LMPPD(2) as follows.Lemma 3.1. Let (

x1,

x2) be a point of the nonempty and bounded

constrained set S of the following LMPPD(2):max

x1f1(x1,x2) = cT

1 x1 + a1f2(x2),where x2 solvesmaxf2(x2) = cT

2 x2,s.t. A1x1 + A2x2 b.Then, (

x1,

x2) Z2if and only if there existsx2w {w Rm|wT A2 = cT

2 ,w 0}such thatwT (A1

x1 + A2

x2 b) =0.JOTA: VOL. 123, NO. 2, NOVEMBER 2004 417Remark 3.1. Lemma 3.1 was given by a few authors such as Bard

(Ref. 5), Bialas and Karwan (Ref. 6), Wang and Feng (Ref. 24). It should

be mentioned that Bard (Ref. 5) and Bialas and Karwan (Ref. 6) proposed

respectively the optimality conditions for general bilevel programs and linear bilevel programs where the reactions of the lower level are assumed to

be unique. These results can be extended for problem LMPPD(2).For given (

x1,...,

xl2) Xl2, LMPPD(l) reduces to LMPPD(2). By

Lemma 3.1, ( x1,...,

xl ) Zl(

x1,...,

xl1) if and only if there existswl Vl [defines] [braceleftBig]wl Rm|wT

l Al = cT

l ,wl 0[bracerightBig]such thatwT

l (A1

x1 ++ Al

xl b) =0.Furthermore, we prove that, for given (

x1,...,

xl ) Jl1(

x1,...,

xl2),if(

x1,...,

xl ) Zl1(

x1,...,

xl2) Jl2(

x1,...,

xl3),then there exists (

wl ,

wl1) Vl1such thatwT

i (A1

x1 ++ Al

xl b) =0,i = l, l 1,whereVl1 [defines] [braceleftBig](wl ,wl1) R2m|ll 0 such that

wTl Al = cT

l ,T

Al1 = cwl1 +

l

l wl[parenrightBig]T

l1,T

Al = al1cwl1 +

l

l wl[parenrightBig]T

l ,T

(A1

x1 ++ Al2

xl2+Al1xl1 + Alxl b) wl1+

l

l wl[parenrightBig]0,for all (

x1,...,

xl2,xl1,xl) Jl1(

x1,...,

xl2),.In general, for given (

x1,...,

xlk) Xlk,2 k l 1, LMPPD(l)

reduces to LMPPD(k). In this case, we have the following theorem.Theorem 3.1. Let (

x1,...,

xl ) Jlk+1(

x1,...,

xlk).If(

x1,...,

xl ) Zlk+1(

x1,...,

xlk) Jlk(

x1,...,

xlk1),wl ,wl1 0418 JOTA: VOL. 123, NO. 2, NOVEMBER 2004then there exists (

wl ,...,

wlk+1) Vlk+1such thatwT

i (A1

x1 ++ Al

xl b) =0,i = l,...,l k + 1,whereVlk+1 [defines] [braceleftbigg](wl,...,wlk+1) Rkm|ll ,ll1,l1

l1; ... ; l

lk+2,...,lk+2lk+20,such thatwT

l Al = cT

l ,wl1 +

l

l wl[parenrightbig]TAl1 = cT

l1,wl1 +

l

l wl[parenrightbig]TAl = al1cT

l ,..wlk+1 +

l

lk+

2wl ++

lk+

2lk+

2wlk+2[parenrightBig]TAlk+1 = cT

lk+1,wlk+1 +

l

lk+

2wl ++

lk+

2lk+

2wlk+2[parenrightBig]TAlk+2 = alk+1cT

lk+2,..

wlk+1 +

l

lk+

2wl ++

lk+

2lk+

2wlk+2[parenrightBig]TAl = cT

lk1[productdisplay]j=1alk+j ,(wlk+1 +

l

lk+2wl ++

lk+2lk+2wlk+2)T (A1

x1 ++ Alk

xlk+Alk+1xlk+1 ++ Alxl b) 0,for all (

x1,...,

xlk ,xlk+1,...,xl) Jlk+1(

x1,...,

xlk ),wl,...,wlk+1 0.Proof. For simplicity, we show only the case l = 3 in details.(a) Let (

x1,

x2,

x3) J3(

x1,

x2). From Lemma 3.1, we know that(

x1,

x2,

x3) Z3(

x1,

x2) J2(

x1)if and only if there existsw3 V3 [defines] {w3 Rm|wT

3 A3 = c

T

3 ,w3 0} (1)

such thatwT

3 (A1

x1 + A2

x2 + A3

x3 b) =0.JOTA: VOL. 123, NO. 2, NOVEMBER 2004 419(b) Let (

x1,

x2,

x3) J2(

x1). It is obvious that (

x1,

x2,

x3) Z3(

x1,

x2).From (a), we know that ( x1,

x2,

x3) Z2(

x1) J1if and only if there exists

w3 such that (

x2,

x3,

w3) is an optimal solution to the following problem:maxT

3 x3,x2,x3,w3cT2 x2 + a2cs.t. A1

x1 + A2x2 + A3x3 b,

wT3 (A1

x1 + A2x2 + A3x3 b) =0,wT3 A3 = cT

3 ,w3 0.For given

w3 V3, consider the following linear programming problem

(LPP):

maxT

3 x3,x2,x3cT2 x2 + a2cs.t. A1

x1 + A2x2 + A3x3 b,wT

3 (A1

x1 + A2x2 + A3x3 b) =0.Sincew3 0 and A1

x1 + A2x2 + A3x3 b 0,we see thatwT

3 (A1

x1 + A2x2 + A3x3 b) =0is equivalent towT

3 (A1

x1 + A2x2 + A3x3 b) 0.Therefore, the dual problem of LPP is

minw2,33wT2 (b A1

x1) + 3

3

wT3 (b A1

x1),s.t. wT2 A2 + 3

3

wT3 A2 = cT

2 ,wT2 A3 + 3

3

wT3 A3 = a2cT

3 ,0,33 0. (2)By the duality theory of linear programming, (

x2,

x3) is an optimal solu-w2 tion of LPP if and only if there exist w2 Rm,

w2 0, 33 R, 33 0 suchthatwT

3 (A1

x1 + A2

x2 + A3

x3 b) =0, (3)420 JOTA: VOL. 123, NO. 2, NOVEMBER 2004wT

2 A2 +

33

wT

3 A2 = c

T

2 , (4)wT

2 A3 +

33

wT

3 A3 = a2c

T

3 , (5)wT

2 (b A1

x1) +

33

wT

3 (b A1

x1) = c

T

2

x2 + a2cT

3

x3. (6)Substituting (4)(5) into (6), by (3) we obtainwT

2 (A1

x1 + A2

x2 + A3

x3 b) =0. (7)If (

x1,

x2,

x3) Z2(

x1) J1, then for any (

x1,x2,x3) J2(

x1),wehavecT2 x2 + a2c[parenrightBig] 0. (8)

Substituting (4), (5), (6) into (8), we obtaincT2 x2 + a2cT

3 x3 cT

3 x3 [parenleftBig]cT2

x2 + a2cT

3

x3T

2

x2 a2cT

3

x3= [parenleftBig]

wT2 + 33

wT3[parenrightBig] (A2x2 + A3x3) [parenleftBig]

wT2 + 33

wT3[parenrightBig] (b A1

x1)= [parenleftBig]

wT2 + 33

wT3[parenrightBig] (A1

x1 + A2x2 + A3x3 b)0, for all (

x1,x2,x3) J2(

x1). (9)From (1)(5), (7), (9), we know that the conclusion holds for l = 3.When l> 3, for the given (

x1,...,

xh) and

wl ,...,

wh+2, we consider

the following linear programming problems ordered according to the indexh, h = l 1,...,l k:max fh+1(xh+1,...,xl)

s.t. A1 x1 ++ Ah

xh + Ah+1xh+1 ++ Alxl b,

wT

i (A1

x1 ++ Ah

xh + Ah+1xh+1 ++ Alxl b) =0,i = l,...,h +2.We can prove the general case (l > 3) by the duality theory of linear programming in the same way we proved the three level case. The proof is

completed.Although we obtain a necessary optimality condition, it is hard to

verify this optimality condition when l> 3. The larger the level number l,

the more difcult the verication. Thus, more practical optimality conditions need to be investigated.JOTA: VOL. 123, NO. 2, NOVEMBER 2004 4214. Geometric PropertiesGeometric properties of linear multilevel programming problems were

investigated by Bard (Ref. 15), Benson (Ref. 16), and Ruan and Zuo (Ref.18), respectively. They showed that the feasible set of their models are not

only composed of the union of the faces of the constrained set S, but also

connected. However, these results were derived under the assumption that

the reactions of the lower levels are unique. Without this assumption, we

will show that, expect for the feasible set of level l of LMPPD(l), the feasible set of any other level is not necessarily composed of faces of the constrained set. Furthermore, it is not necessarily connected.To show that the feasible set of level l of LMPPD(l) is the union of

faces of the constrained set, we prove the following lemma rst. We recall

that the constrained set S of LMPPD(l) is assumed to be nonempty and

unbounded. Let S1 be a nonempty subset of S.Lemma 4.1. Under Assumption 2.1, S1 is the union of some faces ofS if and only if S1 is such that every closed line segment in S with a relative interior point in S1 has both endpoints in S1.Proof. Obviously, S is a polyhedron and contains a nite number of

faces. Let S1,...,Sn denote all the faces of S and let N denote the set

{1,...,n}.Let0

1 ,...,x0

l ), there exists a closed line segment

in Sj which joins (x1,...,xl ) and [parenleftbig]xis an extreme point of S, then it

is a zero-dimensional face of S. Otherwise, it must be the relative interior point of a face Sj for some j N. Obviously, for any (x1,...,xl)

Sj such that (x1,...,xl ) = (xx0

1 ,...,x0

l0

l[parenrightbig] S1.If [parenleftbig]x0

1 ,...,x[parenrightbig]0

1 ,...,x0

land containsx0

1 ,...,x0

las

a relative interior point. Supposing that every closed line segment inS with a relative interior point in S1 has both endpoints in S1,wehave(x1,...,xl ) S1. Since (x1,...,xl ) is arbitrarily selected in Sj ,wehave Sj

S1. With the same procedure, for any other point in S1, we can prove that,

if it is not an extreme point of S, i.e., not a zero-dimensional face of S,

then the face containing it as a relative interior point must be a subset ofS1. Therefore, S1 is composed of the union of some nonempty faces of S.Conversely, letS1 = [uniondisplay]iN0Si ,422 JOTA: VOL. 123, NO. 2, NOVEMBER 2004where N0 is a subset of N. Letx1

1 ,...,x1

l[parenrightBig] S.Suppose that there exists (0, 1) such that[parenrightBig] , [parenleftBig]x21 ,...,x2

lx1

1 ,...,x1

l[parenrightBig] + (1 ) [parenleftBig]x21 ,...,x2

l[parenrightBig] S1.Hence, for some k N0,wehavex1

1 ,...,x1

l[parenrightBig] + (1 ) [parenleftBig]x21 ,...,x2

l[parenrightBig] Sk.Since Sk is a face of S, by Denition 2.6, we know thatx1

1 ,...,x1

l[parenrightBig] , [parenleftBig]x21 ,...,x2

l[parenrightBig] Sk.Obviously,x1

1 ,...,x1

l[parenrightBig] , [parenleftBig]x21 ,...,x2

l[parenrightBig] S1.The proof is completed.Lemma 4.1 suggests an approach for investigating the geometric property of LMPPD(l). Based on the lemma, we can prove the following result.Theorem 4.1. Under the Assumption 2.1, the feasible set Zl of level

l is the union of some nonempty faces of S.Proof. Letx1

1 ,...,x[parenrightBig] S.Suppose that there exists (0, 1) satisfying1

l[parenrightBig] , [parenleftBig]x21 ,...,x2

lx1

1 ,...,x1

l[parenrightBig] + (1 ) [parenleftBig]x21 ,...,x2

l[parenrightBig] Zl .By Lemma 4.1, we need only to prove thatx1

1 ,...,x1

l[parenrightBig] Zl . (10)

Obviously, to prove (10), it is sufcient to show thatx1

1 ,...,x1

l[parenrightBig] , [parenleftBig]x21 ,...,x2

l[parenrightBig] Zl [parenleftBig]x11 ,...,x1

l1[parenrightBig] , [parenleftBig]x21 ,...,x2

l[parenrightBig] Zl [parenleftBig]x21 ,...,x2

l1[parenrightBig] .JOTA: VOL. 123, NO. 2, NOVEMBER 2004 423DenoteSx1=x1,...,xl1=xl1 [defines] {(

x1,...,

xl1,xl)

|A1

x1 ++ Al1

xl1 + Alxl b}.Assume thatx1

1 ,...,x1

l[parenrightBig] /

Zlx1

1 ,...,x1

l

1[parenrightBig] .Since S is bounded andx1

1 ,...,x1

l[parenrightbig] S, Sx1=x11 ,...,xl1=x1

l1 is nonemptyand bounded. By Denition 2.1, Zl [parenleftbig]x1

1 ,...,xis the optimal solution

set of a bounded linear programming problem. Therefore, there would

exist 1

l1[parenrightbig]x1l satisfyingx1

1 ,...,x1

l

1,

x1

l[parenrightBig] Zl [parenleftBig]x11 ,...,x1

l1[parenrightBig] ,such thatl . (11)Since S is convex, we havex1

1 + (

1 )x2

1 ,...,xcT

lx1

l >cT

l x11

l

1 + (

1 )x2

l

1,

x1

l

+(1 )x2

l[parenrightBig] S.Becausex1

1 + (

1 )x2

1 ,...,x1

l

1 + (

1 )x2

l

1,x1

l

+(1 )x2

l[parenrightBig] Zl ,we getx1

1 + (

1 )x2

1 ,...,x1

l

1 + (

1 )x2

l

1,x1

l

+(1 )x2

l[parenrightBig]

Zlx1

1 + (

1 )x2

1 ,...,x1

l

1 + (

1 )x2

l

1[parenrightBig] .Thus,cT

lx1

l+(1 )x2

l[parenrightBig] cT

l

x1

l+(1 )x2

l[parenrightBig] ,which impliescT

lx1

lcT

l x1

l .This contradicts (11); hence, the assumption thatx1

1 ,...,x1

l[parenrightBig] /

Zlx1

1 ,...,x1

l

1[parenrightBig]424 JOTA: VOL. 123, NO. 2, NOVEMBER 2004does not hold. Therefore,x1

1 ,...,x1

l[parenrightBig] Zl [parenleftBig]x11 ,...,x[parenrightBig] .With the same method, we can prove thatx2

1 ,...,x1

l12

l[parenrightBig] Zl [parenleftBig]x2

1 ,...,x2

l

1[parenrightBig] .The proof is completed.Although it is shown that the feasible set of level l is the union of

some faces of the constrained set S, this does not always hold for the feasible sets of level 1 to level l 1. To show this, we consider the following

linear three-level program.Example 4.1.LMPPD(3)1[parenrightBig] max

xf1(x,y,z) = x +4z, where y solves

maxyf2(y, z) =2z, where z solves

maxzf3(z) = z,

s.t. x 1,y 1,z 1,

x + y + z 2.5,0,y 0,z 0.By Figure 1, it is obvious that Z3, the feasible set of level 3 of

LMPPD(3)1, is the union of the two connected faces ABDEF and BCD

of the constrained set. It is not hard to see that (3), the feasible set of

LMPPD(3)1, which is also the feasible set Z2 of level 2, is the union of

the rectangle GDEF and the line segment CD. Since the rectangle GDEFFig. 1. See Example 4.1.x JOTA: VOL. 123, NO. 2, NOVEMBER 2004 425is not a face of the constrained set, (3) is not the union of faces of the

constrained set. The optimal solution set is the line segment GD; the optimal objective values aref 1 =4.5,f 2 =2,f 3 =1,respectively.Another type of geometric property is connectedness. In Example 4.1,

the feasible sets of all levels are connected. However, we will show that

this is not always true. To discuss the connectedness of the feasible sets,

we quote a lemma rst.Lemma 4.2. See Ref. 33. Let T be connected and let F(t) be connected for each t T . If the point-to-set mapping F is upper semicontinuous on T , then the set F(T ) ={F(t)|t T } is connected.For the connectedness of the feasible set Zl of level l of LMPPD(l),

we have the following theorem.Theorem 4.2. Under Assumption 2.1, the feasible set Zl of level l of

LMPPD(l) is connected.Proof. For xed wl Vl, denoteG(wl ) = [braceleftBig](x1,...,xl ) S|wT

l (A1x1 ++ Alxl b) =0[bracerightBig] .By Lemma 3.1, we haveZl = G(Vl).It is easy to verify that Vl and G(wl ) are convex; thus the two sets are

connected. From Theorem 10 of Ref. 32, we obtain immediately that the

point-to-set mapping G is upper semicontinuous on Vl . By Lemma 4.2,

G(Vl ) is connected; namely, Zl is connected. The proof is completed.However, we can demonstrate that the feasible sets of level 1 to levell 1 of LMPPD(l) are not necessarily connected. The following example

can be used to illustrate this.426 JOTA: VOL. 123, NO. 2, NOVEMBER 2004Example 4.2.LMPPD(3)2[parenrightBig] max

xf1(x,y,z) = z,where y solves

maxyf2(y, z) =z,where z solves

maxzf3(z) = z,

s.t. x 2, y + z 0,y + z 2,

x, y, z 0.By Figure 2, the feasible set Z3 of level 3 of LMPPD (3)2 is the union of

the two connected faces of AEDO and EBCD of the constrained set. The

feasible set (3) of LMPPD(3)2, which is also the feasible set of level 2,

includes the line segments OA and BC. Obviously, they are not connected.

The optimal solution set includes also the line segments OA and BC; the

optimal objective values aref 1 =0,f 2 =0,f 3 =0,respectively.Theorems 4.1 and 4.2 and Examples 4.1 and 4.2 give us a detailed

interpretation of the geometric structure of the solution sets of LMPPD(l).

As shown by Theorems 4.1 and 4.2, the feasible set of level l of

LMPPD(l) is composed of the union of some nonempty and connected

faces of the constrained set S. However, what should be emphasized is that

this does not always hold for the cases of level 1 to level l 1.Fig. 2. See Example 4.2.JOTA: VOL. 123, NO. 2, NOVEMBER 2004 4275. ConclusionsIn this paper, a new model is proposed for a multilevel programming

problem MPPD(l). Optimality conditions and geometric properties of its

linear case LMPPD(l) are discussed respectively. Under the assumption

that the constrained set S is bounded and nonempty, we prove that the

feasible set of level l of LMPPD(l) is not only composed of the union of

some nonempty faces of the constrained set S, but also connected. This

property is similar to the existing results for linear multilevel programming

problems. However, it does not always hold for the feasible sets of level

1tolevel l 1 of LMPPD(l). Two examples are given to illustrate the

conclusion. Some issues may deserve further investigations. For example, is

there a vertex optimal solution for LMPPD(l)? If it exists, we may design

an extreme point algorithm, such as the kth-best method (see Ref. 6) to

solve LMPPD(l).References1. Candler, W., and Norton,R.D., Multilevel Programming, World Bank

Development Research Center, Discussion Paper 20, Washington, DC, 1977.2. Candler, W., and Norton,R.D., Multilevel Programming and Development

Policy, World Bank Staff, Working Paper 258, Washington, DC, 1977.3. Candler, W., and Townsley, R., A Linear Two-Level Programming Problem,

Computers and Operations Research, Vol. 9, pp. 5976, 1982.4. Bard,J.F., An Algorithm for Solving the General Bilevel Programming Problem, Mathematics of Operations Research, Vol. 8, pp. 260272, 1983.5. Bard,J.F., Optimality Conditions for the Bilevel Programming Problem,Naval

Research Logistics Quarterly, Vol. 31, pp. 1326, 1984.6. Bialas, W. F., and Karwan, M. H., Two-Level Linear Programming, Management Science, Vol. 30, pp. 10041020, 1984.7. Bard,J.F., Convex Two-Level Optimization, Mathematical Programming,

Vol. 40, pp. 1527, 1988.8. Falk, J. E., and Liu,J., On Bilevel Programming, Part 1: General Nonlinear

Cases, Mathematical Programming, Vol. 70, pp. 4772, 1995.9. Ye,J.J., Necessary Conditions for Bilevel Dynamic Optimization Problems,

SIAM Journal on Control and Optimization, Vol. 33, pp. 12081223, 1995.10. Yezza, A., First-Order Necessary Optimality Conditions for General Bilevel

Programming Problems, Journal of Optimization Theory and Applications,

Vol. 89. pp. 189219, 1996.11. Wang, S. Y., Wang, Q., and Coladas, U. L., A Stability Theorem in Nonlinear

Bilevel Programming,Questiio, Vol. 20, pp. 215222, 1996.12. Bard,J.F., An Investigation of the Linear Three-Level Programming Problem,

IEEE Transactions on Systems, Man, and Cybernetics, Vol. 14, pp. 711717,

1984.428 JOTA: VOL. 123, NO. 2, NOVEMBER 200413. Wen, U. P., and Bialas,W.F., The Hybrid Algorithm for Solving the

Three-Level Linear Programming Problem, Computers and Operations

Research, Vol. 13, pp. 367377, 1986.14. White,D.J., Penalty Function Approach to Linear Trilevel Programming,

Journal of Optimization Theory and Applications, Vol. 93, pp. 183197, 1997.15. Bard,J.F., Geometric Algorithmic Development for a Hierarchical Planning Problem, European Journal of Operational Research, Vol. 19, pp. 372383, 1985.16. Benson,H.P., On the Structure and Properties of a Linear Multilevel Programming Problem, Journal of Optimization Theory and Applications, Vol. 60,

pp. 353373, 1989.17. White,D.J., Multilevel Programming, Rational Reaction Sets, and Efcient Solutions, Journal of Optimization Theory and Applications, Vol. 87,

pp. 727746, 1995.18. Ruan, G. Z., and Zuo,X.B., The Optimality Conditions and Fundamental

Properties of Linear Multilevel Programming Problems, Journal of Systems Science and Mathematical Sciences, Vol. 18, pp. 159166, 1998 (in Chinese).19. Petriczek,G., On the Use of Multilevel Optimization in Water Quality Problems, Systems Analysis, Modeling, and Simulation, Vol. 8, pp. 457467, 1991.20. Migdalas, A., Bilevel Programming in Trafc Planning: Models, Methods, and

Challenge, Journal of Global Optimization, Vol. 7, pp. 381405, 1995.21. Bard, J. F., Plummer, J., and Sourie,J.C., Determining Tax Credits for

Converting Nonfood Crops to Biofuels: An Application of Bilevel Programming,

Nonconvex Optimization and Its Applications, Vol. 20, pp. 2350, 1998.22. Amouzegar, M. A., and Moshirvaziri, K., Determining Optimal Pollution

Control Policies: An Application of Bilevel Programming, European Journal of

Operational Research, Vol. 119, pp. 100120, 1999.23. Vicente, L. N., and Calamai, P. H., Bilevel and Multilevel Programming:

A Bibliography Review, Journal of Global Optimization, Vol. 5, pp. 291306,

1994.24. Wang, X. J., and Feng,S.Y., Optimization Theory of Bilevel Systems, Science

Press, Beijing, 1995 (in Chinese).25. Bard, J. F., and Moore,J.T., A Branch-and-Bound Algorithm for the Bilevel

Programming Problem, SIAM Journal on Scientic and Statistical Computing,

Vol. 11, pp. 281292, 1990.26. Hansen, P., Jaumard, B., and Savard,G., New Branch-and-Bound Algorithm

for Linear Bilevel Programming, SIAM Journal on Scientic and Statistical

Computing, Vol. 13, pp. 11941217, 1992.27. Wang, Q., and Wang,S.Y., Bilevel Programming with Multiple Potential Reactions,

Journal of Systems Science and Systems Engineering, Vol. 13, pp. 269278, 1994.28. Loridan, P., and Morgan,J., Weak via Strong Stackelberg Problem: New

Results, Journal of Global Optimization, Vol. 8, pp. 263287, 1996.29. Wang, Q., Yang, F. M., Wang, S. Y., and Liu, Y. H., Bilevel Programs

with Multiple Followers, Systems Science and Mathematical Sciences, Vol. 13,

pp. 265276, 2000.JOTA: VOL. 123, NO. 2, NOVEMBER 2004 42930. Dempe,S., A Bundle Algorithm Applied to Bilevel Programming Problems with

Nonunique Lower-Level Solutions, Computational Optimization and Applications, Vol. 15, pp. 145166, 2000.31. Rockafellar,R.T., Convex Analysis, Princeton University Press, Princeton,

New Jersey, 1970.32. Hogan,W.W., Point-to-Set Maps in Mathematical Programming, SIAM

Review, Vol. 15, pp. 591603, 1973.33. Naccache, P. H., Connectedness of the Set of Nondominated Outcomes in

Multicriteria Optimization, Journal of Optimization Theory and Applications,

Vol. 25, pp. 459467, 1978.