Optimal Design part 1 2010-11-1.ppt

OptimalDesign Theory MethodsandApplications 最优化设计理论 方法和应用 Dr JianzhongCha查建中博士Dr WeiLiu刘伟博士 2 58 Reference 1 G V Reklaitis A RavindranandK M Ragsdell EngineeringOptimization MethodsandApplications 1983JohnWiley Sons Inc 2 陈立周 1982冶金工业出版社3 周济 1988高教出版社4 D M Himmelblau AppliedNonlinearProgramming 1972 Mcgraw HillBookCo 实用非线性规划 1981科学出版社 5 JorgeNocedal StephenJ Wright NumericalOptimization科学出版社2006 16 孙靖民 第三版 机械工业出版社2006 97 刘惟信 第二版 清华大学出版2002 78 陈立周冶金工业出版社2005 BoardmeetingatLeuven Belgium Nov 7 10 3 58 LectureanddiscussioninZhejiangPolytech Nov 11 12 4 58 InternationalConferenceIITE 2010 Nov 14 16 5 58 IITEGoverningBaordMeeting Nov 17 18 6 58 WinterinSt Petersburg 7 58 TheWinterPalace 8 58 InsideoftheWinterpalace 9 58 10 58 GradingPolicy H W 20 Projects40 Exam40 Whytoreformtheengineeringeducation ManygraduatescannotfindworkIndustrycannotfindtalentstheyneed2010NobleAwardforeconomics trytoexplaintheparadox MatchingConflict UNESCOReportonEngineering Issues ChallengesandOpportunitiesforDevelopment Engineeringisoftentheunsungpartnerofscience Ihope UNESCOfirstreportonengineeringwillcontributetochangingthat DirectorGeneralofUNESCO 11 58 Desiredattributesofanengineersource BoeingManagementCompany AgoodunderstandingofengineeringsciencefundamentalsAgoodunderstandingofdesignandmanufacturingprocessAmulti disciplinary systemsperspectiveAbasicunderstandingofthecontextinwhichengineeringispracticalGoodcommunicationskillsHighethicalstandardsAbilitytothinkbothcriticallyandcreatively independentlyandcooperativelyFlexibility theabilityandself confidencetoadapttorapidormajorchangesCuriosityanddesiretolearnforlifeAprofoundunderstandingofimportanceofteamwork Goalsforlearning UNESCOFourPillars LearntoKnowLearntoDoLearntoLivetogetherLearntoBe 13 58 Thewaytolearn Education elicitation enlighten 启发式学习教育 教养 教导 教训 培育 自上而下灌输ThreestrategiestoreformengineeringeducationUniversity IndustryCooperationLearningbyDoingInternationalizationLearningEnglishbyusingAdvancedglobaleducationmodelsInternationalstandardoftalentsProjectbasedlearning Learningbydoing Independentstudy self study Advicebyteachers 14 58 15 58 CourseProject Acompleteoptimaldesignproject findinganddefiningproblems engineeringdesign original atleast3designvariables week1 2 15 gradingdependsonrelevancyandcomplexityofproblems developingmathmodel week3 15 selectingalgorithmandparameters week4 5 solvingproblem week4 5 20 checkingengineeringrelevancy week5 10 writingafinalreport week6 7 20 Presentingresultsinclass week8 15 CourseProject Teamwork 5students group aprojectmanagerforeachgroupselectedbystudents eachgrouphasitsownproblem no2problemsidenticalCountedas40 ofthetotalscoreforthecourseSelf assessment peerassessment teacher sassessment 16 58 17 58 MathematicModelofOptimalDesign 11 19 07 AnExample WewouldlikethistraytoholdavolumeVoffluidandhaveaheightH Volume w h l assumingsmallwallthickness 18 58 h H Pickavalueforwandsolvefortheltoobtainasatisfactorydesign Minimummaterialisdesiredandthetraythicknessnotbechangedbecauseofmanufacturingandstructurerequirements materialvolume minf S T minfS T n 3q 2so wehaveoneindependentvariable 19 58 addonemoreconstraintintothemodel S T and 1 Ifthen 2 Ifthenw W Incase 1 thelastconstraintisnotactive 20 58 MathematicModelofOptimalDesign Minimizef x1 x2 xn ObjectiveFunctionSubjectto ConstraintFunctionx x1 x2 xn T asetofdesignvariables completeness independency Objectivefunction 目标函数 tobereachedwiththebestpossiblevalueattheoptimumdesignConstraintfunction 约束函数 tobesatisfiedatspecifiedvalueorrangeattheoptimumdesign 21 58 Putthemodeloftheexampleintostandardformasminf f x1 x2 x3 S T Where x1 h x2 l x3 w 22 58 H W due11 30 10 1 ForarectangularbasetrayofcapacityV determinew landhtogiveminimummaterialvolumeVm wherehisfreetobeselected FindminimumVmintermsofVandthicknessT 2 ForacircularbasetrayofvolumeVandwallthicknessT findminimumVmfora h H b hfree CompareVmoftherectangularandcirculartraysinthefixedandfreehcases 23 58 BasicConceptsofOptimization Terminology Optimization最优化Minimization极小化Objectivefunction目标函数Constraintfunction约束函数Designvariable设计变量Feasibleregion可行域 24 58 Mathematicmodel DesignVariable x x1 x2 xn TsimpleboundObjectivefunction goal targetofoptimization Constrainfunctions tobesatisfiedwithspecifications 2 Feasibleregion可行域FeasibleDesign feasiblepoint 可行解 apointinsolutionspacewhichcansatisfyallconstraintfunctionsFeasibleregionisthecompletesetofallfeasiblepoints 25 58 3 Analyticalpropertiesoffunctions 解析性质 1 Gradientoffunctions梯度Ifthegradientequalszero itmayreachoptimum minimumormaximum 2 Contouroffunctions等值线 或等值面 consistsallpointswhichhavethesamefunctionvalue 26 58 3 Hessianmatrix海色矩阵二阶导数矩阵Allentriesaresymmetric 对称 totheDiagonalofmatrix 对角线 4 FirstorderTaylorextension ageneralnonlinearfunctionf x isapproximatedbyanlinearfunction 27 58 SecondorderTaylorextension Quadraticfunction二次型 28 58 MathematicModelofOptimization 1 Designvariables Allindependentparameters whichinfluencethebehaviorofthesystemstobeoptimized2 Objectivefunction Thebestgoalortargetofoptimization3 Constraintfunction tobesatisfiedduringoptimizationprocess sometimesnotnecessary andattheoptimumsolution 29 58 TheGradientoffunctionsFiniteDifferenceDerivative有限差分Stepsizeofis0 001 bydefault orotherappropriatevalue 30 58 HessianMatrixPropertyoftheHessianmatrixHAssumingfisaquadraticfunctionIfH x1 x2 xn ispositivedefinite thenfisataminimumvalue IfHisnegativedefinite fisatmaximumvalue IfHisindefinite fisatasaddlepoint 鞍点IfHissemi definite thetestfails 31 58 Howtojudge MatrixHispositivedefiniteifandonlyifalltheeigenvaluesofHarepositive MatrixHisnegativedefiniteifandonlyifalltheeigenvaluesofHarenegative Positive negative semi definitematrix ifandonlyiftheeigenvaluesareallnon negative non positive andoneormorezero Indefinitematrix mixtureofpositiveandnegativeeigenvaluesNotice Theeigenvaluesofarealsymmetricmatrixareallrealnumbers 32 58 For2 DcasesAtapointwhere shouldbesatisfiedwiththedefinitionofeigenvalueswhere denoteseigenvalues andIdenotesaunitmatrixofnxnwithvalue1ondiagonalentries 0everywhereelse 33 58 ForrealeigenvalueTheleftpartcanre arrangedas Radical theworst casewillbe andeigenvalueisrealnumber Tohaveaminimumpointwhen 34 58 ifand then sarepositive 35 58 ForpositiveF11 F22withF11 F22 F122 duetoF11 F22 0andF11F22 F122 matrixHispositivedefinite FornegativeF11 F22withF11 F22 F122 duetoF11 F22F122 matrixHisnegativedefinite Matrixispositivesemi definitewithpositiveF11 F22andF11 F22 F122 whichresultseigenvalue0MatrixisindefinitewithF11 F22 F122 saddlepoint Whatdoesismeanonarealfunction arebothnegativeandpositive Hisindefinite Conclusions 36 58 atx1 X1 x2 X2 F1 F2 0 A2 DsecondorderTaylorseriesextension F11andF22 0 37 58 addansubstractontherighthandoftheequation 1 H definite正定 F11 F22 F122 F11 0 3 H semidefinite F11 F22 F122 inadirectionwhere thenanychanges x1 x2willincreasef f 0 2 H indefinite F11 F22 F122 inadirectionwherethen f 0 F11 0 then f 0 For x2 0 f 0results thisisasaddlepoint 38 58 Lagrangemultipliersforconstrainedoptimization拉格朗日乘子 minf x S T hi x 0 i 1 q 39 58 minf x1x2S T x1 x2 1 attheconstrainedoptimumpoints Denote 40 58 Ifx areoptimalpoint then Lagrangemultipliersforinequalityconstraints Minf x S T gi 0 i 1 p Introducing slackvariables 松弛变量 sintogi x hi xi si gi x si2 0 n 2pequations hi gi si2 0 41 58 Tosolvethesimultaneousequation consider 0andobtainx sandf s 0andobtainx f pickupthebestresults 42 58 Example Postofficeparcelproblem S T l 42l d 72 S T l s12 42 0l d s22 72 0L fT Th 43 58 Try 1 2 0d 0f 0 amaximum 2 0s1 0l 42d 0f 0 amaximum s1 s2 0 44 58 l 42 alocalminimum 1 0s2 0 45 58 H W 2 due12 10 10 Solvetherectangularparcelpostproblemforthemaximum poolcue length ST Twosetsofconstraints 1 L 42L 2W 2H 72 2 L 42L 2W 2H 72L 0H 0W 0 Useslackvariable Lagrangemultipliesmethod Comparetheresultsfromthetwocasesandexplainwhytheyaredifferent 46 58 VisualizetheGradientVector In2 Dspace withunitvectorofgradient 47 58 ForalineconstantF dx1 dx2 T unitvectorofTargetofF anglebetweenTand f 48 58 90 270 twovectorsarenormal 正交 Example f x1x2 Considercurveforf 1 x1x2 1 curveforf 2 x1x2 2 49 58 a 50 58 Kuhn TuckerConditions KTConditions Thenecessaryconditionsforalocaloptimum minf x S T hj 0j 1 mgi 0i 1 q i 0 igi x 0 gi 0 51 58 Usuallym n andtherearenotenough stobecertainofsatisfyingtheequations G 1doesnotworkwhenn m Tosolvefor useminimizationofresidualvector IfR 0 andeach iarepositive KTConditionsaresatisfied 52 58 Example minf x1 x2 S T x1 0 x12 x22 1 considerA where pointA g2istheonlyactiveconstraint 53 58 1 1 b pointB active x1 0 x2 1 g1 x1 0 active c pointC x1 1x2 0 g1 1g2 0 active 54 58 HW3 due12 17 10 Thefunctionf x x1 1 2 x2 1 2istobeminimizedsubjecttog1 x1 2 0 g2 x2 0 5 0g3 x2 x1 0 a Sketchthecontouroftheobjectivefunctionandconstraints byinspection findtheconstrainedoptimumpoint b UsetheKohn Tuckerconditionstotesttheoptimumpointobtainedbytheinspection andthepointatx1 0 x2 0 Aretheyoptimumpoints 55 58 One DimensionalSearch Onlyonevariableisinvolvedminf x Byanumericalsearchscheme 1 Identifyaregionthatcontainstheoptimumpoint 2 Applyaniterative 选代 schemetolocatetheoptimumpointtoadesiredaccuracy Quadraticinterpolationasanapproach Considerf x toberepresentedbyaquadraticsf H a b c 2 Tofinda b c threevaluesof withthecorrespondingvaluesoffarenecessary 1 2 3 56 58 Fromthe3points optimum cantheestimatedas Basedonthe3values theconstanta b ccanbefoundsubtract aniterativeprocedureisusedtoimprovetheestimation 57 58 Secondderivativeimplication c 0isnecessaryforaminimum whatkindof sandf syieldapositivec Consider0 1 2 3 2 3 If f1 f2 0and f1 f2 f1 f3 thencispositive f1 f2 f1 f3 f2 f3f2 f3 Thedesiredresultofthefiststepintheone Dsearchisthe Rangefinding 58 58 ProcedureofAlgorithm 算法 1 findingtherange 1 Frequentlyx0maybezeroandusuallyconsider 1 0 2 Steptoapointgivenby 2 1 t wheretisaninitialstepsize 3 checkf2andiff2 f1 letandcomputeanew 2andf2 continueuntilf2 f1isfoundandthenconsider 3 2 t Afterthe3pointsfind andcomputerf 4 Iftheminimumpointistotheleftofx0 asignchangestrategyshouldbeincluded Afterthe3pointsfind andcomputerf 5 Iff3 f2 3 2 t theniff3 f2 increasetot 2t continuetillf3 f2 2 findingtheminimum Aftertherange 1 2 3withcorrespondingf 1 f 2 f 3 Howdoweapplyquadraticinterpolationtoconvergetooptimum Afterthe3pointsfind andcomputerf 59 58 Iff f 2 and 2 3 let 1 1 2 3 3 computenew Iff f 2 and 2 3 obtainanew Iff f 2 and 2 3 let 1 1 2 2 3 new Iff f 2 and 1 2 let 1 2 2 3 3 new Continueuntiloptimumissatisfactorilylocatedusuallystopwhen fa fb wherefaisthemostrecentf andfbisthepreviousf let 1 1 2 3 2 60 58 ProgrammingAssignment Due12 21 10 Writeaprogramtoperforma1 Dsearchusingthequadraticinterpolationalgorithm allfunctionalevaluationsduringRANGEfindingandtheiterativesearchshouldbeperformedinasubroutinewhichincludesoutputoffand shouldstartfromanyinitialvalue includebothstepsincreasinganddecreasingasnecessary Testproblemfor1 Dsearch Solvefroma 0 110witht 0 01b 0 110witht 1000Turninlistsforbothsolutionswiththesourcecodeoftheprogram 61 58 Region EliminationMethodsfor1 Dresearch Insteadofinterpolation thisproceduretriestosystematicallydeducetheregionknown tocontaintheoptimumpoint ItassumesaUNIMODALfunctionandtofindtheminimummaximumintervalthatmaycontaintheoptimum Minimaxcriterionofsearchstrategy Theintervalshouldbereducedbythesameamount Theamountshouldbeaslargeaspossible Algorithm 1 IntervalHalving Step1 Let L b a computef m Step2 Set Step3 Computef 1 andcomparef 1 andf m i Iff 1 f m thendroptheinterval m b bysettingb m andnew m 1 gotostep5 ii Iff 1 f m gotostep4 62 58 Step4 Computef 2 andcomparef 2 andf m afterafunctionalevaluation theinitialsearchintervalwillbereducedto Nisthenumberoffunctionalevaluation i Iff 2 f m thendrop a m bysettinga m new m 2 gotostep5 ii Iff 2 f m drop a 1 2 b Seta 1 b 2 gotostep5 Step5 ComputeL b a ifitsmallenoughterminate otherwisegotostep2 Remarks Ateachstageofthealgorithm exactlyhalfthelengthofthesearchintervalisdeleted Thenewmidpointisalwaysequaltooneoftheprevioustrialpoints 1 mand 2 Hence atmosttwofunctionalevaluationsarenecessaryateachsubsequentstep 63 58 2 Goldensectionsearch 0 618 Indiscussionofregion eliminationandminimaxSearchstrategy thefollowingisobserved Ifonlytwotrialsareavailable thenitisbesttolocatethemequal distantfromt