Algorithms for Optimization (The MIT Press)

A comprehensive introduction to optimization with a focus on practical algorithms for the design of engineering systems. This book offers a comprehensive introduction to optimization with a focus on practical algorithms. The book approaches optimization from an engineering perspective, where the objective is to design a system that optimizes a set of metrics subject to constraints. Readers will learn about computational approaches for a range of challenges, including searching high-dimensional spaces, handling problems where there are multiple competing objectives, and accommodating uncertainty in the metrics. Figures, examples, and exercises convey the intuition behind the mathematical approaches. The text provides concrete implementations in the Julia programming language. Topics covered include derivatives and their generalization to multiple dimensions; local descent and first- and second-order methods that inform local descent; stochastic methods, which introduce randomness into the optimization process; linear constrained optimization, when both the objective function and the constraints are linear; surrogate models, probabilistic surrogate models, and using probabilistic surrogate models to guide optimization; optimization under uncertainty; uncertainty propagation; expression optimization; and multidisciplinary design optimization. Appendixes offer an introduction to the Julia language, test functions for evaluating algorithm performance, and mathematical concepts used in the derivation and analysis of the optimization methods discussed in the text. The book can be used by advanced undergraduates and graduate students in mathematics, statistics, computer science, any engineering field, (including electrical engineering and aerospace engineering), and operations research, and as a reference for professionals. -- Provided by publisher Contents......Page 8 Preface......Page 18 Acknowledgments......Page 20 1. Introduction......Page 22 1.1 A History......Page 23 1.2 Optimization Process......Page 25 1.3 Basic Optimization Problem......Page 26 1.4 Constraints......Page 27 1.5 Critical Points......Page 28 1.6 Conditions for Local Minima......Page 29 1.8 Overview......Page 32 1.10 Exercises......Page 38 2.1 Derivatives......Page 40 2.2 Derivatives in Multiple Dimensions......Page 42 2.3 Numerical Differentiation......Page 44 2.4 Automatic Differentiation......Page 48 2.5 Summary......Page 53 2.6 Exercises......Page 54 3.2 Finding an Initial Bracket......Page 56 3.3 Fibonacci Search......Page 58 3.4 Golden Section Search......Page 60 3.5 Quadratic Fit Search......Page 64 3.6 Shubert-Piyavskii Method......Page 66 3.7 Bisection Method......Page 70 3.9 Exercises......Page 72 4.1 Descent Direction Iteration......Page 74 4.2 Line Search......Page 75 4.3 Approximate Line Search......Page 76 4.4 Trust Region Methods......Page 82 4.5 Termination Conditions......Page 84 4.7 Exercises......Page 87 5.1 Gradient Descent......Page 90 5.2 Conjugate Gradient......Page 91 5.3 Momentum......Page 96 5.4 Nesterov Momentum......Page 97 5.5 Adagrad......Page 98 5.7 Adadelta......Page 99 5.8 Adam......Page 100 5.9 Hypergradient Descent......Page 101 5.11 Exercises......Page 105 6.1 Newton’s Method......Page 108 6.3 Quasi-Newton Methods......Page 112 6.5 Exercises......Page 116 7.1 Cyclic Coordinate Search......Page 120 7.2 Powell’s Method......Page 121 7.3 Hooke-Jeeves......Page 123 7.4 Generalized Pattern Search......Page 124 7.5 Nelder-Mead Simplex Method......Page 126 7.6 Divided Rectangles......Page 129 7.7 Summary......Page 141 7.8 Exercises......Page 144 8.1 Noisy Descent......Page 146 8.2 Mesh Adaptive Direct Search......Page 147 8.3 Simulated Annealing......Page 149 8.4 Cross-Entropy Method......Page 154 8.5 Natural Evolution Strategies......Page 158 8.6 Covariance Matrix Adaptation......Page 159 8.8 Exercises......Page 163 9.1 Initialization......Page 168 9.2 Genetic Algorithms......Page 169 9.3 Differential Evolution......Page 178 9.4 Particle Swarm Optimization......Page 179 9.5 Firefly Algorithm......Page 180 9.6 Cuckoo Search......Page 182 9.7 Hybrid Methods......Page 183 9.9 Exercises......Page 186 10.1 Constrained Optimization......Page 188 10.2 Constraint Types......Page 189 10.3 Transformations to Remove Constraints......Page 190 10.4 Lagrange Multipliers......Page 192 10.5 Inequality Constraints......Page 195 10.6 Duality......Page 198 10.7 Penalty Methods......Page 199 10.9 Interior Point Methods......Page 204 10.11 Exercises......Page 207 11.1 Problem Formulation......Page 210 11.2 Simplex Algorithm......Page 216 11.3 Dual Certificates......Page 227 11.5 Exercises......Page 231 12.1 Pareto Optimality......Page 232 12.2 Constraint Methods......Page 237 12.3 Weight Methods......Page 239 12.4 Multiobjective Population Methods......Page 242 12.5 Preference Elicitation......Page 249 12.7 Exercises......Page 253 13.1 Full Factorial......Page 256 13.2 Random Sampling......Page 257 13.3 Uniform Projection Plans......Page 258 13.4 Stratified Sampling......Page 259 13.5 Space-Filling Metrics......Page 260 13.6 Space-Filling Subsets......Page 265 13.7 Quasi-Random Sequences......Page 266 13.9 Exercises......Page 272 14.1 Fitting Surrogate Models......Page 274 14.2 Linear Models......Page 275 14.3 Basis Functions......Page 276 14.4 Fitting Noisy Objective Functions......Page 284 14.5 Model Selection......Page 286 14.7 Exercises......Page 295 15.1 Gaussian Distribution......Page 296 15.2 Gaussian Processes......Page 298 15.3 Prediction......Page 301 15.4 Gradient Measurements......Page 303 15.5 Noisy Measurements......Page 306 15.6 Fitting Gaussian Processes......Page 308 15.8 Exercises......Page 309 16.1 Prediction-Based Exploration......Page 312 16.2 Error-Based Exploration......Page 313 16.4 Probability of Improvement Exploration......Page 314 16.5 Expected Improvement Exploration......Page 315 16.6 Safe Optimization......Page 317 16.8 Exercises......Page 326 17.1 Uncertainty......Page 328 17.2 Set-Based Uncertainty......Page 330 17.3 Probabilistic Uncertainty......Page 333 17.5 Exercises......Page 339 18.1 Sampling Methods......Page 342 18.2 Taylor Approximation......Page 343 18.3 Polynomial Chaos......Page 344 18.4 Bayesian Monte Carlo......Page 355 18.6 Exercises......Page 358 19. Discrete Optimization......Page 360 19.1 Integer Programs......Page 361 19.2 Rounding......Page 362 19.3 Cutting Planes......Page 363 19.4 Branch and Bound......Page 367 19.5 Dynamic Programming......Page 372 19.6 Ant Colony Optimization......Page 375 19.8 Exercises......Page 379 20.1 Grammars......Page 382 20.2 Genetic Programming......Page 385 20.3 Grammatical Evolution......Page 391 20.4 Probabilistic Grammars......Page 396 20.5 Probabilistic Prototype Trees......Page 398 20.6 Summary......Page 403 20.7 Exercises......Page 405 21.1 Disciplinary Analyses......Page 408 21.2 Interdisciplinary Compatibility......Page 410 21.4 Multidisciplinary Design Feasible......Page 414 21.5 Sequential Optimization......Page 417 21.6 Individual Discipline Feasible......Page 419 21.7 Collaborative Optimization......Page 424 21.8 Simultaneous Analysis and Design......Page 427 21.9 Summary......Page 428 21.10 Exercises......Page 429 A.1 Types......Page 432 A.2 Functions......Page 441 A.3 Control Flow......Page 443 A.4 Packages......Page 444 B.1 Ackley’s Function......Page 446 B.2 Booth’s Function......Page 447 B.3 Branin Function......Page 448 B.4 Flower Function......Page 449 B.5 Michalewicz Function......Page 450 B.6 Rosenbrock’s Banana Function......Page 451 B.7 Wheeler’s Ridge......Page 452 B.8 Circle Function......Page 453 C.1 Asymptotic Notation......Page 454 C.2 Taylor Expansion......Page 456 C.3 Convexity......Page 457 C.5 Matrix Calculus......Page 460 C.7 Gaussian Distribution......Page 463 C.8 Gaussian Quadrature......Page 464 D. Solutions......Page 468 Bibliography......Page 504 Index......Page 516 "A comprehensive introduction to optimization with a focus on practical algorithms for the design of engineering systems. This book offers a comprehensive introduction to optimization with a focus on practical algorithms. The book approaches optimization from an engineering perspective, where the objective is to design a system that optimizes a set of metrics subject to constraints. Readers will learn about computational approaches for a range of challenges, including searching high-dimensional spaces, handling problems where there are multiple competing objectives, and accommodating uncertainty in the metrics. Figures, examples, and exercises convey the intuition behind the mathematical approaches. The text provides concrete implementations in the Julia programming language. Topics covered include derivatives and their generalization to multiple dimensions; local descent and first- and second-order methods that inform local descent; stochastic methods, which introduce randomness into the optimization process; linear constrained optimization, when both the objective function and the constraints are linear; surrogate models, probabilistic surrogate models, and using probabilistic surrogate models to guide optimization; optimization under uncertainty; uncertainty propagation; expression optimization; and multidisciplinary design optimization. Appendixes offer an introduction to the Julia language, test functions for evaluating algorithm performance, and mathematical concepts used in the derivation and analysis of the optimization methods discussed in the text. The book can be used by advanced undergraduates and graduate students in mathematics, statistics, computer science, any engineering field, (including electrical engineering and aerospace engineering), and operations research, and as a reference for professionals"--Nota del editor