Optimization Techniques and Applications with Examples

XIN-SHE YANG, PHD, is Reader/Professor in Modelling and Optimization at Middlesex University London. He is also an elected Bye-Fellow and College Lecturer at Cambridge University, Adjunct Professor at Reykjavik University, Iceland, as well as Distinguished Chair Professor at Xi'an Polytechnic University, China.

• List of Figures xiiiList of Tables xviiPreface xixAcknowledgements xxiAcronyms xxiiiIntroduction xxvPart I Fundamentals 11 Mathematical Foundations 31.1 Functions and Continuity 31.1.1 Functions 31.1.2 Continuity 41.1.3 Upper and Lower Bounds 41.2 Review of Calculus 61.2.1 Differentiation 61.2.2 Taylor Expansions 91.2.3 Partial Derivatives 121.2.4 Lipschitz Continuity 131.2.5 Integration 141.3 Vectors 161.3.1 Vector Algebra 171.3.2 Norms 171.3.3 2D Norms 191.4 Matrix Algebra 191.4.1 Matrices 191.4.2 Determinant 231.4.3 Rank of a Matrix 241.4.4 Frobenius Norm 251.5 Eigenvalues and Eigenvectors 251.5.1 Definiteness 281.5.2 Quadratic Form 291.6 Optimization and Optimality 311.6.1 Minimum and Maximum 311.6.2 Feasible Solution 321.6.3 Gradient and Hessian Matrix 321.6.4 Optimality Conditions 341.7 General Formulation of Optimization Problems 35Exercises 36Further Reading 362 Algorithms, Complexity, and Convexity 372.1 What Is an Algorithm? 372.2 Order Notations 392.3 Convergence Rate 402.4 Computational Complexity 422.4.1 Time and Space Complexity 422.4.2 Class P 432.4.3 Class NP 442.4.4 NP-Completeness 442.4.5 Complexity of Algorithms 452.5 Convexity 462.5.1 Linear and Affine Functions 462.5.2 Convex Functions 482.5.3 Subgradients 502.6 Stochastic Nature in Algorithms 512.6.1 Algorithms with Randomization 512.6.2 Random Variables 512.6.3 Poisson Distribution and Gaussian Distribution 542.6.4 Monte Carlo 562.6.5 Common Probability Distributions 58Exercises 61Bibliography 62Part II Optimization Techniques and Algorithms 633 Optimization 653.1 Unconstrained Optimization 653.1.1 Univariate Functions 653.1.2 Multivariate Functions 683.2 Gradient-Based Methods 703.2.1 Newton’s Method 713.2.2 Convergence Analysis 723.2.3 Steepest Descent Method 733.2.4 Line Search 773.2.5 Conjugate Gradient Method 783.2.6 Stochastic Gradient Descent 793.2.7 Subgradient Method 813.3 Gradient-Free Nelder–Mead Method 813.3.1 A Simplex 813.3.2 Nelder–Mead Downhill Simplex Method 82Exercises 84Bibliography 844 Constrained Optimization 874.1 Mathematical Formulation 874.2 Lagrange Multipliers 874.3 Slack Variables 914.4 Generalized Reduced Gradient Method 944.5 KKT Conditions 974.6 PenaltyMethod 99Exercises 101Bibliography 1015 Optimization Techniques: Approximation Methods 1035.1 BFGS Method 1035.2 Trust-Region Method 1055.3 Sequential Quadratic Programming 1075.3.1 Quadratic Programming 1075.3.2 SQP Procedure 1075.4 Convex Optimization 1095.5 Equality Constrained Optimization 1135.6 Barrier Functions 1155.7 Interior-PointMethods 1195.8 Stochastic and Robust Optimization 121Exercises 123Bibliography 123Part III Applied Optimization 1256 Linear Programming 1276.1 Introduction 1276.2 Simplex Method 1296.2.1 Slack Variables 1296.2.2 Standard Formulation 1306.2.3 Duality 1316.2.4 Augmented Form 1326.3 Worked Example by Simplex Method 1336.4 Interior-PointMethod for LP 136Exercises 139Bibliography 1397 Integer Programming 1417.1 Integer Linear Programming 1417.1.1 Review of LP 1417.1.2 Integer LP 1427.2 LP Relaxation 1437.3 Branch and Bound 1467.3.1 How to Branch 1537.4 Mixed Integer Programming 1557.5 Applications of LP, IP, and MIP 1567.5.1 Transport Problem 1567.5.2 Product Portfolio 1587.5.3 Scheduling 1607.5.4 Knapsack Problem 1617.5.5 Traveling Salesman Problem 161Exercises 163Bibliography 1638 Regression and Regularization 1658.1 Sample Mean and Variance 1658.2 Regression Analysis 1688.2.1 Maximum Likelihood 1688.2.2 Regression 1688.2.3 Linearization 1738.2.4 Generalized Linear Regression 1758.2.5 Goodness of Fit 1788.3 Nonlinear Least Squares 1798.3.1 Gauss–Newton Algorithm 1808.3.2 Levenberg–Marquardt Algorithm 1828.3.3 Weighted Least Squares 1838.4 Over-fitting and Information Criteria 1848.5 Regularization and Lasso Method 1868.6 Logistic Regression 1878.7 Principal Component Analysis 191Exercises 195Bibliography 1969 Machine Learning Algorithms 1999.1 Data Mining 1999.1.1 Hierarchy Clustering 2009.1.2 k-Means Clustering 2019.1.3 Distance Metric 2029.2 Data Mining for Big Data 2029.2.1 Characteristics of Big Data 2039.2.2 Statistical Nature of Big Data 2039.2.3 Mining Big Data 2049.3 Artificial Neural Networks 2069.3.1 Neuron Model 2079.3.2 Neural Networks 2089.3.3 Back Propagation Algorithm 2109.3.4 Loss Functions in ANN 2129.3.5 Stochastic Gradient Descent 2139.3.6 Restricted Boltzmann Machine 2149.4 Support Vector Machines 2169.4.1 Statistical Learning Theory 2169.4.2 Linear Support Vector Machine 2179.4.3 Kernel Functions and Nonlinear SVM 2209.5 Deep Learning 2219.5.1 Learning 2219.5.2 Deep Neural Nets 2229.5.3 Tuning of Hyper-Parameters 223Exercises 223Bibliography 22410 Queueing Theory and Simulation 22710.1 Introduction 22710.1.1 Components of Queueing 22710.1.2 Notations 22810.2 Arrival Model 23010.2.1 Poisson Distribution 23010.2.2 Inter-arrival Time 23310.3 Service Model 23310.3.1 Exponential Distribution 23310.3.2 Service Time Model 23510.3.3 Erlang Distribution 23510.4 Basic QueueingModel 23610.4.1 M/M/1 Queue 23610.4.2 M/M/s Queue 24010.5 Little’s Law 24210.6 Queue Management and Optimization 243Exercises 245Bibliography 246Part IV Advanced Topics 24911 Multiobjective Optimization 25111.1 Introduction 25111.2 Pareto Front and Pareto Optimality 25311.3 Choice and Challenges 25511.4 Transformation to Single Objective Optimization 25611.4.1 Weighted Sum Method 25611.4.2 Utility Function 25911.5 The 𝜖-Constraint Method 26111.6 Evolutionary Approaches 26411.6.1 Metaheuristics 26411.6.2 Non-Dominated Sorting Genetic Algorithm 265Exercises 266Bibliography 26612 Constraint-Handling Techniques 26912.1 Introduction and Overview 26912.2 Method of Lagrange Multipliers 27012.3 Barrier Function Method 27212.4 PenaltyMethod 27212.5 Equality Constraints via Tolerance 27312.6 Feasibility Criteria 27412.7 Stochastic Ranking 27512.8 Multiobjective Constraint-Handling and Ranking 276Exercises 276Bibliography 277Part V Evolutionary Computation and Nature-InspiredAlgorithms 27913 Evolutionary Algorithms 28113.1 Evolutionary Computation 28113.3.1 Basic Procedure 28413.3.2 Choice of Parameters 28513.4 Simulated Annealing 28713.5 Differential Evolution 290Exercises 293Bibliography 29314 Nature-Inspired Algorithms 29714.1 Introduction to SI 29714.2 Ant and Bee Algorithms 29814.3 Particle Swarm Optimization 29914.3.1 Accelerated PSO 30114.3.2 Binary PSO 30214.4 Firefly Algorithm 30314.5 Cuckoo Search 30614.5.1 CS Algorithm 30714.5.2 Lévy Flight 30914.5.3 Advantages of CS 31214.6 Bat Algorithm 31314.7 Flower Pollination Algorithm 31514.8 Other Algorithms 319Exercises 319Bibliography 319Appendix A Notes on Software Packages 323Appendix B Problem Solutions 329Index 345