優化理論與實用演算法（簡體書）

米凱爾·J. 科申德弗（Mykel J. Kochenderfer） 斯坦福大學航空航天系和計算機科學系副教授，也是該校智能系統實驗室（SISL）主任，研究用於設計穩健決策系統的先進算法和分析方法。

蒂姆·A. 惠勒（Tim A. Wheeler） 斯坦福大學航空航天系博士，現為舊金山灣區的軟件工程師，從事自動駕駛、控制和決策系統方面的研發工作。

本書全面介紹優化技術，重點關注工程系統設計中的實用算法。書中涵蓋豐富多彩的優化主題，介紹基本的數學公式以及解決數學問題的算法，並提供了圖形、示例和習題來深入解析各種優化方法。
閱讀本書需要有一定的數學基礎，並了解多元微積分、線性代數和概率概念，附錄C中提供了一些復習材料。本書適合高等院校數學、統計學、計算機科學、航空航天、電氣工程、運籌學專業的本科生和研究生閱讀，也適合作為相關技術人員的參考書。
本書的基礎是算法，所有算法均以Julia編程語言實現。Julia語言是以人類可讀的形式詳細說明算法的理想語言。在注明代碼來源的前提下，允許讀者免費使用與本書相關的代碼段。希望讀者可以用其他編程語言實現書中的算法，我們會在本書網頁上給出鏈接。

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