CHI Xiao-ni，ZHANG Qing(College of Mathematics and Computer Science，Huanggang Normal University，Huangzhou 438000，Hubei，China)

1 Introduction

In reality，there are uncertain data almost everywhere.Uncertainty makes the optimal solution of a deterministic bilevel programming problem(BLP)［1］become feasible but not optimal，or infeasible.When there is uncertainty in the lower level optimization problem of a bilevel programming problem，by a robust optimization method it can be formulated［2］as a second－order cone bilevel programming problem(SOCBLP).

Recently great attention has been paid to second－order cone optimization problems，since they have various important applications in many fields，such as robust linear programming，robust leastsquares［3］，filter design，antenna array weight design，truss design，and so on［4］.Although secondorder cone programming problems， second－order cone complementarity problems and mathematical programming problems with second－order cone complementarity constraints［5，6］have been actively studied over the recent years，little work has been done on SOCBLP.

In this paper，we consider a bilevel programming problem having the linear second－order cone programming as its lower level problem，i.e.，a linear second－order cone bilevel programming(SOCBLP)problem.For x∈X?Rn，y∈Y?Rm，F(xiàn)∶X×Y→R，and f∶ X × Y→ R，the linear SOCBLP problem is given by［7］

where c1，c2∈Rn，d1，d2∈Rm，b1∈Rp，b2∈Rq，A1∈Rp×n，B1∈Rp×m，A2∈Rq×n，and B2∈ Rq×m.Here Km=Km1×Km2×…×Kmrwith m=m1+m2+…+mris the Cartesian product of second－order cones.Kmj(j=1，2，…，r)is the second－order cone(SOC)of dimension mjdefined by

where‖·‖ refers to the Euclidean norm.It is easy to verify that the SOC Kmis self－dual.

Since SOCBLP is generally a problem of nonconvexity and non－differentiability，it is difficult to dealwith it directly［7］. To effectively solve SOCBLP，we propose a Kth－best approach for solving the 2－dimensional linear SOCBLP in this paper.

The organization of this paper is as follows.In Section 2，some concepts，theoretical properties and a Kth－best approach are proposed for the 2－dimensional linear SOCBLP.In Section 3，the numerical example shows the effectiveness of our approach.Section 4 concludes this paper.

2 Kth-best approach

In this section，we review some preliminaries about the Euclidean Jordan algebra［8］associated with SOC，which plays an important role in the design of our method.Then some theoretical properties and a Kth－best approach are given for the 2－dimensional linear SOCBLP.

The Euclidean Jordan algebra for the SOC Kmis the algebra［3，8］defined by

x?s=(xTs;x0s1+s0x1)，?x，s∈ Rm.

The element e=(1;0;…;0)∈Rmis the unit element of this algebra.

Since the SOC Km=Km1×Km2×…×Kmris generally not polyhedral for mj≥3(j=1，2，…，r)，we are mainly concerned in this paper with the 2－dimensional SOC Kmj，i.e.，m1=m2=… =mr=2.Thus the constraint y∈Kmin problem(1)holds if and only if

for j=1，2，…，r.Therefore the 2－dimensional linear SOCBLP(1)is equivalent to the following BLP problem

Definition 2.1

(1)Constraint region of the 2－dimensional linear SOCBLP problem(1):

(2)Feasible set for the follower for each fixed x∈X:

(3)Projection of S onto the leader＇s decision space:

(4)Follower＇s rational reaction set for

where

(5)Inducible region:

IR={(x，y) ∶(x，y) ∈ S，y∈ P(x)}.

For simplicity，we make the following assumptions throughout this paper.

Assumption 2.1

(1)S is nonempty and compact.

(2)For decisions taken by the leader，the follower has some room to respond，i.e.，P(x)≠?.

(3)P(x)is a point－to－point map.

Thus the 2－dimensional linear SOCBLP problem(1)can be written as

min{F(x，y) ∶(x，y) ∈ IR}.

By extending the theoretical properties of the linear BLP［1］，we obtain the following results about the 2－dimensional linear SOCBLP(1).

Theorem 2.1The optimal solution(x*，y*)of the 2－dimensional linear SOCBLP(1)occurs at a vertex of S.

Corollary 2.1If(x，y)is an extreme point of IR，it is an extreme point of S.

By Theorem 2.1 and Corollary 2.1，we extend the Kth－best approach from the linear BLP［1］to the 2－dimensional linear SOCBLP(1).The main idea of the Kth－best approach is to compute the global optimal solution of the 2－dimensional linear SOCBLP by enumerating the extreme points of the constraint region S.

