Share E-Book

Algorithms for Optimization Second Edition (Mykel J. Kochenderfer, Tim A. Wheeler)(Z-Library)

Author

,

Rating 4.0 AI initial rating

Log in to rate

Data Structures and Algorithms
Language English

The extensively updated second edition of this popular textbook provides a comprehensive introduction to optimization with a focus on practical algorithms. Mykel Kochenderfer and Tim Wheeler approach 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. Suitable for advanced undergraduates and graduate students in mathematics, statistics, computer science, engineering, and operations research and as a reference for professionals, the text provides concrete implementations in the Julia programming language.

Format PDF
Size 13.9 MB
(First 20 pages)

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

Page 1
(This page has no text content)
Page 2
(This page has no text content)
Page 3
Algorithms for Optimization
Page 4
(This page has no text content)
Page 5
Algorithms for Optimization second edition Mykel J. Kochenderfer Tim A. Wheeler The MIT Press Cambridge, Massachusetts London, England
Page 6
This work is licensed under a Creative Commons “Attribution-NonCommercial- NoDerivatives 4.0 International” license. © 2026 Massachusetts Institute of Technology Copyright in this monograph has been licensed exclusively to The MIT Press, http://mitpress.mit.edu. All inquiries regarding rights should be addressed to The MIT Press, Rights and Permissions Department. This book was set in TEX Gyre Pagella by the authors in LATEX.
Page 7
To our families.
Page 8
(This page has no text content)
Page 9
Contents Preface xv Acknowledgments xix 1 Introduction 1 1.1 A History 2 1.2 Optimization Process 4 1.3 Mathematical Formulation 5 1.4 Applications 7 1.5 Minima 10 1.6 Optimality Conditions 10 1.7 Overview 14 1.8 Summary 20 1.9 Exercises 20 2 Derivatives and Gradients 23 2.1 Derivatives 23 2.2 Derivatives in Multiple Dimensions 25 2.3 Numerical Differentiation 26 2.4 Automatic Differentiation 29 2.5 Regression Gradient 35 2.6 Simultaneous Perturbation Stochastic Gradient Approximation 37 2.7 Summary 38 2.8 Exercises 39
Page 10
viii contents 3 Bracketing 43 3.1 Unimodality 43 3.2 Finding an Initial Bracket 43 3.3 Fibonacci Search 45 3.4 Golden Section Search 47 3.5 Quadratic Fit Search 51 3.6 Shubert-Piyavskii Method 53 3.7 Bisection Method 57 3.8 Summary 59 3.9 Exercises 59 4 Local Descent 61 4.1 Descent Direction Iteration 61 4.2 Step Factors 62 4.3 Line Search 64 4.4 Approximate Line Search 65 4.5 Trust Region Methods 71 4.6 Termination Conditions 73 4.7 Summary 74 4.8 Exercises 74 5 First-Order Methods 77 5.1 Gradient Descent 77 5.2 Conjugate Gradient 79 5.3 Momentum 81 5.4 Nesterov Momentum 82 5.5 AdaGrad 82 5.6 RMSProp 84 5.7 Adadelta 84 5.8 Adam 86 5.9 Hypergradient Descent 86 5.10 Summary 89 5.11 Exercises 89 © 2026 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license. 2026-09-05 15:07:21-07:00, comments to bugs@algorithmsbook.com
Page 11
contents ix 6 Second-Order Methods 95 6.1 Newton’s Method 95 6.2 Secant Method 97 6.3 Levenberg-Marquardt Algorithm 100 6.4 Levenberg-Marquardt for Sum of Squares 102 6.5 Quasi-Newton Methods 103 6.6 Summary 106 6.7 Exercises 106 7 Direct Methods 113 7.1 Cyclic Coordinate Search 113 7.2 Powell’s Method 115 7.3 Hooke-Jeeves 116 7.4 Generalized Pattern Search 117 7.5 Nelder-Mead Simplex Method 119 7.6 Divided Rectangles 124 7.7 Summary 131 7.8 Exercises 131 8 Stochastic Methods 135 8.1 Noisy Descent 135 8.2 Mesh Adaptive Direct Search 136 8.3 Memory-Efficient Zeroth-Order Optimization 138 8.4 Simulated Annealing 140 8.5 Cross-Entropy Method 144 8.6 Proposal Distribution Descent 148 8.7 Information-Geometric Optimization 149 8.8 Covariance Matrix Adaptation 152 8.9 Summary 156 8.10 Exercises 156 9 Population Methods 163 9.1 Population Iteration 163 9.2 Genetic Algorithms 164 9.3 Differential Evolution 172 9.4 Particle Swarm Optimization 172 © 2026 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license. 2026-09-05 15:07:21-07:00, comments to bugs@algorithmsbook.com
Page 12
x contents 9.5 Firefly Algorithm 174 9.6 Cuckoo Search 177 9.7 Hybrid Methods 179 9.8 Summary 179 9.9 Exercises 181 10 Constraints 183 10.1 Constrained Optimization 183 10.2 Constraint Types 184 10.3 Transformations to Remove Constraints 185 10.4 Removing Affine Equality Constraints 187 10.5 Projected Iterative Methods 188 10.6 Lagrange Multipliers 189 10.7 Inequality Constraints 192 10.8 Slack Variables 195 10.9 Penalty Methods 195 10.10 Method of Multipliers 197 10.11 Interior Point Methods 199 10.12 Summary 201 10.13 Exercises 201 11 Duality 209 11.1 Dual Problem 209 11.2 Primal-Dual Methods 213 11.3 Dual Ascent 216 11.4 Alternating Direction Method of Multipliers 219 11.5 ADMM Applications 223 11.6 Distributed Methods 234 11.7 Summary 239 11.8 Exercises 239 12 Linear Programming 249 12.1 Problem Formulation 249 12.2 Simplex Algorithm 255 12.3 Dual Certificates 266 12.4 Summary 269 12.5 Exercises 269 © 2026 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license. 2026-09-05 15:07:21-07:00, comments to bugs@algorithmsbook.com
Page 13
contents xi 13 Quadratic Programming 273 13.1 Problem Formulation 273 13.2 Unconstrained Least-Squares Problems 274 13.3 Least Squares with Linear Inequalities 278 13.4 Least Distance Programming 281 13.5 Solving Nonnegative Least-Squares Problems 285 13.6 Dual Certificates 287 13.7 Summary 290 13.8 Exercises 291 14 Disciplined Convex Programming 297 14.1 Canonical Form 297 14.2 Verification 298 14.3 Canonicalization 307 14.4 Solving 314 14.5 Summary 317 14.6 Exercises 317 15 Multiobjective Optimization 325 15.1 Pareto Optimality 325 15.2 Constraint Methods 329 15.3 Weight Methods 331 15.4 Multiobjective Population Methods 334 15.5 Preference Elicitation 340 15.6 Summary 344 15.7 Exercises 344 16 Sampling Plans 349 16.1 Full Factorial 349 16.2 Random Sampling 350 16.3 Uniform Projection Plans 351 16.4 Stratified Sampling 352 16.5 Space-Filling Metrics 352 16.6 Space-Filling Subsets 356 16.7 Quasi-Random Sequences 359 16.8 Summary 361 16.9 Exercises 363 © 2026 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license. 2026-09-05 15:07:21-07:00, comments to bugs@algorithmsbook.com
Page 14
xii contents 17 Surrogate Models 365 17.1 Fitting Surrogate Models 365 17.2 Linear Models 366 17.3 Basis Functions 367 17.4 Fitting Noisy Objective Functions 372 17.5 Model Selection 375 17.6 Multifidelity Surrogate Models 383 17.7 Summary 384 17.8 Exercises 385 18 Probabilistic Surrogate Models 389 18.1 Gaussian Distribution 389 18.2 Gaussian Processes 391 18.3 Prediction 394 18.4 Gradient Measurements 396 18.5 Noisy Measurements 399 18.6 Fitting Gaussian Processes 401 18.7 Summary 401 18.8 Exercises 402 19 Surrogate Optimization 411 19.1 Prediction-Based Exploration 411 19.2 Error-Based Exploration 412 19.3 Lower Confidence Bound Exploration 413 19.4 Probability of Improvement Exploration 413 19.5 Expected Improvement Exploration 414 19.6 Safe Optimization 416 19.7 Summary 424 19.8 Exercises 424 20 Optimization Under Uncertainty 427 20.1 Uncertainty 427 20.2 Set-Based Uncertainty 429 20.3 Probabilistic Uncertainty 432 20.4 Summary 439 20.5 Exercises 439 © 2026 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license. 2026-09-05 15:07:21-07:00, comments to bugs@algorithmsbook.com
Page 15
contents xiii 21 Uncertainty Propagation 443 21.1 Sampling Methods 443 21.2 Taylor Approximation 444 21.3 Polynomial Chaos 445 21.4 Bayesian Monte Carlo 455 21.5 Summary 457 21.6 Exercises 457 22 Discrete Optimization 463 22.1 Integer Programs 464 22.2 Rounding 465 22.3 Cutting Planes 466 22.4 Branch and Bound 471 22.5 Dynamic Programming 474 22.6 Ant Colony Optimization 477 22.7 Summary 481 22.8 Exercises 481 23 Expression Optimization 489 23.1 Grammars 489 23.2 Genetic Programming 493 23.3 Grammatical Evolution 497 23.4 Probabilistic Grammars 501 23.5 Probabilistic Prototype Trees 502 23.6 Summary 509 23.7 Exercises 510 24 Multidisciplinary Optimization 515 24.1 Disciplinary Analyses 515 24.2 Interdisciplinary Compatibility 517 24.3 Architectures 521 24.4 Multidisciplinary Design Feasible 521 24.5 Sequential Optimization 524 24.6 Individual Discipline Feasible 526 24.7 Collaborative Optimization 531 24.8 Simultaneous Analysis and Design 534 24.9 Summary 535 24.10 Exercises 536 © 2026 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license. 2026-09-05 15:07:21-07:00, comments to bugs@algorithmsbook.com
Page 16
xiv contents appendices A Julia 541 A.1 Types 541 A.2 Functions 555 A.3 Control Flow 558 A.4 Packages 560 B Test Functions 561 B.1 Ackley’s Function 561 B.2 Booth’s Function 561 B.3 Branin Function 564 B.4 Flower Function 565 B.5 Michalewicz Function 566 B.6 Rosenbrock’s Banana Function 567 B.7 Wheeler’s Ridge 568 B.8 Circle Function 569 C Mathematical Concepts 571 C.1 Asymptotic Notation 571 C.2 Taylor Expansion 573 C.3 Convexity 574 C.4 Norms 577 C.5 Generalized Gradient 577 C.6 Matrix Calculus 579 C.7 Positive Definiteness 582 C.8 Matrix Decompositions 582 C.9 Gaussian Distribution 586 C.10 Gaussian Quadrature 586 References 591 Index 607 © 2026 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license. 2026-09-05 15:07:21-07:00, comments to bugs@algorithmsbook.com
Page 17
Preface This book provides a broad introduction to optimization with a focus on practical algorithms for the design of engineering systems. We cover a wide variety of optimization topics, introducing the underlying mathematical problem formula- tions and the algorithms for solving them. Figures, examples, and exercises are provided to convey the intuition behind the various approaches. This text is intended for advanced undergraduates and graduate students as well as professionals. The book requires some mathematical maturity and assumes prior exposure to multivariable calculus, linear algebra, and probability concepts. Some review material is provided in the appendix. Disciplines where the book would be especially useful include mathematics, statistics, computer science, aerospace, electrical engineering, and operations research. Although we will occasionally refer to particular applications as examples, the focus is on general algorithms and their properties rather than the details of specific application domains. Fundamental to this book are the algorithms, which are all implemented in the Julia programming language. We have found the language to be ideal for specifying algorithms in human readable form. Permission is granted, free of charge, to use the code snippets associated with this book, subject to the condition that the source of the code is acknowledged. We anticipate that others may want to contribute translations of these algorithms to other programming languages. As translations become available, we will link to them from the book’s webpage. The implementations of the algorithms in this book are intended to convey the essential ideas behind each approach. These implementations are not intended to be production quality, but rather to be clear and concise. There are many optimization software packages, both commercial and open source, that provide much more robust implementations. We reference many of these packages in the
Page 18
xvi preface text, andwe encourage readers to explore these packages for practical applications. In some situations, especially for problems that do not lend themselves to general- purpose solvers, the Julia code in this book may be useful starting points for custom implementations. We intentionally wanted to optimize for breadth rather than depth—unifying ideas in optimization that span many different communities that have emerged from diverse disciplines ranging from operations research to aerospace design. There are many excellent optimization books published over the past fifty years that go deep into particular areas, such as convex optimization, discrete optimiza- tion, and linear programming. Instead of attempting to reproduce their theoretical analyses, we reference them in the wide margins. New in this second edition are three chapters on duality, quadratic programming, and disciplined convex programming. The first new chapter covers the principles of duality and several of the core optimization algorithms that leverage its the- ory, including primal-dual methods, dual ascent, and the alternating direction method of multipliers. The previous edition had sections that mentioned duality, but dedicating a chapter to it allows for more focus on its theory and primal-dual algorithms. We are particularly excited to cover the alternating direction method of multipliers, an approach that has been the subject of recent theoretical and practical advances. This algorithm is generally applicable to constrained opti- mization and can be robustly scaled to extremely large problems. We apply the alternating direction method of multipliers to a broad range of problems that generalize under its umbrella, including alternating projections, least absolute deviation, and basis pursuit. The second new chapter covers quadratic programming. It mirrors our existing chapter on linear-constrained optimization, now renamed ‘‘Linear Programming’’. Linear programming refers to solving a very general class of linear-constrained op- timization problems with linear objectives. Quadratic programming is also a very general class of linear-constrained optimization problems, but with quadratic ob- jectives. This new chapter covers a series of algorithmic problem decompositions that successively transform a general quadratic program into a form amenable to efficient solution by iterative algorithms. The third new chapter focuses on disciplined convex programming. Disciplined convex programming allows problems to be expressed in a natural manner, but allows for algorithms to verify problem convexity and reformulate input problems into a general structure amenable to efficient solution by a wide variety of solvers. © 2026 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license. 2026-09-05 15:07:21-07:00, comments to bugs@algorithmsbook.com
Page 19
preface xvii Disciplined convex programming is a workhorse of modern convex optimization. This chapter covers the theory and algorithms to allow the reader to be better equipped to effectively use disciplined convex solvers, verify convexity, and exploit problem structure to efficiently solve large problems. In addition to these new chapters, we have added additional methods, ranging from new ways to estimate gradients to multifidelity techniques. Based on feed- back from multiple iterations of the course, we improved the clarity of the text to make the topics more accessible, expanded explanations, updated references, and streamlined the algorithms. There are now additional exercises, example applications, and figures. Mykel J . Kochenderfer Tim A. Wheeler Stanford, Calif. May 24, 2026 Ancillary material is available on the book’s webpage: http://mitpress.mit.edu/algorithms-for-optimization © 2026 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license. 2026-09-05 15:07:21-07:00, comments to bugs@algorithmsbook.com
Page 20
(This page has no text content)
The above is a preview of the first 20 pages. Register to read the complete e-book.

Recommended for You

Loading recommended books...
Failed to load, please try again later

Tip the Site

Scan the WeChat Pay or Alipay code to tip. No login required.

WeChat Pay
Alipay
← Back to List