最優化理論與方法

最優化理論與方法是電腦科學與技術、人工智能及相關專業的主乾課程之一。本書結合最優化理論與方法的基本原理和各種高效算法的實際應用，系統地介紹了最優化問題的數學建模方法，並融入了和最優化理論與方法課程密切相關的思政元素。 全書共9章，第1章為引言，第2～9章全面系統地介紹了相關數學知識、線性規劃、單純形方法、對偶理論和靈敏度分析、一維搜索、使用導數的最優化方法、懲罰函數法、動態規劃法，同時部分章末引入了思政擴展閱讀內容。 本書提供了較為豐富的實例、案例分析和幾何演示，可以作為電腦科學與技術、人工智能、數學和運籌學等相關專業高年級本科生與研究生的教材，也可以作為從事該領域研究的工程技術人員的學習參考書。

第1章 引言 1
1.1 概述 1
1.2 線性規劃與非線性規劃問題 2
第2章 相關數學知識 6
2.1 向量與矩陣 6
2.1.1 基本定義 6
2.1.2 矩陣的秩 6
2.1.3 線性方程組 7
2.1.4 內積和範數 8
2.2 凸集與凸函數 10
2.2.1 凸集 10
2.2.2 凸集分離定理 11
2.2.3 凸函數 13
2.2.4 凸函數的判別 13
2.2.5 凸規劃 14
2.3 微積分基礎 15
2.3.1 序列與極限 15
2.3.2 可微性 16
2.3.3 導數矩陣 17
2.3.4 微分法則 19
2.3.5 水平集與梯度 19
2.3.6 泰勒級數 21
習題 22
第3章 線性規劃 25
3.1 線性規劃問題的標準形式 25
3.2 兩變量線性規劃問題的圖解法 28
3.3 線性規劃的基本概念與性質 31
3.3.1 線性規劃的基本概念 31
3.3.2 線性規劃的基本性質 35
3.4 用LINGO軟件求解線性規劃問題 35
3.5 用MATLAB求解線性規劃問題 36
習題 37
第4章 單純形方法 39
4.1 單純形方法的原理 39
4.1.1 單純形方法的基本思想 39
4.1.2 最優性條件 39
4.1.3 基本可行解的轉換 41
4.1.4 單純形方法的計算步驟 43
4.1.5 收斂性分析 46
4.2 使用表格形式的單純形方法 46
4.3 案例分析和代碼實現 51
習題 54
第5章 對偶理論和靈敏度分析 55
5.1 線性規劃中的對偶理論 55
5.1.1 對偶問題的提出 55
5.1.2 對偶問題的定義 56
5.1.3 對偶定理 60
5.1.4 對偶問題的經濟含義——影子價格 62
5.2 對偶單純形方法 63
5.2.1 對偶單純形方法的基本思想 63
5.2.2 計算步驟 65
5.2.3 對偶單純形方法的MATLAB實現 67
5.3 靈敏度分析 69
5.3.1 改變系數向量c 69
5.3.2 改變右端向量b 71
5.3.3 改變約束矩陣A 73
5.3.4 增加新的約束條件 74
習題 77
第6章 一維搜索 78
6.1 一維搜索概述 78
6.1.1 基本概念 78
6.1.2 一維搜索算法的閉性 78
6.2 試探法 79
6.2.1 0.618試探法 79
6.2.2 Fibonacci試探法 81
6.2.3 0.618試探法和Fibonacci試探法的關系 84
6.3 案例分析 85
習題 92
第7章 使用導數的最優化方法 93
7.1 最速下降法 93
7.1.1 最速下降方向 93
7.1.2 最速下降法的迭代算法 94
7.1.3 最速下降法的收斂性 95
7.2 牛頓法 96
7.2.1 牛頓法的迭代算法 96
7.2.2 阻尼牛頓法 99
7.2.3 牛頓法的進一步修正 100
7.3 共軛梯度法 101
7.3.1 共軛方向 101
7.3.2 FR共軛梯度法 102
7.3.3 用於一般函數的共軛梯度法 105
7.3.4 PRP共軛梯度法的收斂性 107
習題 110
第8章 懲罰函數法 112
8.1 外點懲罰函數法 112
8.1.1 外點懲罰函數的基本思想 112
8.1.2 外點懲罰函數法的計算步驟 113
8.1.3 外點懲罰函數法的收斂性 114
8.2 內點懲罰函數法 116
8.2.1 內點懲罰函數法的基本思想 116
8.2.2 內點懲罰函數法的計算步驟 117
8.2.3 內點懲罰函數法的收斂性 117
8.2.4 案例分析 119
習題 121
第9章 動態規劃法 123
9.1 動態規劃的基本概念 123
9.1.1 動態規劃的實例與定義 123
9.1.2 形式化術語 123
9.2 逆推解法及案例分析 125
9.2.1 逆推解法介紹 125
9.2.2 逆推解法案例分析 125
9.3 順推解法及案例分析 128
9.3.1 順推解法介紹 128
9.3.2 順推解法案例分析 128
參考文獻 133