全局优化问题一直是最优化领域的老大难问题,备受关注。本书首先介绍了非凸全局优化问题的研究进展,然后从分支方法、定界理论、算法设计及相关技术等方面详细论述了非凸全局优化问题的分支定界算法。全书主要内容如下:全局优化方法的研究现状,分支定界算法的理论基础、分支方法、定界技巧及相关概念,二次规划、线性多乘积规划、广义线性多乘积规划、广义几何规划、广义线性比式和、二次约束二次比式和、广义多项式比式和、一般非线性比式和等问题的分支定界算法。
样章试读
目录
- 目录
《运筹与管理科学丛书》序
前言
符号说明
第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
第9章 广义多项式比式和问题的分支定界算法 169
9.1 等价问题 169
9.2 线性松弛规划及加速技巧 170
9.3 算法及其收敛性 181
9.3.1 分支规则 181
9.3.2 算法描述 182
9.3.3 收敛性分析 183
9.4 数值实验 184
9.5 本章小结 185
第10章 一般非线性比式和问题的分支定界算法 186
10.1 凹、凸比式和问题的单纯形分支定界算法 186
10.1.1 问题描述 186
10.1.2 等价问题及定界方法 186
10.1.3 算法及其收敛性 189
10.1.4 数值算例 191
10.2 D.C.函数比式和问题的锥分分支定界算法 192
10.2.1 等价变换 193
10.2.2 带有反凸约束的线性规划 195
10.2.3 求解方法 198
10.2.4 算法及其收敛性 199
10.2.5 数值实验 200
10.3 本章小结 204
参考文献 205
索引 215
《运筹与管理科学丛书》已出版书目 218