Let(x［1］，y［1］)，(x［2］，y［2］)，…，(x［N］，y［N］)denote the N ordered basic solutions of the linear programming problem

such that

for i=1，2，…，N－1.Then solving(3)is equivalent to finding the index

K*∶=min{i∈{1，2，…，N－ 1} ∶(x［i］，y［i］) ∈IR}，which yields the global optimal value(cT1x［K*］+dT1y［K*］).Our approach is described in detail as follows.

Algorithm 2.1(Kth－best approach)

Step 1Put i=1.Solve(3)by the simplex method to obtain the optimal solution(x［1］，y［1］).Let W={(x［1］，y［1］)}and T= ?.Go to Step 2.

Step 2Solve the lower level problem with x=x［i］using the simplex method to obtain the optimal solutionIf~=y［i］，stop;(x［i］，y［i］)is the global optimal solution of(1)with K*=i.Otherwise，go to Step 3.

Step 3Let W［i］denote the set of adjacent extreme points of(x［i］，y［i］)such that(x，y) ∈W［i］implies

Let T=T∪{(x［i］，y［i］)}and W=(W∪W［i］)T.Go to Step 4.

Step 4Set i=i+1 and choose(x［i］，y［i］)such that

Go to Step 2.

3 Numerical Example

Example 3.1Consider the following linear SOCBLP problem with x∈R1，y∈R2，and X={x|x≥0}，Y={(y1，y2)|y1≥0，y2≥0}.

By the definition of SOC，problem(4)can be rewritten as

According to our Kth－best approach，let i=1.Solve(5)in format(3)by the simplex method to obtain the optimal solution(x［i］，y［i］)=(0，1，0).Let W={(0，1，0)}and T= ?.Go to Step 2.

Loop 1Solving the lower level problem with x=0，we have~=(0，0)≠(1，0)=y［i］，and go to Step 3.We have W［i］={(0，1，0)，(0，1，1)，(0，0，0)，(1，0，0)}，T={(0，1，0)}and W={(0，1，1)，(0，0，0)，(1，0，0)}，and then go to Step 4.Update i=2，choose(x［i］，y［i］)=(0，1，1)，and then go to Step 2.

Loop 2Solving the lower level problem with x=0，we have=(0，0)≠(1，1)=y［i］，and go to Step 3.We have W［i］={(0，1，1)，(0，0，0)，(1，0，0)}，T={(0，1，0)，(0，1，1)}and W={(0，0，0)，(1，0，0)}，and then go to Step 4.Update i=3，choose(x［i］，y［i］)=(0，0，0)，and then go to Step 2.

Loop 3Solving the lower level problem with x=0，we have~=(0，0)=y［i］，and stop here.The extreme point(x［i］，y［i］)=(0，0，0)is the global optimal solution of problem(4).

Example 3.1 shows that the Kth－best approach is effective.

4 Conclusions

Since SOCBLP is generally a problem of nonconvexity and non－differentiability，it is difficult to deal with it directly.In this paper，we give some basic concepts and theoretical properties，and present a Kth－best approach for solving the 2－dimensional linear SOCBLP(1).The numerical example illustrates the effectiveness of our approach.

［1］ Bard J F.Practical Bilevel Programming［M］.Netherlands:Kluwer Academic Publishers，1998.

［2］ Ejiri T.A Smoothing Method for Mathematical Programs with Second－Order Cone Complementarity Constraints［D］.Kyoto:Kyoto University，Master thesis，2007.

［3］ Alizadeh F，Goldfarb D.Second－order cone programming［J］.Math Program.Ser B，2003，95:3－51.

［4］ Lobo M S，Vandenberghe L，Boyd S，and Lebret H.Applications of second－order cone programming［J］.Linear Algebra Appl，1998，284:193－228.

［5］ Zhang Y，Zhang L W，Wu J.Convergence properties of a smoothing approach for mathematical programs with second－order cone complementarity constraints［J］.Set－valued Anal，2011，19:609－ 646.

［6］ Jiang Y.Optimization Problems with Second－Order Cone Equilibrium Constraints［D］.Dalian:Dalian U－niversity of Technology，Ph D thesis，2011.(in Chinese)

［7］ Chi X，Wan Z，Hao Z.The models and theories of linear second－order cone bilevel programming［J］.unpublished，2012.

［8］ Faraut J，Korányi A.Analysis on Symmetric Cones［M］.New York:Oxford University Press，1994.