OptimizationTechniquesandApplicationswithExamples Optimization Techniques and Applications with Examples Xin-SheYang MiddlesexUniversityLondon Thiseditionfirstpublished2018 ©2018JohnWiley&Sons,Inc. Allrightsreserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,or transmitted,inanyformorbyanymeans,electronic,mechanical,photocopying,recordingor otherwise,exceptaspermittedbylaw.Adviceonhowtoobtainpermissiontoreusematerialfromthis titleisavailableathttp://www.wiley.com/go/permissions. TherightofXin-SheYangtobeidentifiedastheauthorofthematerialinthisworkhasbeenassertedin accordancewithlaw. RegisteredOffice JohnWiley&Sons,Inc.,111RiverStreet,Hoboken,NJ07030,USA EditorialOffice 111RiverStreet,Hoboken,NJ07030,USA Fordetailsofourglobaleditorialoffices,customerservices,andmoreinformationaboutWileyproducts visitusatwww.wiley.com. Wileyalsopublishesitsbooksinavarietyofelectronicformatsandbyprint-on-demand.Somecontent thatappearsinstandardprintversionsofthisbookmaynotbeavailableinotherformats. LimitofLiability/DisclaimerofWarranty Inviewofongoingresearch,equipmentmodifications,changesingovernmentalregulations,andthe constantflowofinformationrelatingtotheuseofexperimentalreagents,equipment,anddevices,the readerisurgedtoreviewandevaluatetheinformationprovidedinthepackageinsertorinstructionsfor eachchemical,pieceofequipment,reagent,ordevicefor,amongotherthings,anychangesinthe instructionsorindicationofusageandforaddedwarningsandprecautions.Whilethepublisherand authorshaveusedtheirbesteffortsinpreparingthiswork,theymakenorepresentationsorwarranties withrespecttotheaccuracyorcompletenessofthecontentsofthisworkandspecificallydisclaimall warranties,includingwithoutlimitationanyimpliedwarrantiesofmerchantabilityorfitnessfora particularpurpose.Nowarrantymaybecreatedorextendedbysalesrepresentatives,writtensales materialsorpromotionalstatementsforthiswork.Thefactthatanorganization,website,orproductis referredtointhisworkasacitationand/orpotentialsourceoffurtherinformationdoesnotmeanthat thepublisherandauthorsendorsetheinformationorservicestheorganization,website,orproductmay provideorrecommendationsitmaymake.Thisworkissoldwiththeunderstandingthatthepublisheris notengagedinrenderingprofessionalservices.Theadviceandstrategiescontainedhereinmaynotbe suitableforyoursituation.Youshouldconsultwithaspecialistwhereappropriate.Further,readers shouldbeawarethatwebsiteslistedinthisworkmayhavechangedordisappearedbetweenwhenthis workwaswrittenandwhenitisread.Neitherthepublishernorauthorsshallbeliableforanylossof profitoranyothercommercialdamages,includingbutnotlimitedtospecial,incidental,consequential, orotherdamages. LibraryofCongressCataloging-in-PublicationData Names:Yang,Xin-She,author. Title:Optimizationtechniquesandapplicationswithexamples/Xin-SheYang. Description:Hoboken,NewJersey:JohnWiley&Sons,2018.|Includesbibliographical referencesandindex.| Identifiers:LCCN2018019716(print)|LCCN2018033280(ebook)|ISBN9781119490609 (AdobePDF)|ISBN9781119490623(ePub)|ISBN9781119490548(hardcover) Subjects:LCSH:Mathematicaloptimization. Classification:LCCQA402.5(ebook)|LCCQA402.5.Y3662018(print)|DDC519.6–dc23 LCrecordavailableathttps://lccn.loc.gov/2018019716 Coverimage:©MirageC/GettyImages Coverdesign:Wiley Setin10/12ptWarnockbySPiGlobal,Pondicherry,India PrintedintheUnitedStatesofAmerica 10 9 8 7 6 5 4 3 2 1 v Contents ListofFigures xiii ListofTables xvii Preface xix Acknowledgements xxi Acronyms xxiii Introduction xxv PartI Fundamentals 1 1 MathematicalFoundations 3 1.1 FunctionsandContinuity 3 1.1.1 Functions 3 1.1.2 Continuity 4 1.1.3 UpperandLowerBounds 4 1.2 ReviewofCalculus 6 1.2.1 Differentiation 6 1.2.2 TaylorExpansions 9 1.2.3 PartialDerivatives 12 1.2.4 LipschitzContinuity 13 1.2.5 Integration 14 1.3 Vectors 16 1.3.1 VectorAlgebra 17 1.3.2 Norms 17 1.3.3 2DNorms 19 1.4 MatrixAlgebra 19 1.4.1 Matrices 19 1.4.2 Determinant 23 1.4.3 RankofaMatrix 24 1.4.4 FrobeniusNorm 25 vi Contents 1.5 EigenvaluesandEigenvectors 25 1.5.1 Definiteness 28 1.5.2 QuadraticForm 29 1.6 OptimizationandOptimality 31 1.6.1 MinimumandMaximum 31 1.6.2 FeasibleSolution 32 1.6.3 GradientandHessianMatrix 32 1.6.4 OptimalityConditions 34 1.7 GeneralFormulationofOptimizationProblems 35 Exercises 36 FurtherReading 36 2 Algorithms,Complexity,andConvexity 37 2.1 WhatIsanAlgorithm? 37 2.2 OrderNotations 39 2.3 ConvergenceRate 40 2.4 ComputationalComplexity 42 2.4.1 TimeandSpaceComplexity 42 2.4.2 ClassP 43 2.4.3 ClassNP 44 2.4.4 NP-Completeness 44 2.4.5 ComplexityofAlgorithms 45 2.5 Convexity 46 2.5.1 LinearandAffineFunctions 46 2.5.2 ConvexFunctions 48 2.5.3 Subgradients 50 2.6 StochasticNatureinAlgorithms 51 2.6.1 AlgorithmswithRandomization 51 2.6.2 RandomVariables 51 2.6.3 PoissonDistributionandGaussianDistribution 54 2.6.4 MonteCarlo 56 2.6.5 CommonProbabilityDistributions 58 Exercises 61 Bibliography 62 PartII OptimizationTechniquesandAlgorithms 63 3 Optimization 65 3.1 UnconstrainedOptimization 65 3.1.1 UnivariateFunctions 65 3.1.2 MultivariateFunctions 68 3.2 Gradient-BasedMethods 70 Contents vii 3.2.1 Newton’sMethod 71 3.2.2 ConvergenceAnalysis 72 3.2.3 SteepestDescentMethod 73 3.2.4 LineSearch 77 3.2.5 ConjugateGradientMethod 78 3.2.6 StochasticGradientDescent 79 3.2.7 SubgradientMethod 81 3.3 Gradient-FreeNelder–MeadMethod 81 3.3.1 ASimplex 81 3.3.2 Nelder–MeadDownhillSimplexMethod 82 Exercises 84 Bibliography 84 4 ConstrainedOptimization 87 4.1 MathematicalFormulation 87 4.2 LagrangeMultipliers 87 4.3 SlackVariables 91 4.4 GeneralizedReducedGradientMethod 94 4.5 KKTConditions 97 4.6 PenaltyMethod 99 Exercises 101 Bibliography 101 5 OptimizationTechniques:ApproximationMethods 103 5.1 BFGSMethod 103 5.2 Trust-RegionMethod 105 5.3 SequentialQuadraticProgramming 107 5.3.1 QuadraticProgramming 107 5.3.2 SQPProcedure 107 5.4 ConvexOptimization 109 5.5 EqualityConstrainedOptimization 113 5.6 BarrierFunctions 115 5.7 Interior-PointMethods 119 5.8 StochasticandRobustOptimization 121 Exercises 123 Bibliography 123 PartIII AppliedOptimization 125 6 LinearProgramming 127 6.1 Introduction 127 6.2 SimplexMethod 129 viii Contents 6.2.1 SlackVariables 129 6.2.2 StandardFormulation 130 6.2.3 Duality 131 6.2.4 AugmentedForm 132 6.3 WorkedExamplebySimplexMethod 133 6.4 Interior-PointMethodforLP 136 Exercises 139 Bibliography 139 7 IntegerProgramming 141 7.1 IntegerLinearProgramming 141 7.1.1 ReviewofLP 141 7.1.2 IntegerLP 142 7.2 LPRelaxation 143 7.3 BranchandBound 146 7.3.1 HowtoBranch 153 7.4 MixedIntegerProgramming 155 7.5 ApplicationsofLP,IP,andMIP 156 7.5.1 TransportProblem 156 7.5.2 ProductPortfolio 158 7.5.3 Scheduling 160 7.5.4 KnapsackProblem 161 7.5.5 TravelingSalesmanProblem 161 Exercises 163 Bibliography 163 8 RegressionandRegularization 165 8.1 SampleMeanandVariance 165 8.2 RegressionAnalysis 168 8.2.1 MaximumLikelihood 168 8.2.2 Regression 168 8.2.3 Linearization 173 8.2.4 GeneralizedLinearRegression 175 8.2.5 GoodnessofFit 178 8.3 NonlinearLeastSquares 179 8.3.1 Gauss–NewtonAlgorithm 180 8.3.2 Levenberg–MarquardtAlgorithm 182 8.3.3 WeightedLeastSquares 183 8.4 Over-fittingandInformationCriteria 184 8.5 RegularizationandLassoMethod 186 8.6 LogisticRegression 187 8.7 PrincipalComponentAnalysis 191 Contents ix Exercises 195 Bibliography 196 9 MachineLearningAlgorithms 199 9.1 DataMining 199 9.1.1 HierarchyClustering 200 9.1.2 k-MeansClustering 201 9.1.3 DistanceMetric 202 9.2 DataMiningforBigData 202 9.2.1 CharacteristicsofBigData 203 9.2.2 StatisticalNatureofBigData 203 9.2.3 MiningBigData 204 9.3 ArtificialNeuralNetworks 206 9.3.1 NeuronModel 207 9.3.2 NeuralNetworks 208 9.3.3 BackPropagationAlgorithm 210 9.3.4 LossFunctionsinANN 212 9.3.5 StochasticGradientDescent 213 9.3.6 RestrictedBoltzmannMachine 214 9.4 SupportVectorMachines 216 9.4.1 StatisticalLearningTheory 216 9.4.2 LinearSupportVectorMachine 217 9.4.3 KernelFunctionsandNonlinearSVM 220 9.5 DeepLearning 221 9.5.1 Learning 221 9.5.2 DeepNeuralNets 222 9.5.3 TuningofHyper-Parameters 223 Exercises 223 Bibliography 224 10 QueueingTheoryandSimulation 227 10.1 Introduction 227 10.1.1 ComponentsofQueueing 227 10.1.2 Notations 228 10.2 ArrivalModel 230 10.2.1 PoissonDistribution 230 10.2.2 Inter-arrivalTime 233 10.3 ServiceModel 233 10.3.1 ExponentialDistribution 233 10.3.2 ServiceTimeModel 235 10.3.3 ErlangDistribution 235 10.4 BasicQueueingModel 236 10.4.1 M/M/1Queue 236 x Contents 10.4.2 M/M/sQueue 240 10.5 Little’sLaw 242 10.6 QueueManagementandOptimization 243 Exercises 245 Bibliography 246 PartIV AdvancedTopics 249 11 MultiobjectiveOptimization 251 11.1 Introduction 251 11.2 ParetoFrontandParetoOptimality 253 11.3 ChoiceandChallenges 255 11.4 TransformationtoSingleObjectiveOptimization 256 11.4.1 WeightedSumMethod 256 11.4.2 UtilityFunction 259 11.5 The𝜖-ConstraintMethod 261 11.6 EvolutionaryApproaches 264 11.6.1 Metaheuristics 264 11.6.2 Non-DominatedSortingGeneticAlgorithm 265 Exercises 266 Bibliography 266 12 Constraint-HandlingTechniques 269 12.1 IntroductionandOverview 269 12.2 MethodofLagrangeMultipliers 270 12.3 BarrierFunctionMethod 272 12.4 PenaltyMethod 272 12.5 EqualityConstraintsviaTolerance 273 12.6 FeasibilityCriteria 274 12.7 StochasticRanking 275 12.8 MultiobjectiveConstraint-HandlingandRanking 276 Exercises 276 Bibliography 277 PartV EvolutionaryComputationandNature-Inspired Algorithms 279 13 EvolutionaryAlgorithms 281 13.1 EvolutionaryComputation 281 13.2 EvolutionaryStrategy 282 13.3 GeneticAlgorithms 283