Algorithms for Optimization

by Kochenderfer, Wheeler

ISBN: 9780262039420 | Copyright 2019

Click here to preview

Instructor Requests

Digital Exam/Desk Copy Print Desk Copy Ancillaries
Tabs

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.

Expand/Collapse All
Contents (pg. vii)
Preface (pg. xvii)
Acknowledgments (pg. xix)
1. Introduction (pg. 1)
1.1 A History (pg. 2)
1.2 Optimization Process (pg. 4)
1.3 Basic Optimization Problem (pg. 5)
1.4 Constraints (pg. 6)
1.5 Critical Points (pg. 7)
1.6 Conditions for Local Minima (pg. 8)
1.7 Contour Plots (pg. 11)
1.8 Overview (pg. 11)
1.9 Summary (pg. 17)
1.10 Exercises (pg. 17)
2. Derivatives and Gradients (pg. 19)
2.1 Derivatives (pg. 19)
2.2 Derivatives in Multiple Dimensions (pg. 21)
2.3 Numerical Differentiation (pg. 23)
2.4 Automatic Differentiation (pg. 27)
2.5 Summary (pg. 32)
2.6 Exercises (pg. 33)
3. Bracketing (pg. 35)
3.1 Unimodality (pg. 35)
3.2 Finding an Initial Bracket (pg. 35)
3.3 Fibonacci Search (pg. 37)
3.4 Golden Section Search (pg. 39)
3.5 Quadratic Fit Search (pg. 43)
3.6 Shubert-Piyavskii Method (pg. 45)
3.7 Bisection Method (pg. 49)
3.8 Summary (pg. 51)
3.9 Exercises (pg. 51)
4. Local Descent (pg. 53)
4.1 Descent Direction Iteration (pg. 53)
4.2 Line Search (pg. 54)
4.3 Approximate Line Search (pg. 55)
4.4 Trust Region Methods (pg. 61)
4.5 Termination Conditions (pg. 63)
4.6 Summary (pg. 66)
4.7 Exercises (pg. 66)
5. First-Order Methods (pg. 69)
5.1 Gradient Descent (pg. 69)
5.2 Conjugate Gradient (pg. 70)
5.3 Momentum (pg. 75)
5.4 Nesterov Momentum (pg. 76)
5.5 Adagrad (pg. 77)
5.6 RMSProp (pg. 78)
5.7 Adadelta (pg. 78)
5.8 Adam (pg. 79)
5.9 Hypergradient Descent (pg. 80)
5.10 Summary (pg. 84)
5.11 Exercises (pg. 84)
6. Second-Order Methods (pg. 87)
6.1 Newton’s Method (pg. 87)
6.2 Secant Method (pg. 91)
6.3 Quasi-Newton Methods (pg. 91)
6.4 Summary (pg. 95)
6.5 Exercises (pg. 95)
7. Direct Methods (pg. 99)
7.1 Cyclic Coordinate Search (pg. 99)
7.2 Powell’s Method (pg. 100)
7.3 Hooke-Jeeves (pg. 102)
7.4 Generalized Pattern Search (pg. 103)
7.5 Nelder-Mead Simplex Method (pg. 105)
7.6 Divided Rectangles (pg. 108)
7.7 Summary (pg. 120)
7.8 Exercises (pg. 123)
8. Stochastic Methods (pg. 125)
8.1 Noisy Descent (pg. 125)
8.2 Mesh Adaptive Direct Search (pg. 126)
8.3 Simulated Annealing (pg. 128)
8.4 Cross-Entropy Method (pg. 133)
8.5 Natural Evolution Strategies (pg. 137)
8.6 Covariance Matrix Adaptation (pg. 138)
8.7 Summary (pg. 142)
8.8 Exercises (pg. 142)
9. Population Methods (pg. 147)
9.1 Initialization (pg. 147)
9.2 Genetic Algorithms (pg. 148)
9.3 Differential Evolution (pg. 157)
9.4 Particle Swarm Optimization (pg. 158)
9.5 Firefly Algorithm (pg. 159)
9.6 Cuckoo Search (pg. 161)
9.7 Hybrid Methods (pg. 162)
9.8 Summary (pg. 165)
9.9 Exercises (pg. 165)
10. Constraints (pg. 167)
10.1 Constrained Optimization (pg. 167)
10.2 Constraint Types (pg. 168)
10.3 Transformations to Remove Constraints (pg. 169)
10.4 Lagrange Multipliers (pg. 171)
10.5 Inequality Constraints (pg. 174)
10.6 Duality (pg. 177)
10.7 Penalty Methods (pg. 178)
10.8 Augmented Lagrange Method (pg. 183)
10.9 Interior Point Methods (pg. 183)
10.10 Summary (pg. 186)
10.11 Exercises (pg. 186)
11. Linear Constrained Optimization (pg. 189)
11.1 Problem Formulation (pg. 189)
11.2 Simplex Algorithm (pg. 195)
11.3 Dual Certificates (pg. 206)
11.4 Summary (pg. 210)
11.5 Exercises (pg. 210)
12. Multiobjective Optimization (pg. 211)
12.1 Pareto Optimality (pg. 211)
12.2 Constraint Methods (pg. 216)
12.3 Weight Methods (pg. 218)
12.4 Multiobjective Population Methods (pg. 221)
12.5 Preference Elicitation (pg. 228)
12.6 Summary (pg. 232)
12.7 Exercises (pg. 232)
13. Sampling Plans (pg. 235)
13.1 Full Factorial (pg. 235)
13.2 Random Sampling (pg. 236)
13.3 Uniform Projection Plans (pg. 237)
13.4 Stratified Sampling (pg. 238)
13.5 Space-Filling Metrics (pg. 239)
13.6 Space-Filling Subsets (pg. 244)
13.7 Quasi-Random Sequences (pg. 245)
13.8 Summary (pg. 251)
13.9 Exercises (pg. 251)
14. Surrogate Models (pg. 253)
14.1 Fitting Surrogate Models (pg. 253)
14.2 Linear Models (pg. 254)
14.3 Basis Functions (pg. 255)
14.4 Fitting Noisy Objective Functions (pg. 263)
14.5 Model Selection (pg. 265)
14.6 Summary (pg. 274)
14.7 Exercises (pg. 274)
15. Probabilistic Surrogate Models (pg. 275)
15.1 Gaussian Distribution (pg. 275)
15.2 Gaussian Processes (pg. 277)
15.3 Prediction (pg. 280)
15.4 Gradient Measurements (pg. 282)
15.5 Noisy Measurements (pg. 285)
15.6 Fitting Gaussian Processes (pg. 287)
15.7 Summary (pg. 288)
15.8 Exercises (pg. 288)
16. Surrogate Optimization (pg. 291)
16.1 Prediction-Based Exploration (pg. 291)
16.2 Error-Based Exploration (pg. 292)
16.3 Lower Confidence Bound Exploration (pg. 293)
16.4 Probability of Improvement Exploration (pg. 293)
16.5 Expected Improvement Exploration (pg. 294)
16.6 Safe Optimization (pg. 296)
16.7 Summary (pg. 305)
16.8 Exercises (pg. 305)
17. Optimization under Uncertainty (pg. 307)
17.1 Uncertainty (pg. 307)
17.2 Set-Based Uncertainty (pg. 309)
17.3 Probabilistic Uncertainty (pg. 312)
17.4 Summary (pg. 318)
17.5 Exercises (pg. 318)
18. Uncertainty Propagation (pg. 321)
18.1 Sampling Methods (pg. 321)
18.2 Taylor Approximation (pg. 322)
18.3 Polynomial Chaos (pg. 323)
18.4 Bayesian Monte Carlo (pg. 334)
18.5 Summary (pg. 337)
18.6 Exercises (pg. 337)
19. Discrete Optimization (pg. 339)
19.1 Integer Programs (pg. 340)
19.2 Rounding (pg. 341)
19.3 Cutting Planes (pg. 342)
19.4 Branch and Bound (pg. 346)
19.5 Dynamic Programming (pg. 351)
19.6 Ant Colony Optimization (pg. 354)
19.7 Summary (pg. 358)
19.8 Exercises (pg. 358)
20. Expression Optimization (pg. 361)
20.1 Grammars (pg. 361)
20.2 Genetic Programming (pg. 364)
20.3 Grammatical Evolution (pg. 370)
20.4 Probabilistic Grammars (pg. 375)
20.5 Probabilistic Prototype Trees (pg. 377)
20.6 Summary (pg. 382)
20.7 Exercises (pg. 384)
21. Multidisciplinary Optimization (pg. 387)
21.1 Disciplinary Analyses (pg. 387)
21.2 Interdisciplinary Compatibility (pg. 389)
21.3 Architectures (pg. 393)
21.4 Multidisciplinary Design Feasible (pg. 393)
21.5 Sequential Optimization (pg. 396)
21.6 Individual Discipline Feasible (pg. 398)
21.7 Collaborative Optimization (pg. 403)
21.8 Simultaneous Analysis and Design (pg. 406)
21.9 Summary (pg. 407)
21.10 Exercises (pg. 408)
A. Julia (pg. 411)
A.1 Types (pg. 411)
A.2 Functions (pg. 420)
A.3 Control Flow (pg. 422)
A.4 Packages (pg. 423)
B. Test Functions (pg. 425)
B.1 Ackley’s Function (pg. 425)
B.2 Booth’s Function (pg. 426)
B.3 Branin Function (pg. 427)
B.4 Flower Function (pg. 428)
B.5 Michalewicz Function (pg. 429)
B.6 Rosenbrock’s Banana Function (pg. 430)
B.7 Wheeler’s Ridge (pg. 431)
B.8 Circle Function (pg. 432)
C. Mathematical Concepts (pg. 433)
C.1 Asymptotic Notation (pg. 433)
C.2 Taylor Expansion (pg. 435)
C.3 Convexity (pg. 436)
C.4 Norms (pg. 439)
C.5 Matrix Calculus (pg. 439)
C.6 Positive Definiteness (pg. 442)
C.7 Gaussian Distribution (pg. 442)
C.8 Gaussian Quadrature (pg. 443)
D. Solutions (pg. 447)
Bibliography (pg. 483)
Index (pg. 495)

Tim A. Wheeler

Tim A. Wheeler is a software engineer at Kitty Hawk Corporation in Mountain View, California.

Instructors Only
You must have an instructor account and submit a request to access instructor materials for this book.
eTextbook
Go paperless today! Available online anytime, nothing to download or install.

Features

  • Bookmarking
  • Note taking
  • Highlighting