(復(fù)雜系統(tǒng)的性能評(píng)價(jià)與優(yōu)化課件資料)Ordinal-Optimization--Soft-Optim

12/9/20221OrdinalOptimization

—SoftOptimizationforHardProblems—Qing-ShanJia（賈慶山）Email:jiaqs@CenterforIntelligentandNetworkedSystems(CFINS)Dept.ofAutomation,TsinghuaUniversity,Beijing100084,China12/9/20221OrdinalOptimization2/40AcknowledgmentJointworkwithProf.Yu-ChiHo（何毓琦）Prof.Qian-ChuanZhao（趙千川）Prof.Xiao-HongGuan（管曉宏）Dr.ChenSong（宋宸）SupportedbyNationalScienceFoundation,ChinaNewCenturyExcellentTalentsinUniversity,China973fundamentalresearchgrants,ChinaArmyResearchOfficeAirForceOfficeofScientificResearch2/40AcknowledgmentJointworkw3/40OutlineBackground:simulation-basedoptimizationOrdinaloptimizationComparisonofselectionrulesConstrainedordinaloptimizationVectorordinaloptimizationApplicationExamplePerformanceoptimizationinaremanufacturingsystemTheWitsenhausenproblemConclusion3/40OutlineBackground:simulat4/40Human-madecomplexsystemsTransportationsystemManufacturingsystemCommunicationsystemElectricpowergridSupplychain4/40Human-madecomplexsystems5/40Time-consumingsimulationRealsystemPerformanceSimulationtimeRemanufacturingsystemAccuratelyevaluatetheaveragecostofamaintenancestrategyby1000independentsimulations30minutesCongestioncontrolandbuffermanagementinacomputernetworkAsimulationofthe1000-seconddynamicsofa12000-node-single-bottleneckcomputernetwork1.5hoursSecurityevaluationandoptimizationforalargescaleelectricpowergridAsimulationofthe30-seconddynamicsofalargescalepowergridwith5000busesand300generatorsafterafailureevent2hoursSchedulingofatransportationnetworkAsimulationofthe24-hourdynamicsofanetworkwith20intersections2hoursTurbinebladedesignproblemA3Dextrusionsimulationwithfiniteelementmethodology7days5/40Time-consumingsimulationR6/40MajordifficultiesSimulation-basedperformanceevaluationTime-consumingsimulationNoisyobservationDiscreteparametersLargedesignspace:curseofdimensionalityNogradientinformation6/40MajordifficultiesSimulati7/40OrdinalOptimization(OO)OOisanimportanttooltodealwithsimulation-basedoptimization.FirstdevelopedbyProf.Y.-C.Ho,R.S.Sreenivas,andP.Vakiliin1992[Ho,SreenivasandVakili1992].Inthepastdecade,morethan200publicationsandmanysuccessfulapplications.AnonlineincompleteOOpublicationslistisavailableat:/en/resource/index.php

ThefirstbookonOOispublished:Ho,Y.-C.,Zhao,Q.-C.,andJia,Q.-S.,OrdinalOptimization:SoftOptimizationforHardProblems,NewYork,NY:Springer,2007.7/40OrdinalOptimization(OO)O8/40Basicideas(I)Ordinalcomparisonv.s.Whichoneisbigger?Howmuchbigger,sayinunitofcmormm?Itiseasiertofindoutwhichdesignisbetterthantoanswerhowmuchbetter.8/40Basicideas(I)Ordinalcom9/40Basicideas(II)GoalsofteningWhichboardiseasiertohit?Why?Itiseasiertofindagoodenoughdesignthantofindtheoptimaldesign.v.s.9/40Basicideas(II)Goalsofte10/40Basicideas-summaryOrdinalcomparisonComparedesignsusingacrudemodel,computationallyfastbutroughperformanceestimate.GoalsofteningFindingtheglobaloptimalispracticallyinfeasible.Amorereasonablegoal:findagoodenough(top-n%)design.Notonlyintuitivelyreasonable,butalsocanbeshowninamathematicallyrigorouswayObservedorderconvergestotrueorderexponentiallyfastw.r.t.#ofobservations[Dai1996,Xie1997].Theprobabilitythatsomeoftheobservedtop-n%designsaretrulygoodenoughconvergesto1exponentiallyfastw.r.t.n[LeeLauHo1999].Insteadoffindingthebestforsure,OOfindsagoodenoughdesignwithhighprobability.Whatdowesaveinthisway?Andhowmuch?10/40Basicideas-summaryOrdi11/40ApplicationProcedureGSkQQ:

