Algorithms for Optimization

出版者:The MIT Press

作者:Mykel J. Kochenderfer

页数:520

出版时间:2019-3-12

价格:USD 85.00

isbn号码:9780262039420

具体描述

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.

目录信息

Contents
Preface
Acknowledgments
1 Introduction
1.1 A History
1.2 Optimization Process
1.3 Basic Optimization Problem
1.4 Constraints
1.5 Critical Points
1.6 Conditions for Local Minima
1.7 Contour Plots
1.8 Overview
1.9 Summary
1.10 Exercises
2 Derivatives and Gradients
2.1 Derivatives
2.2 Derivatives in Multiple Dimensions
2.3 Numerical Differentiation
2.4 Automatic Differentiation
2.5 Summary
2.6 Exercises
3 Bracketing
3.1 Unimodality
3.2 Finding an Initial Bracket
3.3 Fibonacci Search
3.4 Golden Section Search
3.5 Quadratic Fit Search
3.6 Shubert-Piyavskii Method
3.7 Bisection Method
3.8 Summary
3.9 Exercises
4 Local Descent
4.1 Descent Direction Iteration
4.2 Line Search
4.3 Approximate Line Search
4.4 Trust Region Methods
4.5 Termination Conditions
4.6 Summary
4.7 Exercises
5 First-Order Methods
5.1 Gradient Descent
5.2 Conjugate Gradient
5.3 Momentum
5.4 Nesterov Momentum
5.5 Adagrad
5.6 RMSProp
5.7 Adadelta
5.8 Adam
5.9 Hypergradient Descent
5.10 Summary
5.11 Exercises
6 Second-Order Methods
6.1 Newton’s Method
6.2 Secant Method
6.3 Quasi-Newton Methods
6.4 Summary
6.5 Exercises
7 Direct Methods
7.1 Cyclic Coordinate Search
7.2 Powell’s Method
7.3 Hooke-Jeeves
7.4 Generalized Pattern Search
7.5 Nelder-Mead Simplex Method
7.6 Divided Rectangles
7.7 Summary
7.8 Exercises
8 Stochastic Methods
8.1 Noisy Descent
8.2 Mesh Adaptive Direct Search
8.3 Simulated Annealing
8.4 Cross-Entropy Method
8.5 Natural Evolution Strategies
8.6 Covariance Matrix Adaptation
8.7 Summary
8.8 Exercises
9 Population Methods
9.1 Initialization
9.2 Genetic Algorithms
9.3 Differential Evolution
9.4 Particle Swarm Optimization
9.5 Firefly Algorithm
9.6 Cuckoo Search
9.7 Hybrid Methods
9.8 Summary
9.9 Exercises
10 Constraints
10.1 Constrained Optimization
10.2 Constraint Types
10.3 Transformations to Remove Constraints
10.4 Lagrange Multipliers
10.5 Inequality Constraints
10.6 Duality
10.7 Penalty Methods
10.8 Augmented Lagrange Method
10.9 Interior Point Methods
10.10 Summary
10.11 Exercises
11 Linear Constrained Optimization
11.1 Problem Formulation
11.2 Simplex Algorithm
11.3 Dual Certificates
11.4 Summary
11.5 Exercises
12 Multiobjective Optimization
12.1 Pareto Optimality
12.2 Constraint Methods
12.3 Weight Methods
12.4 Multiobjective Population Methods
12.5 Preference Elicitation
12.6 Summary
12.7 Exercises
13 Sampling Plans
13.1 Full Factorial
13.2 Random Sampling
13.3 Uniform Projection Plans
13.4 Stratified Sampling
13.5 Space-Filling Metrics
13.6 Space-Filling Subsets
13.7 Quasi-Random Sequences
13.8 Summary
13.9 Exercises
14 Surrogate Models
14.1 Fitting Surrogate Models
14.2 Linear Models
14.3 Basis Functions
14.4 Fitting Noisy Objective Functions
14.5 Model Selection
14.6 Summary
14.7 Exercises
15 Probabilistic Surrogate Models
15.1 Gaussian Distribution
15.2 Gaussian Processes
15.3 Prediction
15.4 Gradient Measurements
15.5 Noisy Measurements
15.6 Fitting Gaussian Processes
15.7 Summary
15.8 Exercises
16 Surrogate Optimization
16.1 Prediction-Based Exploration
16.2 Error-Based Exploration
16.3 Lower Confidence Bound Exploration
16.4 Probability of Improvement Exploration
16.5 Expected Improvement Exploration
16.6 Safe Optimization
16.7 Summary
16.8 Exercises
17 Optimization under Uncertainty
17.1 Uncertainty
17.2 Set-Based Uncertainty
17.3 Probabilistic Uncertainty
17.4 Summary
17.5 Exercises
18 Uncertainty Propagation
18.1 Sampling Methods
18.2 Taylor Approximation
18.3 Polynomial Chaos
18.4 Bayesian Monte Carlo
18.5 Summary
18.6 Exercises
19 Discrete Optimization
19.1 Integer Programs
19.2 Rounding
19.3 Cutting Planes
19.4 Branch and Bound
19.5 Dynamic Programming
19.6 Ant Colony Optimization
19.7 Summary
19.8 Exercises
20 Expression Optimization
20.1 Grammars
20.2 Genetic Programming
20.3 Grammatical Evolution
20.4 Probabilistic Grammars
20.5 Probabilistic Prototype Trees
20.6 Summary
20.7 Exercises
21 Multidisciplinary Optimization
21.1 Disciplinary Analyses
21.2 Interdisciplinary Compatibility
21.3 Architectures
21.4 Multidisciplinary Design Feasible
21.5 Sequential Optimization
21.6 Individual Discipline Feasible
21.7 Collaborative Optimization
21.8 Simultaneous Analysis and Design
21.9 Summary
21.10 Exercises
A Julia
A.1 Types
A.2 Functions
A.3 Control Flow
A.4 Packages
B Test Functions
B.1 Ackley’s Function
B.2 Booth’s Function
B.3 Branin Function
B.4 Flower Function
B.5 Michalewicz Function
B.6 Rosenbrock’s Banana Function
B.7 Wheeler’s Ridge
B.8 Circle Function
C Mathematical Concepts
C.1 Asymptotic Notation
C.2 Taylor Expansion
C.3 Convexity
C.4 Norms
C.5 Matrix Calculus
C.6 Positive Definiteness
C.7 Gaussian Distribution
C.8 Gaussian Quadrature
D Solutions
Bibliography
Index
· · · · · · (收起)

