[工学]系统优化调度

[工学]系统优化调度

ModelingandOptimizationofComplexNetworkedSystems:ApplicationstoOperationsSchedulingandSupplyNetworkManagementPeterB.Luh,VisitingProfessorCenterforIntelligentandNetworkedSystemsDepartmentofAutomationRoom503,MainBuildingTsinghuaUniversityPhone:6279-2438Email:Peter.Luh@uconn.edu9/11/20011Fall2001,CopyRightP.B.Luh\nAreyouintherightclassroom?Whatarecomplexnetworkedsystems?ComputerandcommunicationnetworksPowersystemsSupplychainsWhyareweinterestedincomplexnetworkedsystems?Asaperson,ateam,adepartment,oracompanyMediocrityorexcellence?Survivingorthriving?Needtoaccuratelydescribethesystemunderconsiderationandprudentdecision-makingtomaximizeanobjective(s)MajorareasofdevelopmentandadvancementWhydoweneedtostudytheirmodelingandoptimization?9/11/20012Fall2001,CopyRightP.B.Luh\nThemajorsegmentsinthecourseMathematicaloptimizationconceptsandalgorithms,focusingonmethodsthatcansolvepracticallarge-scaleproblems(7lectures)Operationsschedulingformanufacturingandservicesectors,makinguseofoptimizationmethodslearnedinthefirstsegment(4lectures)Strategy,planning,andoperationsofmodernsupplynetworks,exploringdistributedandcollaborativedecision-makingandoptimizationwithinanetworkedenvironment(4lectures)Participantswhoareinterestedinresearchcantakepartinextradiscussionsessionsonminiresearchprojects9/11/20013Fall2001,CopyRightP.B.Luh\nWhatdoyouexpecttolearnfromthiscourse?SolidunderstandingoftheabovesubjectsClassroomparticipationexperienceMini(ormajor)researchopportunitiesImprovedEnglishWhatistheworkload?Slightlyaboveaverage,andintensiveinSeptember(8lectures)andOctober(7lectures)(andinNovemberandinDecember)Prerequisites:AfirstyeargraduatecourseonsystemtheoryHowcanwemakeitafuncourseforallofus?Preparation:BeforeandaftereachclassParticipation:Inclass9/11/20014Fall2001,CopyRightP.B.Luh\nClassesInSeptember:Monday8:00–9:35,Thursday8:00–9:35,andFriday13:30–15:05InOctober:Monday8:00–9:35andFriday13:30–15:05OfficeHours:Monday16:00–17:00,Thursday16:00–17:00TimeforvoluntarydiscussionsessionstobearrangedMajorreferencesDimitriP.Bertsekas,NonlinearProgramming,SecondEdition,AthenaScientific,Belmont,MA,1999MichaelPinedoandXiuliChao,OperationsSchedulingwithApplicationsinManufacturingandServices,McGraw-Hill,1999SunilChopraandPeterMeindl,SupplyChainManagement:Strategy,PlanningandOperations,PrenticeHall,20009/11/20015Fall2001,CopyRightP.B.Luh\nTentativeOutline1.IntroductionandUnconstrainedOptimization(2.33lectures)2.OptimizationoveraConvexSet(2lectures)3.DualityandDualMethods(2.66lectures)4.OperationsSchedulingwithApplicationsinManufacturingandServices(1.33lectures)5.JobShopScheduling(1.33lectures)6.SchedulingModelsinServiceIndustries(1.33lectures)7.SupplyChainManagement:Strategy,Planning,andOperations(2lectures)8.DistributedandCollaborativeDecision-MakinginSupplyNetworks(2lectures)9/11/20016Fall2001,CopyRightP.B.Luh\nGrading:Homework45%MidTerm25%TermProject25%ClassroomParticipation5%Total100%GeneralRules:Termprojectscanbedoneindividuallyorinteamsoftwoonrelevantoptimizationtopicsorapplications.Topicsshouldbebasedonatleasttworecentpapers.Numericalimplementationandtestingarestronglyencouraged.TermprojectproposalsaredueonFridayOctober12.Thedateofpresentationsandthedateofsubmittingthefinalreportswillbedeterminedlater.9/11/20017Fall2001,CopyRightP.B.Luh\nHomeworkproblemsshouldbeclear,concise,andcomplete.Notallthehomeworkproblemswillbegraded.Gradingwillbebasedonsomerandomlyselectedproblems.Lateassignmentswillbediscounted10%aday,upto5days.Thispolicywillbestrictlyenforced.Homeworksolutionswillbeprovidedonthewebsitesaweekaftertheduedate.Commentsanddiscussionsareencouragedinclass,afterclass,duringofficehoursorbyappointment.NOCHEATING!9/11/20018Fall2001,CopyRightP.B.Luh\nReadingAssignment:BertsekasSections1.1,1.2,andAppendicesAandBToday:IntroductionandUnconstrainedOptimizationMotivationandCourseOverviewProblemClassificationOptimalityConditionsforUnconstrainedOptimizationGradientMethodsFrameworkTomorrow:BertsekasSections2.3~2.69/11/20019Fall2001,CopyRightP.B.Luh\nMathematicalOptimizationConceptsandAlgorithms1.2ProblemClassificationGeneralFormulationMinimizef(x),subjecttoxXRnf(x):Costfunctionx:DecisionvariableX:ConstraintsetExample1Asmallshopspecializesinmaking2typesofautoparts9/11/200110Fall2001,CopyRightP.B.Luh\nHowtodecidethebestquantities?Whatisthemodel?Maxx1,x230x1+40x2,orMinx1,x2(30x1+40x2),subjecttox1+5x2160,(C1)x1+1.5x260,(C2)2x1+x280,and(C3),x10,x20(nowtreatedascontinuousvariable)Whatkindofproblemsisthis?9/11/200111Fall2001,CopyRightP.B.Luh\nLinearcostfunctionwithlinearconstraintsALinearProgramming(LP)problemGenericLPformulationMinimizef(x)c'xsubjecttoxX{xRn,Ax=b,x0}withcRn,bRm,ARmxngiven9/11/200112Fall2001,CopyRightP.B.Luh\nExample2SameasExample1exceptthatMaxx1,x2(50–x1)x1+(64–x2)x2subjecttothesamesetofconstraintsNonlinearcostfunctionand/ornonlinearconstraintsNonlinearprogramming(NLP)~withdiminishingreturn9/11/200113Fall2001,CopyRightP.B.Luh\nOthertypesofproblems:IntegerProgramming(IP)Withintegervariables,e.g.,ifx1andx2areintegers,ormanufacturingschedulingproblemstobediscussedlaterMixedIntegerProgramming(MIP)–Withbothintegerandcontinuousvariables,e.g.,powersystemunitcommitmentandeconomicdispatchMinimizethetotalgenerationcostSubjecttosystemdemandandreserveconstraintsByselectingunitup/downandgenerationlevelsAlthoughmanylectureswillbeonnonlinearprogramming,manyresultswillbeapplicabletointegerprogrammingandmixedintegerprogramming9/11/200114Fall2001,CopyRightP.B.Luh\n1.3OptimalityConditionsforUnconstrainedOptimizationProblemFormulationMinimizef(x),withxXRn,f(x):ContinuouslydifferentiableformostofthischapterShallbrieflygooverthefollowing:LocalandglobalminimumNecessaryconditionsforoptimalityThecaseofaconvexcostfunctionSufficientconditionsforoptimalityExistenceofoptimalsolutions9/11/200115Fall2001,CopyRightP.B.Luh\nWhichoftheaboveisalocalminimumpoint?Globalminimum?Howtomathematicallydefinetheseterms?Localminimum:A,B,andC.Global:Cf(x*)f(x)xwith||x–x*||<x*isalocalminimumf(x*)f(x)xXx*isaglobalminimumMinimumisstrictif“”isreplacedby“<”LocalandGlobalMinimum9/11/200116Fall2001,CopyRightP.B.Luh\nWhatarethenecessaryconditionsforapointtobealocalminimum?Globalminimum?NecessaryConditionsLocalOptimalityProp.1.1.1:Firstorder:f(x*)=0astationarypointSecondorder:2f(x*)0,i.e.,positivesemi-definite,iff(x)istwicecontinuouslydifferentiableWhataref(x)and2f(x)?9/11/200117Fall2001,CopyRightP.B.Luh\n~GradientHessian~Proof:Defineg()=f(x*+d)foradirectiondandscalar.ThenThisshouldbetrueforanydf(x*)=0.9/11/200118Fall2001,CopyRightP.B.Luh\nAlso,tohavef(x*+d)=f(x*)+f(x*)'d+0.52d'2f(x*)d+o(2)=f(x*)+0.52d'2f(x*)d+o(2)f(x*)weneed2f(x*)0Example:Minimizef(x1,x2)x12+2x22+2x1-x1x2x*=(-8/7,-2/7).Also,9/11/200119Fall2001,CopyRightP.B.Luh\nTheaboveareforlocalminimum.Whatcanbesaidaboutglobaloptimalconditions?Difficulttoinvestigateglobaloptimalconditions,exceptfortheconvexcasetobediscussednextorbyusingstochasticoptimizationsuchassimulatedannealingorgeneticalgorithms9/11/200120Fall2001,CopyRightP.B.Luh\nTheCaseofaConvexCostFunctionWhatisaconvexset?Howaboutaconvexfunction?Howareconvexsetsandconvexfunctionsrelated?ConvexSetsDef.B.1:SetXinRnisconvexiffx1+(1-)x2X,x1,x2X,[0,1]ConvexFunctionsA:ConvexB:NotconvexA:NotconvexB:Convex9/11/200121Fall2001,CopyRightP.B.Luh\nDef.B.2:XaconvexsetinRn.f(x):XRisconvexifff(x1+(1-)x2)f(x1)+(1-)f(x2)x1,x2X,[0,1]这里的CONVEX指的是下凸的“《”LinearcombinationisanoverestimateConvexisstrictif“”isreplacedby“<”Relationshipbetweenconvexfunctionsandconvexsets:ReadyourselfTheorem.f(x)isconvexiffthelinearapproximationatanarbitrarypointx+basedonthegradientisanunder-estimateoff(x),i.e.,f(x)f(x+)+f(x+)’(x-x+),xImplications:f(x*)=0x*isaglobalminimum9/11/200122Fall2001,CopyRightP.B.Luh\nTheorem.Afunctionf(x)isconvexifftheHessianispositivesemi-definiteforallx,i.e.,2f(x)0xProp.1.1.2:Foraconvexfunctionf(x)overaconvexsetXAlocalminimumisaglobalminimum;Iff(x)isstrictlyconvex,thenthereexistsatmostoneglobalminimum;andIfXisopen,thenf(x*)=0isanecessaryandsufficientconditionforx*tobeaglobalminimum9/11/200123Fall2001,CopyRightP.B.Luh\nSufficientConditionsforOptimalityPreviouslynecessaryconditionsforoptimality:f(x*)=0and2f(x*)0.Aretheysufficientconditionsalso?Prop.1.1.3:Letf(x)betwicecontinuouslydifferentiableinanopensetS.Supposex*Ssatisfiesf(x*)=0and2f(x*)>0,thenx*isastrictunconstrainedlocalminimumProof:f(x*+d)-f(x*)=f(x*)'d+0.5d'2f(x*)d+o(||d||2)>0.Localminimathatdonotsatisfytheabovesufficientconditionsarecalledsingular,otherwisenon-singular.Singularlocalminimaaredifficulttodealwith9/11/200124Fall2001,CopyRightP.B.Luh\nExistenceofOptimalSolutionsDoesaminimumalwaysexist?Examples:f1(x)=1/x,f2(x)=exProp.A.8:Iff(x)iscontinuousandXiscompact(closedandbounded),thenx*alwaysexists.Iff(x)iscontinuousandXisclosed,andfiscoercive(i.e.,f(x)when||x||),thenx*alwaysexists.Whybothernecessary,sufficient,andexistenceconditions?HelpunderstandwhatisreallygoingonCanbeusedtoterminateanalgorithmwhentheseconditionsaresatisfiedCanbeusedtodeveloporimprovealgorithmsMovexinadirectionsothattheseconditionsare“more”satisfied9/11/200125Fall2001,CopyRightP.B.Luh\n1.4GradientMethodsFrameworkIterativeDescentAlgorithmsMinimizef(x),withxXRnf(x):ContinuouslydifferentiableAnalogy:AblindpersonwithastickgoesdownahillKnowsthecurrentelevationandtheslopeCanmeasureafewmorepoints,oneatatimeandatacostWantstodecidewhichdirectiontogo,andbyhowfartoreachthetop9/11/200126Fall2001,CopyRightP.B.Luh\nMathematicallyStartwithaninitialpointx0,evaluatef(x0),f(x0)(andpossibly2f(x0))Basedontheinformation,selectasearchdirection“d”emanatingfromx0Findthenextpointx1alongthedirectiond,andevaluatef(x1),f(x1)(andpossibly2f(x1))Repeattheabove,andsuccessfullygeneratex2,x3,..,suchthatf(x)isdecreasedateachiterationIterativedescentKeyQuestions?x2x3x1Whichdirectiontogo?Howfar?Isthealgorithmguaranteedtoreachx*?Howfasttoreachx*?9/11/200127Fall2001,CopyRightP.B.Luh\nGradientTypeMethodsKeyIdeasGradientf(x):ThedirectionofsteepestascentAveryintuitivedirection:d=-f(x)xk+1=xk-kf(xk),withk0Shalltalkabouttheselectionofklater~LineSearchIsthisaniterativedescentalgorithm?Howtoshowthis?f(xk+1)=f(xk-kf(xk))=f(xk)-f(xk)'[kf(xk)]+o(||kf(xk)||)=f(xk)-k||f(xk)||2+o(k)||f(xk)||0Therequirementsoff(x)'d<0,or-f(xk)'Dkf(xk)<0issatisfiedsinceDk>0Thisiscalledthe“gradientmethod”inthetextGenerally,thegradientmethodisreferredtothecasewhered=-f(xk)ManymethodsarespecialcasesoftheaboveSteepestDescent:DkINewton'sMethod:Dk(2f(xk))-1~Moreinthefuture9/11/200131Fall2001,CopyRightP.B.Luh