designspaceG:

goodenoughsetS:

selectedset

:

trueoptimum

:

estimatedoptimumPr{|GS|k}:alignmentprobability11/40ApplicationProcedureGSkQ12/40Demonstration200designsTrueperformanceJ(qi)=i,i=1,2…200.Observedperformancei.i.d.uniformlydistributednoiseU[0,W].Question:Howmanyobservedtop-12(6%)designsaretrulytop-12ontheaverage?…demonstration…12/40Demonstration200designs13/40Demonstration-summaryW=100,Pr{|GS|3}0.95.|GS|≈5onaverage.W=10000(BlindPick),|GS|≈1onaverage.|GS|isrobustw.r.t.noise.Thecrudemodelhelpstofindsomegoodenoughdesigns,andsavesthecomputingbudgetbyoneorderofmagnitude(from200to12).13/40Demonstration-summaryW=14/40ProblemtypeForagiveng,k,noiselevel,andproblemtype,thevalueofscanbecalculatedusingatablein[LauHo1997],s.t.Pr{|GS|k}0.95.14/40ProblemtypeForagiveng15/40OOSummaryStep1:randomsampleNdesignsfromQStep2:userdefinesgandk.Step3:evaluatethedesignsusingacrudemodelStep4:estimatethenoiselevelandproblemtypeStep5:calculatethevalueofss.t.Pr{|GS|k}0.95.Step6:selecttheobservedtop-sdesignsStep7:OOtheoryensuresthereareatleastktrulygoodenoughdesignsinSwithhighprobability.Usuallysavesthecomputingbudgetbyatleastoneorderofmagnitude.Usefultofastscreenoutsomegoodenoughdesigns,andeasilycombinedwithotheroptimizationmethods.15/40OOSummaryStep1:random16/40SelectionrulesBlindPickHorseRaceMotivatedbysportsgamesPair-wiseeliminationasinU.S.TennisOpenRoundRobinasinNBAseasongamesRound1:q1vs.q2,q3vs.q4Round2:q1vs.q3,q2vs.q4Round3:q1vs.q4,q2vs.q316/40SelectionrulesBlindPick17/40Selectionrules-continuedOptimalComputingBudgetAllocation(OCBA):nottowasteonbaddesigns.distinguishthetrulybestfromtherestdesigns.Breadthvs.Depth:automaticbalancebetweenexplorationandexploitation17/40Selectionrules-continu18/40ComparisonQuestion:WhichselectionruleneedstoselectthesmallestSs.t.Pr{|GS|k}0.95?TheoreticalstudyandabundantexperimentsWefindeasywaystopredictagoodselectionrulewhentheproblemisgiven.Alsosomepropertiesofgoodselectionrules.Somequickanddirtyrules:HorseRaceisingeneralagoodselectionrule.18/40ComparisonQuestion:Which19/40ConstrainedOrdinalOptimizationSimulation-basedconstraints:E[Ji(q)]0ManyinfeasibledesignsGSQEstimatedfeasibledesignsLessinfeasibledesignsGSDirectlyapplyOOConstrainedOO19/40ConstrainedOrdinalOptim20/40COO-continuedBasicidea:Useafeasibilitymodeltoscreenoutthefeasibledesignsfirst,withasmallprobabilitytomakemistakes.ThenapplyOOinthesetofestimatedfeasibledesigns.RequiresasmallerselectedsetthandirectlyapplyingOOwithoutafeasibilitymodel.Thesizeoftheselectedsetalsodependsontheaccuracyofthefeasibilitymodel.Formulawerealsoobtained[Guan,Song,Ho,Zhao2006].20/40COO-continuedBasicidea21/40VectorOrdinalOptimizationMulti-objectivesimulation-basedoptimizationWhatistheorderamongdesigns?Theconceptoflayers1stLayer2ndLayer3rdLayer1stLayer:ParetoFrontierDesignswithinthesamelayerareincomparable.Designswithasmallerlayerindexarebetter.Goodenoughset:designsinthefirstnlayers.Selectedset:designsintheobservedfirstnlayers.21/40VectorOrdinalOptimizati22/40ProblemtypeHardNeutralEasyTrueperformance#ofdesignsineachlayer#ofdesignsinthefirstxlayers22/40ProblemtypeHardNeutralEa23/40VOO-continuedTherelationshipbetweeng,s,k,noiselevel,andproblemtypehasalsobeentabularized[Zhao,Ho,Jia2005].23/40VOO-continuedTherelati24/40AircraftEngineLife-criticalparts,expensive,failure,teardowntorepair.24/40AircraftEngineLife-criti25/40RemanufacturingSystemParameterstooptimize:Eachseason,#ofmachinesintheworkshopand#ofpartstoorderintheinventory.Objectivefunction:maintenancecost(machinecost,inventoryholdingcost,costoforderingnewparts)Constraint:Pr{TurnAroundTime(TAT)i.e.,departuretime–arrivaltime>T0}P025/40RemanufacturingSystemPar26/40TrueperformancesFeasibledesignsInfeasibledesignsInefficientifdirectlyapplyOO.26/40TrueperformancesFeasible27/40ApplicationofCOORandomlysampleN=1000designs.Timeconsumingperformanceevaluation:30minuteseach,500hoursintotal.Crudemodel:singlereplication,1.8secondeach,30minutesintotal.Afeasibilitymodelbasedonroughsettheory,withaccuracy98.5%[Song,Guan,Zhao,Ho2005].Screenoutfeasibledesignswithsmallmistakes.ThenapplyOOtofindsomefeasibleandtrulygoodenough(top-5%)designs.Pr{|GS|1}0.500.700.95|S|,Sizeofselectedset101639ByreducingfromN=1000to|S|,COOsavesthecomputingbudgetbyatleast25folds.27/40ApplicationofCOORandoml28/40ApplicationofVOOMotivation:ItisnotclearwhatistheappropriatevalueofP0intheconstraintsPr{TAT>T0}P0.

