优化理论与实用算法

本书全面介绍优化理论，重点介绍设计工程系统的实用算法。

米凯尔·J. 科申德弗（Mykel J. Kochenderfer） 斯坦福大学航空航天系和计算机科学系副教授，也是该校智能系统实验室（SISL）主任，研究用于设计稳健决策系统的先进算法和分析方法。

蒂姆·A. 惠勒（Tim A. Wheeler） 斯坦福大学航空航天系博士，现为旧金山湾区的软件工程师，从事自动驾驶、控制和决策系统方面的研发工作。

本书全面介绍优化技术，重点关注工程系统设计中的实用算法。书中涵盖丰富多彩的优化主题，介绍基本的数学公式以及解决数学问题的算法，并提供了图形、示例和习题来深入解析各种优化方法。
阅读本书需要有一定的数学基础，并了解多元微积分、线性代数和概率概念，附录C中提供了一些复习材料。本书适合高等院校数学、统计学、计算机科学、航空航天、电气工程、运筹学专业的本科生和研究生阅读，也适合作为相关技术人员的参考书。
本书的基础是算法，所有算法均以Julia编程语言实现。Julia语言是以人类可读的形式详细说明算法的理想语言。在注明代码来源的前提下，允许读者免费使用与本书相关的代码段。希望读者可以用其他编程语言实现书中的算法，我们会在本书网页（http://mitpress.mit.edu/algorithmsforoptimization）上给出链接。

Mykel J.Kochenderfer
Tim A.Wheeler
2018年10月30日于加州斯坦福

译者序

前言

致谢

第1章引言1

1.1优化算法的历史1

1.2优化过程3

1.3基本优化问题3

1.4约束4

1.5极值点5

1.6局部极小值的条件6

1.6.1一元问题6

1.6.2多元问题7

1.7等高线图8

1.8概述8

1.9小结11

1.10练习11

第2章导数和梯度12

2.1导数12

2.2多维导数13

2.3数值微分14

2.3.1有限差分法15

2.3.2复数步长法16

2.4自动微分17

2.4.1前向累积18

2.4.2反向累积20

2.5小结20

2.6练习20

第3章包围22

3.1单模态22

3.2确定初始包围22

3.3斐波那契搜索23

3.4黄金分割搜索25

3.5二次拟合搜索26

3.6ShubertPiyavskii方法28

3.7二分法30

3.8小结32

3.9练习32

第4章局部下降33

4.1下降方向迭代33

4.2线搜索33

4.3近似线搜索34

4.4信赖域方法39

4.5终止条件42

4.6小结42

4.7练习42

第5章一阶方法43

5.1梯度下降43

5.2共轭梯度44

5.3动量46

5.4Nesterov动量47

5.5Adagrad方法48

5.6RMSProp49

5.7Adadelta50

5.8Adam50

5.9超梯度下降51

5.10小结53

5.11练习53

第6章二阶方法54

6.1牛顿法54

6.2割线法57

6.3拟牛顿法57

6.4小结60

6.5练习60

第7章直接方法63

7.1循环坐标搜索63

7.2鲍威尔搜索法64

7.3胡可-吉夫斯搜索法65

7.4广义模式搜索法66

7.5尼尔德-米德单纯形法68

7.6分割矩形法71

7.6.1单变量DIRECT72

7.6.2多变量DIRECT74

7.6.3实施74

7.7小结78

7.8练习79

第8章随机方法80

8.1噪声下降80

8.2网格自适应直接搜索81

8.3模拟退火83

8.4交叉熵法87

8.5自然进化策略89

8.6自适应协方差矩阵90

8.7小结93

8.8练习94

第9章种群方法96

9.1初始化96

9.2遗传算法97

9.2.1染色体98

9.2.2初始化98

9.2.3选择98

9.2.4交叉100

9.2.5变异101

9.3微分进化102

9.4粒子群优化104

9.5萤火虫算法105

9.6布谷鸟搜索106

9.7混合方法108

9.8小结109

9.9练习109

第10章约束110