用户评价

这本书的排版和装帧质量着实令人称道，拿在手上有一种踏实的分量感。纸张的质地很适中，既不会反光得让人眼花缭乱，也不会因为过于粗糙而影响阅读体验。但真正让我感到惊喜的是它对案例分析的详尽程度。我一直觉得，优化理论如果脱离了实际场景，就容易变成空中楼阁，而这本书显然深谙此道。它穿插了许多来自不同领域的实际问题，比如资源分配、路径规划，甚至还有一些涉及机器学习模型训练的例子。更棒的是，每一个案例都不是简单地抛出一个问题，而是细致入微地拆解了如何将现实问题抽象成数学模型，然后应用书中所讲的特定算法进行求解。作者在讲解过程中，常常会加入一些“陷阱”提示，指出初学者容易在哪里犯错，或者在特定条件下应该选择哪种变体算法。这种“过来人”的经验分享，对于我这种需要快速上手应用的人来说，价值连城。我甚至发现，书中有几个小节的讲解方式，和我在某个顶级期刊上读到的某篇论文的处理思路惊人地相似，这让我对这本书的权威性深信不疑。

坦白讲，这本书的阅读过程并非一帆风顺，它对读者的预备知识有着相当高的要求。如果你对线性代数和微积分只有停留在基础层面的了解，那么在读到前三分之一的时候，很可能会感到吃力。不过，作者似乎预料到了这一点，在每章的开篇，都会有一个“预备知识回顾”的小节，用精炼的语言快速梳理了必要的背景知识。这种处理方式非常高明，它既照顾了那些记忆有些模糊的读者，又不会因为冗长的基础回顾而拖慢整体的节奏。我最欣赏它在算法描述上的那种“务实”精神。它不仅仅停留在理论层面，而是非常关注算法的计算复杂度、内存需求，以及在实际计算机上实现的技巧。比如，在介绍动态规划时，作者没有仅仅停留在递归关系上，而是深入探讨了备忘录化（memoization）和自底向上（bottom-up）实现之间的性能差异，并给出了具体的伪代码。这让我感觉，这本书与其说是一本学术专著，不如说是一本面向“高级工程师”的实践指南，它教会你如何写出高效且健壮的优化求解器。