ObjectivefunctionsJ1:Pr{TAT>T0}J2:maintenancecostRandomlysampleN=1000designs.G:designsinthefirsttwolayers.S:observedtop-slayers,sgivenbyVOOtheory,s.t.Pr{|GS|k}0.95.28/40ApplicationofVOOMotivat29/40TruePerformancesThereare14designsinthetruefirsttwolayers.29/40TruePerformancesTherear30/40ApplicationofVOO-continuedFormostk,VOOreducesthecomputingbudgetfromN=1000tolessthan100.k1234567#ofselecteddesigns661414142424k891011121314#ofselecteddesigns36484862859614130/40ApplicationofVOO-cont31/40TheWitsenhausenProblemTwo-stagedecisionmakingproblem[Witsenhausen1968]Stage1(DM1):initialstatex,controlu1=g1(x),newstatex1=x+u1Stage2(DM2):observey=x1+v,controlu2=g2(y),stopsatx2=x1+u2.Costfunction:J(g1,g2)=E[k2(u1)2+(x2)2]Find(g1,g2)tominimizeJ(g1,g2)Benchmark:x~N(0,s2),v~N(0,1),s=5,k=0.231/40TheWitsenhausenProblemT32/40DifficultyThegloballyoptimalcontrollawforsuchasimpleLQGproblemisstillunknownafternear40years.Majordifficulty:informationstructureindecentralizedcontrolTradeoff:costlycontrolwithperfectinformationvs.freecontrolwithnoisyobservationDiscreteversionoftheproblemisNP-complete[PapadimitriouandTsitsiklis1986].Best-so-farnumericalsolution[Leeetal.2001].(slightlyimprovedbyN.LiandJ.S.Shammain2007,reducedby0.17%)32/40DifficultyThegloballyop33/40Milestone1–[Witsenhausen1968]Letf(x)=x+g1(x),g(y)=g2(y),J(f,g)=E[k2(f(x)-x)2+(f(x)-g(f(x)+v))2].Stage1cost:E[k2(f(x)-x)2]Stage2cost:E[(f(x)-g(f(x)+v))2]Optimallinearcontrol:f(x)=lx,g(y)=my,l=m=0.5(1+(1-4k2)0.5),Jlinear*=1-k2=0.96BetternonlinearcontrolfW(x)=ssgn(x),gW(y)=stanh(sy),JW=0.4042Givenf*(x),gf*=E[f(x)f(y-f(x))]/E[f(y-f(x))].Findtheoptimalf*(x)33/40Milestone1–[Witsenhaus34/40Milestone2–[Banal&Basar1987]Theconceptofsignaling:DM1cancels/enhancespartsofthestatex,sothatx1concentratesonagivennegative/positivevalue.DM2ascertainsthesignofx1withhighprobability,cancelsalmostallx1,makesx20.BanalandBasaroptimizedtheone-stepfunction:fBB(x)=sgn(x)s(2/p)0.5,JBB=0.3634.34/40Milestone2–[Banal&Basa35/40Milestone3–[Deng&Ho1999]Simulation-basedcrudemodelofgf*:gf’Randomsampledifferenttypesoff(x).UseOOtocomparewhichtypehasahighprobabilitytocontainmoregoodenoughf(x)’s.Identifyseveralpropertiesofagoodf(x).JDH=0.1901,47%betterthanJBB.35/40Milestone3–[Deng&Ho1936/40Milestone4–[Leeetal.2001]FurtherexplorethestepfunctionideaAcrudemodelofgf*basedonnumericalintegration,fasterandmoreaccuratethanMonteCarlosamplingin[Deng&Ho1999]JLLH=0.1673thebest-so-farsolution.(furtherreducedto0.1670byLiandShammain2007,0.17%)36/40Milestone4–[Leeetal.37/40PursuitofgoodandsimplesolutionsEachmilestonefisbetterthanbefore,butalsobecomemoreandmorecomplicated.fLLHisa27-stepfunction.Canwefindgoodandsimplef?Kolmogorovcomplexitymeasuressimplicity,butingeneralincomputable[Li&Vitányi1997].[Jiaetal.2006]ConstructacrudemodeltoestimatetheKCUseOOtofindgoodandsimplesolutions37/40Pursuitofgoodandsimpl38/40Withminorperformancedegradation(<5%,w.r.t.fLLH),fsgsavesthememoryspacebyover30folds.38/40Withminorperformancede39/40ConclusionSimulation-basedoptimizationTime-consumingsimulation-basedperformanceevaluationOrdinalOptimizationOrdinalcomparisonGoalsofteningUseacrudemodeltoscreenoutgoodenoughdesigns,savesthecomputingbudgetHorseraceisingeneralagoodselectionrule.COO:simulation-basedconstrains.VOO:multi-objectivesimulation-basedoptimization.39/40ConclusionSimulation-base40/40BookHo,Y.-C.,Zhao,Q.-C.,andJia,Q.-S.,OrdinalOptimization:SoftOptimizationforHardProblems,NewYork,NY:Springer,2007.40/40BookHo,Y.-C.,Zhao,Q.-C12/9/202241Thankyou!Anyquestions?12/9/202241Thankyou!Anyquest42/40ReferenceList[BanalandBasar1987]Banal,R.andBasar,T.,“Stochasticteamswithnonclassicalinformationrevisited:Whenisanaffinelawoptimal,”IEEETransactionsonAutomaticControl,1987,32:554-559.[Dai1996]Dai,L.,“Convergencepropertiesofordinalcomparisoninthesimulationofdiscreteeventdynamicsystems”,JournalofOptimizationTheoryandApplications,1996,91(2):363-388.[DengandHo1999]Deng,M.andHo,Y.C.,“Sampling-selectionmethodforstochasticoptimizationproblems,”Automatica,1999,35(2):331-338.[Guan,Song,Ho,Zhao2006]Guan,X.,Song,C.,Ho,Y.-C.,andZhao,Q.,“Constrainedordinaloptimization–afeasibilitymodelbasedapproach”,DiscreteEventDynamicSystems:TheoryandApplications,2006,16(2):279-299.[Ho,SreenivasandVakili1992]Ho,Y.C.,Sreenivas,R.S.,andVakili,P.,“OrdinaloptimizationofDEDS”,DiscreteEventDynamicSystems:TheoryandApplications,1992,2(2):61-88.[Jiaetal.2006]Jia,Q.S.,Zhao,Q.C.,andHo,Y.C.,“AmethodbasedonKolmogorovcomplexitytoimprovetheefficiencyofstrategyoptimizationwithlimitedmemoryspace,”In:Proceedingsofthe2006AmericanControlConference,Minneapolis,MN,June14-16,pp.3105-3110,2006.42/40ReferenceList[Banaland43/40ReferenceListcontd.[LauHo1997]Lau,T.W.E.andHo,Y.C.,“Universalalignmentprobabilitiesandsubsetselectionforordinaloptimization”,JournalofOptimizationTheoryandApplications,1997,93(3):455-489.[LeeLauHo1999]Lee,L.H.,Lau,T.W.E.,andHo,Y.C.,“Explanationofgoalsofteninginordinaloptimization”,IEEETransactionsonAutomaticControl,1999,44(1):94-99.[Leeetal.2001]Lee,J.T.,Lau,E.L.,andHo,Y.C.,“TheWitsenhausencounterexample:Ahierarchicalsearchapproachfornonconvexoptimizationproblems,”IEEETransactionsonAutomaticControl,2001,46(3):382-397.[LiandVitányi1997]Li,M.andVitányi,P.,AnIntroductiontoKolmogorovcomplexityanditsapplications,2ndedition,Springer,BerlinHeidelbergNewYork,1997.[PapadimitriouandTsitsiklis1986]Papadimitriou,C.H.andTsitsiklis,J.N.,“Intractableproblemsincontroltheory,”SIAMJournalonControlandOptimization,1986,24(4):639-654.[Song,Guan,Zhao,Ho2005]Song,C.,Guan,X.,Zhao,Q.,andHo,Y.-C.,“Machinelearningapproachfordeterminingfeasibleplansofaremanufacturingsystem”,IEEETransactionsonAutomationScienceandEngineering,[seealsoIEEETransactionsonRoboticsandAutomation],2005,2(3):262-275.43/40ReferenceListcontd.[Lau44/40ReferenceListcontd.[Witsenhausen1968]Witsenhausen,H.S.,“Acounterexampleinstochasticoptimumcontrol,”SIAMJournalonControl,1968,6(1):131-147.[Xie1997]Xie,X.,“Dynamicsandconvergencerateofordinalcomparisonofstochasticdiscrete-eventsystems”,IEEETransactionsonAutomaticControl,1997,42(4):586-590.[Zhao,Ho,Jia2005]Zhao,Q.C.,Ho,Y.C.,andJia,Q.-S.,“Vectorordinaloptimization”,JournalofOptimizationTheoryandApplications,2005,125(2):259-274.44/40ReferenceListcontd.[Wit12/9/202245OrdinalOptimization

