●《運籌與管理科學叢書》序
前言
符號說明
第1章 緒論 1
1.1 很優化問題的基本概念 1
1.2 確定性全局優化方法的基本思想及研究現狀 4
1.3 本書的研究內容 17
第2章 分支定界算法基礎 21
2.1 分支定界算法的基本框架 21
2.2 分支方法 23
2.2.1 矩形剖分方法 23
2.2.2 單純形剖分 23
2.2.3 錐形剖分 24
2.3 上、下界函數構造方法 24
2.3.1 利用區間擴張構造0階上、下界函數 25
2.3.2 利用一階微分中值定理構造線性上、下界函數 26
2.4 利用分解技術構造擬凸函數的上、下界 27
2.5 利用雙線性函數或單分式函數的凸、凹包構造上、下界 28
2.5.1 雙線性函數凸包絡和凹包絡的構造 30
2.5.2 比式函數凸包絡和凹包絡的構造 31
第3章 二次規劃問題的分支定界算法 34
3.1 二次規劃問題的單純形分支定界算法 34
3.1.1 單純形分支定界算法 34
3.1.2 上、下界的構造 35
3.1.3 算法及其收斂性 36
3.2 二次規劃問題的參數線性松弛算法 37
3.2.1 參數線性化技巧 37
3.2.2 算法及其收斂性 41
3.2.3 數值實驗 48
3.3 本章小結 50
第4章 線性多乘積規劃問題的分支定界算法 51
4.1 問題描述 51
4.2 第一種分支定界算法 51
4.2.1 等價轉換及其線性松弛 52
4.2.2 刪除規則 56
4.2.3 算法及其收斂性 59
4.3 第二種分支定界算法 66
4.3.1 縮減技巧 68
4.3.2 算法框架結構 69
4.3.3 算法描述 69
4.3.4 收斂性分析 70
4.3.5 數值實驗 71
4.4 本章小結 73
第5章 廣義線性多乘積規劃問題的單純形分支定界算法 74
5.1 基本操作 74
5.1.1 單純形對分規則 75
5.1.2 下界估計 75
5.1.3 上界估計 78
5.2 算法及其收斂性 78
5.3 數值實驗 80
5.4 本章小結 82
第6章 廣義幾何規劃問題的分支定界算法 83
6.1 分支定界加速算法 83
6.1.1 問題描述 83
6.1.2 線性化方法 83
6.1.3 刪除技術 85
6.1.4 算法及其收斂性 89
6.1.5 數值實驗 93
6.2 兩階段松弛方法 94
6.2.1 問題描述 94
6.2.2 線性松弛問題的產生 94
6.2.3 縮減技巧 99
6.2.4 算法及其收斂性 102
6.2.5 數值實驗 104
6.3 本章小結 106
第7章 廣義線性比式和問題的分支定界算法 107
7.1 線性化方法 107
7.1.1 問題描述 107
7.1.2 問題的線性松弛 108
7.1.3 區域縮減技巧 113
7.1.4 算法及其收斂性 115
7.1.5 數值實驗 118
7.2 外空間分支定界加速算法 119
7.2.1 線性松弛規劃 120
7.2.2 輸出空間加速方法 126
7.2.3 算法及其收斂性 128
7.2.4 數值實驗 132
7.3 梯形分支定界算法 135
7.3.1 預備知識 136
7.3.2 加速技術 142
7.3.3 界緊技術 143
7.3.4 算法及其收斂性 146
7.3.5 數值結果 151
7.4 本章小結 151
第8章 二次約束二次比式和問題的分支縮減定界算法 152
8.1 問題描述 152
8.2 新的線性松弛方法 153
8.3 分支縮減定界算法及收斂性 160
8.3.1 區域分裂方法 161
8.3.2 區域縮減方法 161
8.3.3 分支縮減定界算法 163
8.3.4 算法及其收斂性 164
8.4 數值實驗 165
8.5 本章小結 168
……