这本书的封面设计给我一种沉稳而略带神秘的感觉，深蓝色的主色调配上银色的字体，仿佛在暗示着其中蕴含的复杂与深度。初次翻开，我立刻被它清晰的章节结构所吸引，作者似乎非常注重逻辑的递进，从基础的概念讲解到高级算法的推导，每一步都像是精心铺设的阶梯，引导读者稳步攀登。我尤其欣赏它在理论阐述上的严谨性，大量的数学公式被清晰地呈现，但更难能可贵的是，作者总能在公式之后用非常直观的语言来解释其背后的几何意义或实际操作的含义。这对于我们这些希望将理论知识与工程实践相结合的读者来说，简直是福音。例如，在讨论某个迭代算法的收敛性时，书中不仅给出了严格的证明，还配有一张非常巧妙的图示，清晰地展示了搜索路径是如何逐步逼近最优解的。这种教学方法的结合，极大地降低了理解难度，让原本枯燥的数学推导变得生动起来。我用了好几个晚上才啃完关于拉格朗日乘子法的那一章，但收获是巨大的，感觉自己对约束优化问题的理解达到了一个新的高度。

这本书的语言风格非常独特，它介于严谨的教科书和富有激情的个人论述之间，给人一种仿佛是与一位经验丰富的导师进行一对一交流的感觉。作者在阐述复杂概念时，常常会引用一些历史典故或者某个算法发明背后的故事，这使得原本枯燥的数学发展史变得引人入胜。例如，在讲解某个经典优化算法的诞生时，书中穿插了一段关于当时计算能力的限制的描述，这让读者能深刻理解为什么当初的数学家会选择那种特定的迭代方式。此外，全书的参考书目部分做得极其详尽和有条理，每一条引用后面都附有简短的评论，指明了该文献对本章内容的具体贡献。这对于希望进行更深层次研究的读者来说，无疑是一张宝贵的地图。我已经把这本书列为我书架上必备的工具书，时不时地翻阅一下，总能从中发现一些之前忽略的细节或者获得新的启发。它不仅仅教会了我如何“做”优化，更重要的是，它教会了我如何“思考”优化问题。

这本书的深度和广度都让人印象深刻。它似乎涵盖了主流优化理论的几乎所有重要分支，从无约束优化到复杂的混合整数规划，中间穿插着启发式算法和元启发式方法。但最让我拍案叫绝的，是它处理“不精确”或“近似”优化方法的态度。很多教材往往把重点放在保证全局最优解的方法上，而这本书却用相当大的篇幅讨论了在计算资源受限或问题本质上就是NP难的情况下，如何设计出高质量的启发式算法。作者将蒙特卡洛方法、模拟退火、遗传算法等不同思想的算法放在一起进行对比分析，不仅展示了它们各自的优势，更关键的是，剖析了它们背后的数学直觉和适用范围的边界。这种平衡的视角，使得读者不会陷入对“完美解”的盲目追求中，而是学会根据实际约束条件，权衡求解速度和解的质量。我个人对于其中关于敏感性分析的那一章尤其着迷，它揭示了优化模型参数微小变化对最终决策可能带来的巨大影响，这在商业决策中是至关重要的洞察。

作为一本儿本科生的intro级别的书还凑合。代码质量堪忧。

作为一本儿本科生的intro级别的书还凑合。代码质量堪忧。

作为一本儿本科生的intro级别的书还凑合。代码质量堪忧。

作为一本儿本科生的intro级别的书还凑合。代码质量堪忧。

作为一本儿本科生的intro级别的书还凑合。代码质量堪忧。