—SoftOptimizationforHardProblems—Qing-ShanJia（賈慶山）Email:jiaqs@CenterforIntelligentandNetworkedSystems(CFINS)Dept.ofAutomation,TsinghuaUniversity,Beijing100084,China12/9/20221OrdinalOptimization46/40AcknowledgmentJointworkwithProf.Yu-ChiHo（何毓琦）Prof.Qian-ChuanZhao（趙千川）Prof.Xiao-HongGuan（管曉宏）Dr.ChenSong（宋宸）SupportedbyNationalScienceFoundation,ChinaNewCenturyExcellentTalentsinUniversity,China973fundamentalresearchgrants,ChinaArmyResearchOfficeAirForceOfficeofScientificResearch2/40AcknowledgmentJointworkw47/40OutlineBackground:simulation-basedoptimizationOrdinaloptimizationComparisonofselectionrulesConstrainedordinaloptimizationVectorordinaloptimizationApplicationExamplePerformanceoptimizationinaremanufacturingsystemTheWitsenhausenproblemConclusion3/40OutlineBackground:simulat48/40Human-madecomplexsystemsTransportationsystemManufacturingsystemCommunicationsystemElectricpowergridSupplychain4/40Human-madecomplexsystems49/40Time-consumingsimulationRealsystemPerformanceSimulationtimeRemanufacturingsystemAccuratelyevaluatetheaveragecostofamaintenancestrategyby1000independentsimulations30minutesCongestioncontrolandbuffermanagementinacomputernetworkAsimulationofthe1000-seconddynamicsofa12000-node-single-bottleneckcomputernetwork1.5hoursSecurityevaluationandoptimizationforalargescaleelectricpowergridAsimulationofthe30-seconddynamicsofalargescalepowergridwith5000busesand300generatorsafterafailureevent2hoursSchedulingofatransportationnetworkAsimulationofthe24-hourdynamicsofanetworkwith20intersections2hoursTurbinebladedesignproblemA3Dextrusionsimulationwithfiniteelementmethodology7days5/40Time-consumingsimulationR50/40MajordifficultiesSimulation-basedperformanceevaluationTime-consumingsimulationNoisyobservationDiscreteparametersLargedesignspace:curseofdimensionalityNogradientinformation6/40MajordifficultiesSimulati51/40OrdinalOptimization(OO)OOisanimportanttooltodealwithsimulation-basedoptimization.FirstdevelopedbyProf.Y.-C.Ho,R.S.Sreenivas,andP.Vakiliin1992[Ho,SreenivasandVakili1992].Inthepastdecade,morethan200publicationsandmanysuccessfulapplications.AnonlineincompleteOOpublicationslistisavailableat:/en/resource/index.php

