E nginEEring D O Esign ptimizatiOn Joaquim R. R. A. Martins Andrew Ning Engineering Design Optimization joaquimr.r.a.martins UniversityofMichigan andrewning BrighamYoungUniversity Thisistheelectronicversionofthebook,whichisavailable onthefollowingwebpage: https://mdobook.github.io Thepagenumbershavebeenadjustedtomatchthoseofthe printedbook,whichisavailableat: https://www.cambridge.org/us/academic/subjects/ engineering/control-systems-and-optimization/ engineering-design-optimization Pleasecitethisbookas: JoaquimR.R.A.MartinsandAndrewNing. EngineeringDe- signOptimization. CambridgeUniversityPress,2021. ISBN: 9781108833417. Copyright © 2021 JoaquimR.R.A.MartinsandAndrewNing. Allrights reserved. Publication Firstelectronicedition: January2020. Contents Contents v Preface xi Acknowledgements xiii 1 Introduction 1 1.1 DesignOptimizationProcess 2 1.2 OptimizationProblemFormulation 6 1.3 OptimizationProblemClassification 17 1.4 OptimizationAlgorithms 21 1.5 SelectinganOptimizationApproach 26 1.6 Notation 28 1.7 Summary 29 Problems 30 2 AShortHistoryofOptimization 33 2.1 TheFirstProblems: OptimizingLengthandArea 33 2.2 OptimizationRevolution: DerivativesandCalculus 34 2.3 TheBirthofOptimizationAlgorithms 36 2.4 TheLastDecades 39 2.5 TowardaDiverseFuture 43 2.6 Summary 45 3 NumericalModelsandSolvers 47 3.1 ModelDevelopmentforAnalysisversusOptimization 47 3.2 ModelingProcessandTypesofErrors 48 3.3 NumericalModelsasResidualEquations 50 3.4 DiscretizationofDifferentialEquations 52 3.5 NumericalErrors 53 3.6 OverviewofSolvers 61 3.7 RateofConvergence 63 3.8 Newton-BasedSolvers 66 3.9 ModelsandtheOptimizationProblem 70 v Contents vi 3.10 Summary 73 Problems 75 4 UnconstrainedGradient-BasedOptimization 79 4.1 Fundamentals 80 4.2 TwoOverallApproachestoFindinganOptimum 94 4.3 LineSearch 96 4.4 SearchDirection 110 4.5 Trust-RegionMethods 139 4.6 Summary 147 Problems 149 5 ConstrainedGradient-BasedOptimization 153 5.1 ConstrainedProblemFormulation 154 5.2 Understandingn-DimensionalSpace 156 5.3 OptimalityConditions 158 5.4 PenaltyMethods 175 5.5 SequentialQuadraticProgramming 187 5.6 Interior-PointMethods 204 5.7 ConstraintAggregation 211 5.8 Summary 214 Problems 215 6 ComputingDerivatives 223 6.1 Derivatives,Gradients,andJacobians 223 6.2 OverviewofMethodsforComputingDerivatives 225 6.3 SymbolicDifferentiation 226 6.4 FiniteDifferences 227 6.5 ComplexStep 232 6.6 AlgorithmicDifferentiation 237 6.7 ImplicitAnalyticMethods—DirectandAdjoint 252 6.8 SparseJacobiansandGraphColoring 262 6.9 UnifiedDerivativesEquation 265 6.10 Summary 275 Problems 277 7 Gradient-FreeOptimization 281 7.1 WhentoUseGradient-FreeAlgorithms 281 7.2 ClassificationofGradient-FreeAlgorithms 284 7.3 Nelder–MeadAlgorithm 287 7.4 GeneralizedPatternSearch 292 7.5 DIRECTAlgorithm 298 7.6 GeneticAlgorithms 306 Contents vii 7.7 ParticleSwarmOptimization 316 7.8 Summary 321 Problems 323 8 DiscreteOptimization 327 8.1 Binary,Integer,andDiscreteVariables 327 8.2 AvoidingDiscreteVariables 328 8.3 BranchandBound 330 8.4 GreedyAlgorithms 337 8.5 DynamicProgramming 339 8.6 SimulatedAnnealing 347 8.7 BinaryGeneticAlgorithms 351 8.8 Summary 351 Problems 352 9 MultiobjectiveOptimization 355 9.1 MultipleObjectives 355 9.2 ParetoOptimality 357 9.3 SolutionMethods 358 9.4 Summary 369 Problems 370 10 Surrogate-BasedOptimization 373 10.1 WhentoUseaSurrogateModel 374 10.2 Sampling 375 10.3 ConstructingaSurrogate 384 10.4 Kriging 400 10.5 DeepNeuralNetworks 408 10.6 OptimizationandInfill 414 10.7 Summary 418 Problems 420 11 ConvexOptimization 423 11.1 Introduction 423 11.2 LinearProgramming 425 11.3 QuadraticProgramming 427 11.4 Second-OrderConeProgramming 429 11.5 DisciplinedConvexOptimization 430 11.6 GeometricProgramming 434 11.7 Summary 437 Problems 438 Contents viii 12 OptimizationUnderUncertainty 441 12.1 RobustDesign 442 12.2 ReliableDesign 447 12.3 ForwardPropagation 448 12.4 Summary 469 Problems 471 13 MultidisciplinaryDesignOptimization 475 13.1 TheNeedforMDO 475 13.2 CoupledModels 478 13.3 CoupledDerivativesComputation 501 13.4 MonolithicMDOArchitectures 510 13.5 DistributedMDOArchitectures 519 13.6 Summary 533 Problems 535 A MathematicsBackground 539 A.1 TaylorSeriesExpansion 539 A.2 ChainRule,TotalDerivatives,andDifferentials 541 A.3 MatrixMultiplication 544 A.4 FourFundamentalSubspacesinLinearAlgebra 547 A.5 VectorandMatrixNorms 548 A.6 MatrixTypes 550 A.7 MatrixDerivatives 552 A.8 EigenvaluesandEigenvectors 553 A.9 RandomVariables 554 B LinearSolvers 559 B.1 SystemsofLinearEquations 559 B.2 Conditioning 560 B.3 DirectMethods 560 B.4 IterativeMethods 562 C Quasi-NewtonMethods 571 C.1 Broyden’sMethod 571 C.2 AdditionalQuasi-NewtonApproximations 572 C.3 Sherman–Morrison–WoodburyFormula 576 D TestProblems 579 D.1 UnconstrainedProblems 579 D.2 ConstrainedProblems 586 Contents ix Bibliography 591 Index 615 Preface Despiteitsusefulness,designoptimizationremainsunderusedinin- dustry. Oneofthereasonsforthisistheshortageofdesignoptimization coursesinundergraduateandgraduatecurricula. Thisischanging; today,mosttopaerospaceandmechanicalengineeringdepartmentsin- cludeatleastonegraduate-levelcourseonnumericaloptimization. We havealsoseendesignoptimizationincreasinglyusedinanexpanding numberofindustries. The word engineering in the title reflects the types of problems andalgorithmswefocuson,eventhoughthemethodsareapplicable beyond engineering. In contrast to explicit analytic mathematical functions, most engineering problems are implemented in complex multidisciplinarycodesthatinvolveimplicitfunctions. Suchproblems mightrequirehierarchicalsolversandcoupledderivativecomputation. Furthermore,engineeringproblemsofteninvolvemanydesignvariables andconstraints,requiringscalablemethods. Thetargetaudienceforthisbookisadvancedundergraduateand beginninggraduatestudentsinscienceandengineering. Noprevious exposure to optimization is assumed. Knowledge of linear algebra, multivariablecalculus,andnumericalmethodsishelpful. However, thesesubjects’coreconceptsarereviewedinanappendixandasneeded inthetext. Thecontentofthebookspansapproximatelytwosemester- length university courses. Our approach is to start from the most general case problem and then explain special cases. The first half ofthebookcoversthefundamentals(alongwithanoptionalhistory chapter). Incontrast,thesecondhalf,fromChapter8onward,covers morespecializedoradvancedtopics. Ourphilosophyintheexpositionistoprovideadetailedenough explanationandanalysisofoptimizationalgorithmssothatreaders canimplementabasicworkingversion. Althoughwedonotencourage ∗ InthewordsofDonaldKnuth: “Theul- readerstousetheirimplementationsinsteadofexistingsoftwarefor timatetestofwhetherIunderstandsomething solvingoptimizationproblems,implementingamethodiscrucialin isifIcanexplainittoacomputer. Icansay ∗ somethingtoyouandyou’llnodyourhead, understandingthemethodanditsbehavior. Adeeperknowledgeof butI’mnotsurethatIexplaineditwell. But these methods is useful for developers, researchers, and those who thecomputerdoesn’tnoditshead. Itrepeats backexactlywhatItellit.Inmostoflife,you wanttousenumericaloptimizationmoreeffectively. Theproblemsat canbluff,butnotwithcomputers.” xi Preface xii theendofeachchapteraredesignedtoprovideagradualprogression indifficultyandeventuallyrequireimplementingthemethods. Some of the problems are open-ended to encourage students to explore a giventopicontheirown. Whendiscussingthevariousoptimization techniques,wealsoexplainhowtoavoidthepotentialpitfallsofusinga particularmethodandhowtoemployitmoreeffectively. Practicaltips areincludedthroughoutthebooktoalertthereadertocommonissues encounteredinengineeringdesignoptimizationandhowtoaddress them. We have created a repository with code, data, templates, and examplesasasupplementaryresourceforthisbook: https://github. com/mdobook/resources. Someoftheend-of-chapterexercisesrefer tocodeordatafromthisrepository. Goforthandoptimize!