| Bilevel programming problem is an important optimization problem in operational research. It can be applied in economy, engineering, management and military affairs which has an hierachical structure system. Von Stackelberg published a monograph[44] about game theory in unbalanced economic markets in 1934. In this monograph he built Von Stackelberg competition model named by his name first (also called double oligarch model). Von Stackelberg competition model describes two big competitor in finance. When one person makes a decision, he should considers both optimize his objective function and the other person's reflection. So he should changes his decision. Von Stackelberg competition model is a special model of bilevel programming problem. Because in World Warâ…¡Nazification Germany implemented anti-competitive economic policy, it can not attract people's attention. After World Warâ…¡,Von Stackelberg competition model caught the attention of researchers in game theory. In the mid-1970s, bilevel programming problem was introduced into optimization and made a rapid development. In recent years, bilevel programming problem attracts researchers' attention in many region (applied mathe-matic,operational research, management science, decision-making science, system science and economics), because of its comprehensive application. Bilevel programming problem is an optimization problem whose constraint is another optimization problem. It can be showed in the following form:where x∈X (?) Rn,y∈Y (?) Rm,F,f:X×Y→R1,G:X×Y→Rp,g:X×Y→Rq.In this paper we consider the algorithms of some bilevel programming problem, and mainly obtain the following results:1,We present boundary search method for solving linear bilevel programming problem.Firstly, we solve the following problem (2)by the following boundary search method: Step 1 Let iâ†1.Using the simplex method, we can obtain the optimal solution x1=(x11,x12,…,x1n)T from problem (2.1.3).Go to step 2.Step 2 Let current iterative point be x2=(x21,x22,…,x2n)T.Using the simplex method, we can obtain the optimal solution x'2 of problem (1.2.3). If x2=x'2,x2 is the solution of problem (2). Otherwise, go to step 3.Step 3 Let current iterative point be x3=(x31,x32,…,x3n)T.Assume x3 satisfy p constraint conditions, and let they are first p. Let d = (d1,d2,…,dn)T be search direction. Choose min{p,n-1} constraint conditions from p constraint conditions arbitrarily, then d is the solution of the following equations:the step length of search direction is: For the point x3,search direction d and the step length t,x3+td is a adjacent extreme point of x3.We can obtain other extreme points of x3 like this. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region.If not exist, choose the point which minimize the upper-level objective function as new iterative point, go to step 4. Otherwise, choose the point which maximize the upper-level objective function as new iterative point, go to step 5.Step 4 Let current iterative point be x4={x41,x42,x4n)T.Choose n-1 constraint conditions from p constraint conditions arbitrarily that x4 satisfy:and let them take "=". From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x4 is still iterative point, go to step 3.Step 5 Let current iterative point be x5=(x51,x52,?x5n)T.Choose n-1 constraint conditions from p constraint conditions arbitrarily that x5 satisfy: and let them take "=".From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x5 is the optimal solution of problem (2).Then choose the optimal solution of problem (2) as initial iterative point to solve the linear bilevel programming problem (3):Boundary search method for solving linear bilevel programming problemis presented in the following:Step 1 Let F =+∞is upper-level objective funciton value, T=(?) is the set of iterative points that we have known, W=(?) is the set of feasible extreme points. By the method in [27] and [28], we can obtiain the solution x1 of problem (2). Check x\ whether satisfy upper-level constraint conditions. If satisfy, then the solution x1 of problem (2) is also the problem (3)'s solution. If not satisfy, choose x1 as iterative point, update T = T∪{x1},W=(?),F=c2x1,go to step 2.Step 2 Let x2 ={x21,x22,…,x2n)T is current iterative point. The search direction isAssume x2 satisfy p constraint conditions, and let they are first p. Choose min{p,n-1} constraint conditions from p constraint conditions arbitrarily, and consider the following problem:We can obtain the search direction d. Because the choosen are different,we can obtain q search directions and denote asTakeinto all the constraint conditions to solve the step length max{t} respectively.So we can obtain q adjacent extreme points of x2.If there exists a point both satisfy the lower-level optimality condition and in the feasible region, go to step 3. Otherwise, T = T∪{x2},F=c2x2,W=(W∪W')\T, (W' is the set of x2's adjacent extreme points which satisfy lower-level optimality condition). Choose the point which maximize the upper-level objective function from W as new iterative point, go to step 2.Step 3 Let x3 = (x31,x32,?x3n)T is current iterative point. Denote the points which both satisfy the lower-level optimality condition and in the upper-level constraint conditions in step 2 as xj'(j' =1,2,?p'),the corresponding search direction are dj'.UpdateTake x'j'=xj'-dj't (t≥0) into all the constraint conditions to solve the step length max{t} respectively. So we can obtain x'j'(j'=1,2,…,p'). Then solve the following problem:Let (?) is the solution of problem (4).If c2(?)>F,update F=c2(?).Otherwise,not change F. Choose the point which maximize the upper-level objective function from W and denote as x'.If F > c2x',then x* which is corresponding to F is the solution of problem (3).Otherwise, choose x' as iterative point, go to step 2.2,We present Kth-best approach for solving linear bilevel programming problem which is in the following:Step 1 Let x0=(x01,x02,…,x0n)T be a feasible point arbitrarily.Step 2 Fix (x0s+1,…,x0n) in the lower-level problem, then the problem is transformed to: Using the simplex method, we obtain the solution of the problemwhereand make it is new iterative point. For x1 and optimal search direction c2=(c21,c22,?c2n),we should guarantee that the new iterative point is in the feasible region, namely:If t≠0, we can obtain a new iterative point (x1 + (c2)Tt),update x0 = (x1 + (c2)Tt),repeat step 2. Otherwise, go to step 3.Step 3 Let current iterative point beAssume x2 makes i constraint conditions take "=",let they are first i constraint conditions. Then: (i) If i≤n-1,d* is the solution of the following problem:We can obtain the suboptimal search direction d*,go to step 4.(ii) If i≥n,we solve the following problem:where constraint conditions are n-1 constraint conditions from i constraint conditions arbitrarily. So we can obtain p solution, denote as dj (j = 1,2,…,p).Go to step 5.Step 4 For the current iterative point and suboptimal search directionwe should guarantee that the new iterative point is in the feasible region, namely:We can obtain a new iterative point x3=(x2+(d*)Tt).Take (x3s+1,?x3n) into lower-level problem, it is transformed to: Using the simplex method, we can obtain a new iterative point, denote aswhereGo to step 3.Step 5 Let the current iterative point be x5 = (x51,x52,?x5n)T.dj(j = 1,2,…,p) is the suboptimal search direction. Takeinto the lower-level constraint conditions to solve the step length max{t} respectively. If there exist t > 0 such that the new iterative point satisfy lower-level optimality condition, then choose the point which maximize the upper-level objective function as new iterative point, go to step 3. Otherwise,x5 is still iterative point, go to step 6.Step 6 Let the current iterative point be x6 = (x61,x62,…,x6n)T.Choose n-1 constraint conditions from m constraint conditions arbitrarily that x6 satisfy: and let them take "=".From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x6 is the optimal solution of problem (3).3,We present interior point method for solving linear bilevel programming problem which is in the following:Step 1 Let x1 be initial iterative point which is in feasible region. Let the upper and lower boundary of iterative direction is du=c2,dι=c1.Choose d1=du=c2 as initial iterative direction. Take x1 + d1t into constraint conditions and obtain step length t and x'1 =x1+ d1t.If x'1 satisfy lower-level optimality condition, then use boundary search method or extend Kth-best approach. If x'1 do not satisfy lower-level optimality condition, go to step 2.Step 2 Let the current iterative point be x2,update iterative direction d2=(?)(du+dι).Take x2+d2t into constraint conditions and obtain step length t and x'2=x2+d2t.If x'2 do not satisfy lower-level optimality condition, iterative point do not change, update du=d2,dι=dι.Repeat step 2. If x'2 satisfy lower-level optimality condition, the new iterative point is x3 = x2 + (?)d2t,update du= du,dι= d2.If step length t >ε(εis prior fixed), repeat step 2. Otherwise, go to step 3. Step 3 Let the current iterative point be x3.Add a new plane c2x= c2x3.Choose n-1 constraint conditions arbitrarily from the constraint conditions that x3 satisfy. Prom these n-1 equations and the new plane, we can obtain some new boundary points. Check whether there exists a point satisfy the lower-level optimality condition. If there do not exist,x3 is the optimal solution of the problem (3). If there exist, choose one and denote as x'3,update du= du,dι=x'3-x3,and x3 is still iterative point. Go to step 2.4,We also consider the following two problem, such as, multi-followers bilevel programming problem, fractional bilevel programming problems. These two problem are all derived from normal bilevel programming problem in practical problem and have important application.We give the method for solving these two problem which are based on the method above.5,We give a new definition of the optimal solution for no solution bilevel programming problem.Definition 6.0.1 We call the optimal solution of problem (5) is the feasible optimal solution of problem (1). where umax and umin are objective function value of problem (6) and (7).6, We transform max-min problems to a special type bilevel programming problem and give the following theorem:Theorem 6.0.1 max-min problem (8)is equivalent to the bilevel programming problem (9) And we also solve max-min problems via solving this bilevel programming problem.
|
PDF Full Text Request