搜索
SomeResultsonConstraintActivityandParameterSensitivityinBilevelModelsofOptimalDesignbyBalaChidambaramandJ.R.JagannathaRao1SystemsDesignLaboratoryDepartmentofMechanicalEngineeringTheUniversityofHoustonHouston,TX77204-4792.Email:rao@uh.eduAbstractBilevelproblemsaregeneralmodelsthatariseingame-theoreticanddecompositionrelatedapplica-tionsinengineeringdesign.Theprincipaldifficultyinsolvingthebilevelmodelsisthatthelowerlevelmodelisparametricallydeformedandtheresultingdeformedsolutionisimplicitlyusedbytheupperlevelmodel.Theeffectsofthisparametricdeformationarenotalwaysobvious.Inthispaper,thisparametricmodeldeformationisstudiedinthecontextof(i)two-levelmonotonicityanalysisforconstraintactivitydeduction,and(ii)thecomputationofsensitivitiestodataperturbations.Theresultsandtheexamplesshowthatwhileageneralbilevelmodelcanexhibitcomplexsingularities,suchamodelismucheasiertosolveifthemonotonicityinformationisavailableexplicitly.1IntroductionInthispaper,ourgoalistostudythefollowinggeneralbilevelproblem:minimizefl(x;p)x;p2n+ksubjecttogli(x;p) 0i2Il=f1;2;:::;llghlj(x;p)=0j2Jl=f1;2;:::;mlgx2X (p)(1.1)whereX (p)istheparametricsolutionsetofminimizeff(x;p)x2nsubjecttogf(x;p) 0i2If=f1;2;:::;lfghf(x;p)=0j2Jf=f1;2;:::;mfg(1.2)1authortowhomallcorrespondenceshouldbedirected1Equation(1.1)istheupperlevel(orleader’s)problemandEq.(1.2)isthelowerlevel(orfollower’s)problem.Weobservethatiftheupperlevelproblemisnotconstrainedexplicitlybyglandhl,thenforfl=ff,thebilevelmodelrepresentsaconventionalparametricallydecomposedmodel.Similarly,forfl= ff,thebilevelmodelrepresentsamin-maxformulation(Shimizu[16]).Suchtwo-levelmodelsarefoundinarichvarietyofdesignapplicationsasseeninAzarmandLi[2],Haftka[6],LiandAzarm[8],PanandDiaz[13]andSobieski[19].Thestronginterestintheseproblemsismotivatedbythefactthatengineeringsystemshaveanaturalhierarchicandnon-hierarchiccomponent-wisephysicalstructurewhichcanbeexploitedbyadecompositionstrategyinbothmodelingandsolutiontechniques.Furthermore,inagame-theoreticsetting(see,e.g.,Vincent[21]),themodelsinEqs.(1.1)and(1.2)representtheleaderandfollower,respectively,ofaStackelberggame(SimaanandCruz[18]),wheretheleaderknowsthefollower’smodelandexpectsrational(i.e.,optimal)behaviorfromthefollower.Aftertheleaderannounceshisdecisionstrategyp ,thefollowerthencomputeshisoptimalstrategyx (p ).Severalquestionsrelatedtoexistenceandoptimalityconditionsinbilevelmodelshavebeenaddressedbefore.Forexample,SimaanandCruz[18],andLuchettietal.[12]havedevelopedexistenceresultsforStackelberggames.LoridanandMorgan[9,11,10]havepresentedapproximationresultsfortwo-levelmod-els.Shimizu[16]havedevelopedoptimalityconditionsforgeneraltwo-levelproblemsbasedondirectionalderivatives.Fromacomputationalpointofview,severaldifferentstrategieshavebeenproposedtosolvebilevelproblems.TherecentpaperbyFalkandLiu[3]hasanexcellentsurveyonclassesofalgorithmsforbilevelproblemsaswellasnewalgorithmswheregradientinformationfromthelower-levelproblemisusedforascentmethodsintheupperlevel.Inthispaper,ourgoalistohighlighttheroleplayedbyparametricdeformationofthelowerlevelmodelandinparticulartheresultingparametricsolutionsetX (p)ontwoaspectsofthemodelingandsolutioninbilevelproblems:(1)monotonicitybasedconstraintactivitydeduction,and(2)effectsofright-handsidedataperturbationsonsolutionsatthetwolevels.Forthisreason,thispaperiscloselyrelatedtoandfurtherextendstheresultsobtainedinAzarmandLi[8],AzarmandLi[2]andPanandDiaz[13].Theoutlineofthepaperisasfollows.InSection2,weillustrateusingexampleshowthesingularitiesthatcanariseduetoparametricdeformationinthelowerlevelaffecttheupperlevelmodelinthegeneralbilevelcase.InSection3,weextendtheideasofmonotonicity-basedconstraintactivitydeductiontobilevelproblems,againfocussingontheroleplayedbytheparametricmapX (p).Finally,inSection4,weshowhowdataperturbationsatthetwolevelsdirectlyandindirectlyaffectthesolutiontothebilevelproblem.2TheSingularitiesDueToParametricDeformationThelowerlevelmodelofEq.(1.2)inthebilevelproblemisparameticallydeformedbythevectorp.TheresultingsolutionsetX (p)isimplicitlyusedintheupperlevelmodelofEq.(1.1).Thetwoprincipalreasonswhythebilevelproblemisdifficulttosolveare:1.X (p)needstobecomputedorapproximated,whichinpracticemeansthatEq.(1.2)hastobesolvedeverytimeweneedtoevaluatetheproblemfunctionsofEq.(1.1).Fornonconvexandmultimodalproblemsatthelowerlevel,thismayleadtolossofstabilityofx (p)2X (p)thatisreturnedbyagloballyconvergentnumericalsolver.i.e.,itmaybedifficulttoensurethatforparametersp0andp0+ p,thenumericallycomputedlocalminimax (p0)andx (p0+ p)aresuchthatjjx (p0) x (p0+ p)jj!0asjj pjj!0.Thisdifficultyissomewhatalleviatedinproblemswithmonotonicobjectiveandconstraintfunctions,whereglobalsolutionscouldbeidentifiedanalyticallywithsurprisinglylittleeffort(asillustratedinExamples4and5).2.Themappingoflocalmimimax (p)maynotbewellbehavedunlessstrongconditionsaresatisfied,asrequiredbytheBasicSensitivityTheorem(BST)(see,e.g.,[4],[15]).AccordingtoBST,ifthelin-2earindependenceconstraintqualification,strictcomplementarityconditionandtheseco