ThefirstbookonOOispublished:Ho,Y.-C.,Zhao,Q.-C.,andJia,Q.-S.,OrdinalOptimization:SoftOptimizationforHardProblems,NewYork,NY:Springer,2007.7/40OrdinalOptimization(OO)O52/40Basicideas(I)Ordinalcomparisonv.s.Whichoneisbigger?Howmuchbigger,sayinunitofcmormm?Itiseasiertofindoutwhichdesignisbetterthantoanswerhowmuchbetter.8/40Basicideas(I)Ordinalcom53/40Basicideas(II)GoalsofteningWhichboardiseasiertohit?Why?Itiseasiertofindagoodenoughdesignthantofindtheoptimaldesign.v.s.9/40Basicideas(II)Goalsofte54/40Basicideas-summaryOrdinalcomparisonComparedesignsusingacrudemodel,computationallyfastbutroughperformanceestimate.GoalsofteningFindingtheglobaloptimalispracticallyinfeasible.Amorereasonablegoal:findagoodenough(top-n%)design.Notonlyintuitivelyreasonable,butalsocanbeshowninamathematicallyrigorouswayObservedorderconvergestotrueorderexponentiallyfastw.r.t.#ofobservations[Dai1996,Xie1997].Theprobabilitythatsomeoftheobservedtop-n%designsaretrulygoodenoughconvergesto1exponentiallyfastw.r.t.n[LeeLauHo1999].Insteadoffindingthebestforsure,OOfindsagoodenoughdesignwithhighprobability.Whatdowesaveinthisway?Andhowmuch?10/40Basicideas-summaryOrdi55/40ApplicationProcedureGSkQQ:

