本书介绍优化理论的基本概念和最优化问题的基本求解方法,内容包括线性规划、整数规划、动态规划、图与网络算法、无约束优化、约束优化等。这些优化概念和方法从总体上可分为组合优化和连续优化两大类。本书讲授的内容可看作计算机类专业本科算法课程的延伸,尤其注重数学概念的应用和分析证明能力的训练。
样章试读
目录
- 目录
前言
第一版前言
第1章 凸集和凸函数 1
1.1 最优化问题和方法 1
1.2 凸集及相关性质 4
1.3 凸集的分离 5
1.3.1 点和凸集的分离 5
1.3.2 凸集和凸集的分离 11
1.4 凸函数 13
1.4.1 凸函数及相关性质 13
1.4.2 凸函数的判别 15
1.5 凸规划问题 21
1.6 习题 22
第2章 线性规划的基本性质 24
2.1 线性规划的形式 24
2.1.1 线性规划的三种基本形式 24
2.1.2 三种形式相互等价 30
2.2 可行域和顶点 31
2.3 解线性规划的图解法 33
2.4 基本解和基本可行解 34
2.5 线性规划基本定理 42
2.6 习题 43
第3章 单纯形算法 45
3.1 单纯形算法的基本思想 45
3.2 几何形式的单纯形算法 46
3.3 代数化的单纯形算法 46
3.3.1 基本思想 46
3.3.2 代数化的单纯形算法示例 46
3.4 一般的单纯形算法 51
3.4.1 检验数向量 51
3.4.2 目标函数值和检验向量的值 51
3.4.3 单纯形算法 52
3.5 表格化的单纯形算法 54
3.5.1 单纯形表 54
3.5.2 旋转 55
3.6 使用数学软件解线性规划 62
3.6.1 使用MATLAB解线性规划 62
3.6.2 使用CPLEX解线性规划 64
3.7 单纯形算法的分析 66
3.8 退化问题的处理 71
3.9 两阶段法 71
3.9.1 两阶段法的基本思想 71
3.9.2 解辅助线性规划 72
3.9.3 两阶段单纯形算法 74
3.10 矩阵的全单位模性质 86
3.11 再议解线性规划 88
3.11.1 单纯形算法的复杂性 89
3.11.2 解线性规划的多项式时间算法 89
3.11.3 单纯形算法的平滑分析 89
3.12 习题 90
第4章 线性规划对偶理论 94
4.1 线性规划的对偶 94
4.2 对偶定理 100
4.3 对偶单纯形算法 109
4.4 关于单纯形表检验数行和右端项的讨论 114
4.5 原始对偶算法 115
4.5.1 最短路问题的整数规划 116
4.5.2 原始对偶算法 117
4.5.3 算法分析 119
4.6 习题 123
第5章 整数规划 126
5.1 整数规划问题 126
5.1.1 背包问题 126
5.1.2 最小生成树问题 127
5.1.3 旅行售货商问题 128
5.1.4 整数线性规划 129
5.2 割平面法 131
5.2.1 割平面法的基本思想 131
5.2.2 割平面的生成方法 132
5.3 分支定界法 137
5.3.1 分支定界法的基本思想 137
5.3.2 分支定界法解整数规划 138
5.4 习题 145
第6章 动态规划 147
6.1 动态规划的原理 147
6.1.1 多阶段决策问题 147
6.1.2 最优化原理 152
6.1.3 前向优化和后向优化 154
6.2 问题举例 155
6.2.1 最长公共子序列问题 155
6.2.2 背包问题 157
6.2.3 从背包问题谈时间复杂度 160
6.2.4 旅行售货商问题 163
6.2.5 一般图上的最短s-t路问题 167
6.3 习题 170
第7章 图与网络算法 172
7.1 最大流问题 172
7.1.1 最大流的增广路算法 172
7.1.2 最大流和最小割 181
7.1.3 对偶理论的观点 183
7.2 最小费用流问题 186
7.3 匹配问题概述 196
7.4 二分图上不带权重的最大匹配问题 197
7.4.1 使用最大流算法求解 197
7.4.2 增广路算法 200
7.5 二分图上带权重的最大匹配问题 207
7.5.1 归约到最小费用流问题的解法 207
7.5.2 匈牙利算法 209
7.6 习题 214
第8章 无约束优化的基本概念 217
8.1 一元函数的极小化问题 217
8.1.1 黄金分割法 217
8.1.2 函数逼近法 221
8.2 下降方向 221
8.3 一维搜索的基本概念 225
8.4 无约束优化问题的一阶极值条件 225
8.5 无约束二次规划的解法 226
8.6 习题 233
第9章 使用导数的无约束优化方法 234
9.1 下降算法的一般形式 234
9.2 最速下降法 235
9.2.1 算法 235
9.2.2 搜索为什么要沿负梯度方向进行 236
9.2.3 最速下降法的锯齿现象 239
9.2.4 用最速下降法解无约束二次规划 241
9.3 牛顿法 244
9.3.1 一元优化问题的牛顿法 244
9.3.2 多元优化问题的牛顿法 246
9.3.3 阻尼牛顿法 250
9.3.4 牛顿法的进一步修正 253
9.4 共轭梯度法 254
9.4.1 基本概念 255
9.4.2 共轭方向的几何意义 255
9.4.3 共轭梯度算法 257
9.4.4 算法分析 261
9.4.5 一般无约束优化问题的共轭梯度法 270
9.5 无约束优化问题的二阶极值条件 271
9.6 拟牛顿法 273
9.6.1 拟牛顿方程 273
9.6.2 DFP算法 274
9.6.3 BFGS算法 276
9.7 习题 277
第10章 约束优化问题的基本概念和性质 279
10.1 问题举例 279
10.2 可行方向 281
10.3 不等式约束问题的一阶最优性条件 282
10.3.1 必要条件 283
10.3.2 充分条件 294
10.4 一般约束问题的一阶最优性条件 294
10.4.1 必要条件 294
10.4.2 充分条件 297
10.5 约束优化问题的对偶理论 303
10.5.1 对偶问题 303
10.5.2 凸规划的对偶 307
10.6 习题 312
第11章 约束优化问题的解法 315
11.1 等式约束的二次规划的解法 315
11.1.1 直接消元法 316
11.1.2 拉格朗日法 319
11.2 一种凸二次规划的有效集方法 323
11.2.1 基本思想 323
11.2.2 方法的细节 324
11.2.3 算法设计 327
11.3 简约梯度法 332
11.3.1 简约梯度 332
11.3.2 构造搜索方向 337
11.3.3 算法设计 340
11.4 罚函数法 350
11.4.1 外点罚函数法 350
11.4.2 内点罚函数法 357
11.5 习题 359
第12章 若干基本的数学概念和定理 361
12.1 n维空间中的点与集合 361
12.2 函数的极限和连续 362
12.2.1 一元函数 362
12.2.2 多元函数 362
12.3 无穷小量与无穷小量的阶 363
12.4 可微函数和函数的微分 364
12.4.1 一元函数可微和微分 364
12.4.2 二元函数可微和全微分 365
12.5 泰勒公式 366
12.5.1 带佩亚诺余项的泰勒公式 366
12.5.2 带拉格朗日余项的泰勒公式 366
12.6 方向导数 367
12.7 广义逆矩阵 368
12.7.1 广义逆矩阵的定义 368
12.7.2 广义逆矩阵的计算 369
参考文献 374
索引 378
京公网安备 11010102004214号