10.1约束优化110

10.2约束类型111

10.3消除约束的转换111

10.4拉格朗日乘数法113

10.5不等式约束115

10.6对偶性117

10.7惩罚方法119

10.8增广拉格朗日法121

10.9内点法122

10.10小结123

10.11练习123

第11章线性约束优化125

11.1问题表述125

11.1.1一般形式126

11.1.2标准形式126

11.1.3等式形式127

11.2单纯形算法129

11.2.1顶点129

11.2.2一阶必要条件132

11.2.3优化阶段133

11.2.4初始化阶段136

11.3对偶验证138

11.4小结139

11.5练习139

第12章多目标优化140

12.1帕累托最优140

12.1.1优势位置140

12.1.2帕累托边界141

12.1.3帕累托边界生成142

12.2约束方法143

12.2.1目标约束法143

12.2.2词典约束法143

12.3权重法143

12.3.1加权和法144

12.3.2目标编程144

12.3.3加权指数和145

12.3.4加权最小-最大值法145

12.3.5指数加权准则146

12.4多目标种群方法146

12.4.1子种群146

12.4.2非支配排名147

12.4.3帕累托过滤器148

12.4.4生态位技术149

12.5偏好诱导150

12.5.1模型识别150

12.5.2配对查询选择151

12.5.3设计选择151

12.6小结152

12.7练习152

第13章抽样计划154

13.1全因子154

13.2随机抽样155

13.3均匀投影计划155

13.4分层抽样156

13.5空间填充指标156

13.5.1差异157

13.5.2成对距离157

13.5.3MorrisMitchell标准158

13.6空间填充子集159

13.7准随机序列161

13.7.1加性递归162

13.7.2哈尔顿序列163

13.7.3Sobol序列164

13.8小结165

13.9习题165

第14章代理模型166

14.1拟合代理模型166

14.2线性模型166

14.3基函数168

14.3.1多项式基函数169

14.3.2正弦基函数170

14.3.3径向基函数171

14.4拟合噪声目标函数172

14.5模型选择173

14.5.1保留法175

14.5.2交叉验证176

14.5.3自举法178

14.6小结180

14.7练习180

第15章概率代理模型181

15.1高斯分布181

15.2高斯过程182

15.3预测185

15.4梯度测量186

15.5噪声测量188

15.6拟合高斯过程189

15.7小结189

15.8练习190

第16章代理优化191

16.1基于预测的探索191

16.2基于误差的探索191

16.3置信下界的探索192

16.4改进探索的概率192

16.5预期改进探索194

16.6安全优化194

16.7小结199

16.8练习199

第17章不确定性下的优化200

17.1不确定性200

17.2基于集合的不确定性201

17.2.1极小极大方法201

17.2.2信息差距决策理论203

17.3概率不确定性204

17.3.1期望值204

17.3.2方差204

17.3.3统计可行性205

17.3.4风险价值206

17.3.5条件风险价值206

17.4小结207

17.5练习207

第18章不确定性传播209

18.1抽样方法209

18.2泰勒逼近209

18.3多项式混沌211

18.3.1一元情况211

18.3.2系数216

18.3.3多元情况217

18.4贝叶斯蒙特卡罗217

18.5小结220

18.6练习220

第19章离散优化221

19.1整数规划221

19.2四舍五入222

19.3切割平面224

19.4分支限界法227

19.5动态规划229

19.6蚁群优化231

19.7小结234

19.8练习234

第20章表达式优化236

20.1语法236

20.2遗传编程238

20.3语法进化241

20.4概率语法245

20.5概率原型树246

20.6小结250

20.7练习251

第21章 多学科设计优化253

21.1 学科分析253

21.2 跨学科兼容性254

21.3 架构257

21.4 多学科设计可行性258

21.5 顺序优化259

21.6 单学科可行性260

21.7 协同优化262

21.8 同步分析和设计264

21.9 小结266

21.10 练习266

附录A Julia267

附录B 测试函数277

附录C 数学概念282

附录D 练习参考答案292

参考文献315

索引 324