designspaceG:

goodenoughsetS:

selectedset

:

trueoptimum

:

estimatedoptimumPr{|GS|k}:alignmentprobability11/40ApplicationProcedureGSkQ56/40Demonstration200designsTrueperformanceJ(qi)=i,i=1,2…200.Observedperformancei.i.d.uniformlydistributednoiseU[0,W].Question:Howmanyobservedtop-12(6%)designsaretrulytop-12ontheaverage?…demonstration…12/40Demonstration200designs57/40Demonstration-summaryW=100,Pr{|GS|3}0.95.|GS|≈5onaverage.W=10000(BlindPick),|GS|≈1onaverage.|GS|isrobustw.r.t.noise.Thecrudemodelhelpstofindsomegoodenoughdesigns,andsavesthecomputingbudgetbyoneorderofmagnitude(from200to12).13/40Demonstration-summaryW=58/40ProblemtypeForagiveng,k,noiselevel,andproblemtype,thevalueofscanbecalculatedusingatablein[LauHo1997],s.t.Pr{|GS|k}0.95.14/40ProblemtypeForagiveng59/40OOSummaryStep1:randomsampleNdesignsfromQStep2:userdefinesgandk.Step3:evaluatethedesignsusingacrudemodelStep4:estimatethenoiselevelandproblemtypeStep5:calculatethevalueofss.t.Pr{|GS|k}0.95.Step6:selecttheobservedtop-sdesignsStep7:OOtheoryensuresthereareatleastktrulygoodenoughdesignsinSwithhighprobability.Usuallysavesthecomputingbudgetbyatleastoneorderofmagnitude.Usefultofastscreenoutsomegoodenoughdesigns,andeasilycombinedwithotheroptimizationmethods.15/40OOSummaryStep1:random60/40SelectionrulesBlindPickHorseRaceMotivatedbysportsgamesPair-wiseeliminationasinU.S.TennisOpenRoundRobinasinNBAseasongamesRound1:q1vs.q2,q3vs.q4Round2:q1vs.q3,q2vs.q4Round3:q1vs.q4,q2vs.q316/40SelectionrulesBlindPick61/40Selectionrules-continuedOptimalComputingBudgetAllocation(OCBA):nottowasteonbaddesigns.distinguishthetrulybestfromtherestdesigns.Breadthvs.Depth:automaticbalancebetweenexplorationandexploitation17/40Selectionrules-continu62/40ComparisonQuestion:WhichselectionruleneedstoselectthesmallestSs.t.Pr{|GS|k}0.95?TheoreticalstudyandabundantexperimentsWefindeasywaystopredictagoodselectionrulewhentheproblemisgiven.Alsosomepropertiesofgoodselectionrules.Somequickanddirtyrules:HorseRaceisingeneralagoodselectionrule.18/40ComparisonQuestion:Which63/40ConstrainedOrdinalOptimizationSimulation-basedconstraints:E[Ji(q)]0ManyinfeasibledesignsGSQEstimatedfeasibledesignsLessinfeasibledesignsGSDirectlyapplyOOConstrainedOO19/40ConstrainedOrdinalOptim64/40COO-continuedBasicidea:Useafeasibilitymodeltoscreenoutthefeasibledesignsfirst,withasmallprobabilitytomakemistakes.ThenapplyOOinthesetofestimatedfeasibledesigns.RequiresasmallerselectedsetthandirectlyapplyingOOwithoutafeasibilitymodel.Thesizeoftheselectedsetalsodependsontheaccuracyofthefeasibilitymodel.Formulawerealsoobtained[Guan,Song,Ho,Zhao2006].20/40COO-continuedBasicidea65/40VectorOrdinalOptimizationMulti-objectivesimulation-basedoptimizationWhatistheorderamongdesigns?Theconceptoflayers1stLayer2ndLayer3rdLayer1stLayer:ParetoFrontierDesignswithinthesamelayerareincomparable.Designswithasmallerlayerindexarebetter.Goodenoughset:designsinthefirstnlayers.Selectedset:designsintheobservedfirstnlayers.21/40VectorOrdinalOptimizati66/40ProblemtypeHardNeutralEasyTrueperformance#ofdesignsineachlayer#ofdesignsinthefirstxlayers22/40ProblemtypeHardNeutralEa67/40VOO-continuedTherelationshipbetweeng,s,k,noiselevel,andproblemtypehasalsobeentabularized[Zhao,Ho,Jia2005].23/40VOO-continuedTherelati68/40AircraftEngineLife-criticalparts,expensive,failure,teardowntorepair.24/40AircraftEngineLife-criti69/40RemanufacturingSystemParameterstooptimize:Eachseason,#ofmachinesintheworkshopand#ofpartstoorderintheinventory.Objectivefunction:maintenancecost(machinecost,inventoryholdingcost,costoforderingnewparts)Constraint:Pr{TurnAroundTime(TAT)i.e.,departuretime–arrivaltime>T0}P025/40RemanufacturingSystemPar70/40TrueperformancesFeasibledesignsInfeasibledesignsInefficientifdirectlyapplyOO.26/40TrueperformancesFeasible71/40ApplicationofCOORandomlysampleN=1000designs.Timeconsumingperformanceevaluation:30minuteseach,500hoursintotal.Crudemodel:singlereplication,1.8secondeach,30minutesintotal.Afeasibilitymodelbasedonroughsettheory,withaccuracy98.5%[Song,Guan,Zhao,Ho2005].Screenoutfeasibledesignswithsmallmistakes.ThenapplyOOtofindsomefeasibleandtrulygoodenough(top-5%)designs.Pr{|GS|1}0.500.700.95|S|,Sizeofselectedset101639ByreducingfromN=1000to|S|,COOsavesthecomputingbudgetbyatleast25folds.27/40ApplicationofCOORandoml72/40ApplicationofVOOMotivation:ItisnotclearwhatistheappropriatevalueofP0intheconstraintsPr{TAT>T0}P0.

ObjectivefunctionsJ1:Pr{TAT>T0}J2:maintenancecostRandomlysampleN=1000designs.G:designsinthefirsttwolayers.S:observedtop-slayers,sgivenbyVOOtheory,s.t.Pr{|GS|k}0.95.28/40ApplicationofVOOMotivat73/40TruePerformancesThereare14designsinthetruefirsttwolayers.29/40TruePerformancesTherear74/40ApplicationofVOO-continuedFormostk,VOOreducesthecomputingbudgetfromN=1000tolessthan100.k1234567#ofselecteddesigns661414142424k891011121314#ofselecteddesigns36484862859614130/40ApplicationofVOO-cont75/40TheWitsenhausenProblemTwo-stagedecisionmakingproblem[Witsenhausen1968]Stage1(DM1):initialstatex,controlu1=g1(x),newstatex1=x+u1Stage2(DM2):observey=x1+v,controlu2=g2(y),stopsatx2=x1+u2.Costfunction:J(g1,g2)=E[k2(u1)2+(x2)2]Find(g1,g2)tominimizeJ(g1,g2)Benchmark:x~N(0,s2),v~N(0,1),s=5,k=0.231/40TheWitsenhausenProblemT76/