目录 1
第1章 引论 1
1.1 学科简介 1
1.2 实例与模型 4
1.3 预备知识 9
1.3.1 线性空间 9
1.3.2 范数 12
1.3.3 集合与序列 14
1.3.4 矩阵的分解与校正 15
1.3.5 函数的可微性与展开 17
1.4 习题 20
第2章 凸分析 22
2.1 仿射集 22
2.2 凸集与锥 25
2.3 凸集分离定理 27
2.3.1 点与凸集分离 28
2.3.2 凸集与凸集分离 31
2.4 多面体理论 32
2.4.1 多面体的维数 33
2.4.2 择一定理 34
2.4.3 多面体的面和最小不等式表示 38
2.4.4 多面体的表示定理 44
2.5 凸函数 49
2.5.1 基本性质 49
2.5.2 函数凸性的判定方法 52
2.6 习题 54
第3章 线性规划 57
3.1 线性规划的基本定理 57
3.1.1 基本定理与标准形式 58
3.1.2 极点的代数特征 61
3.2 单纯形算法 64
3.2.1 基本原理 64
3.2.2 算法步骤与单纯形表 67
3.2.3 启动机制 70
3.3 线性规划的最优性条件 77
3.4 对偶理论 79
3.4.1 对偶定理 79
3.4.2 对偶单纯形法 84
3.5 单纯形算法的改进与推广 88
3.5.1 修正单纯形法 88
3.5.2 原始-对偶算法 91
3.5.3 退化与循环 94
3.5.4 Dantzig-Wolfe分解算法 99
3.5.5 灵敏度分析 104
3.6.1 算法复杂性概念 108
3.6 线性规划内点算法 108
3.6.2 单纯形算法的复杂性 111
3.6.3 Karmarkar投影尺度算法 114
3.6.4 原始-对偶尺度算法 124
3.6.5 原始-对偶路径跟踪算法 130
3.6.6 内点算法的其他策略 137
3.7 习题 144
第4章 无约束优化 150
4.1 无约束优化的最优性条件 150
4.2.1 一维搜索与收敛性 152
4.2 算法收敛性 152
4.2.2 算法映射与收敛性 162
4.2.3 收敛速度与算法停止规则 166
4.3 牛顿法 170
4.3.1 迭代格式 170
4.3.2 局部收敛性 172
4.3.3 修正牛顿法 174
4.3.4 非精确的牛顿法 177
4.4 共轭方向与线性共轭梯度法 179
4.4.1 共轭方向与扩张子空间定理 179
4.4.2 线性共轭梯度法与二次终止性 181
4.5 非线性共轭梯度法 186
4.5.1 FR 共轭梯度法 187
4.5.2 PRP共轭梯度法 192
4.6 拟牛顿方法 196
4.6.1 拟牛顿条件和算法步骤 196
4.6.2 对称秩1校正公式 197
4.6.3 对称秩2校正公式 200
4.6.4 Broyden族 208
4.7 习题 213
5.1.1 一阶必要条件 220
5.1 一阶最优性条件与约束规格 220
第5章 约束优化 220
5.1.2 约束规格 226
5.1.3 一阶充分条件 228
5.2 二阶最优性条件 230
5.2.1 二阶必要条件 231
5.2.2 二阶充分条件 233
5.3 对偶理论 235
5.3.1 对偶形式 235
5.3.2 对偶定理 237
5.3.3 鞍点定理 240
5.4 二次规划 242
5.4.1 基本性质 244
5.4.2 等式约束的二次规划 248
5.4.3 凸二次规划的积极约束集方法 254
5.4.4 线性互补问题 260
5.5 可行方向法 265
5.5.1 Zoutendijk可行方向法 266
5.5.2 Rosen梯度投影法 268
5.5.3 Wolfe既约梯度法 270
5.5.4 Frank-Wolfe线性化方法 272
5.6 序列无约束化方法 273
5.6.1 二次罚函数法 275
5.6.2 对数障碍函数法 280
5.6.3 乘子法 284
5.7 逐次二次规划法 289
5.7.1 Newton-Lagrange方法 289
5.7.2 逐次二次规划的算法模型 291
5.7.3 二次规划子问题的Hesse矩阵 297
5.7.4 价值函数与搜索方向的下降性 299
5.8 信赖域法 305
5.8.1 信赖域法的基本原理 305
5.8.2 子问题的精确求解法 308
5.8.3 子问题的近似求解法 313
5.8.4 信赖域法的全局收敛性 318
5.9 习题 319
第6章 多目标规划 325
6.1 引言 325
6.2 向量集的有效点与弱有效点 327
6.2.1 几何特征 328
6.2.2 代数特征 330
6.3 多目标规划的解及其性质 333
6.3.1 Pareto最优解 333
6.3.2 KT-有效解与G-有效解 335
6.4 多目标规划的解法 338
6.3.3 最优性条件 338
6.4.1 基于一个单目标问题的方法 339
6.4.2 基于多个单目标问题的方法 343
6.5 习题 345
第7章 组合优化与整数规划 347
7.1 网络流问题与算法 348
7.1.1 图论中的基本概念 348
7.1.2 最短路问题 350
7.1.3 最大流与最小割问题 352
7.1.4 最小费用网络流问题 355
7.1.5 最大森林问题 356
7.2 匹配问题与算法 357
7.2.1 匹配与最大基数匹配 357
7.2.2 二部图匹配 359
7.3 整数规划的基本性质 362
7.3.1 整数规划的模型 363
7.3.2 整数规划的性质 366
7.4 割平面法 371
7.4.1 Gomory割平面法 371
7.4.2 构造有效不等式的方法 379
7.5.1 分支定界的基本原理 381
7.5 分支定界法 381
7.5.2 分支定界的算法步骤 383
7.6 分解算法 388
7.6.1 基于Lagrange松弛的分解算法 388
7.6.2 Benders分解算法 392
7.7 习题 397
第8章 全局优化 401
8.1 全局优化的基本概念与性质 401
8.1.1 凸集的性质 401
8.1.2 函数的连续性与凹凸性 403
8.1.3 凸包络 405
8.1.4 Lipschitz函数 409
8.1.5 D.C．函数 411
8.2 常见的全局优化模型 413
8.2.1 二次规划 413
8.2.2 凹极小化 417
8.2.3 D.C．规划 419
8.2.4 Lipschitz优化 425
8.3 外逼近与割平面算法 426
8.3.1 外逼近的基本原理 427
8.3.2 割平面算法 429
8.3.3 求解松弛问题的方法 431
8.4 凹性割方法 433
8.4.1 有效割与凹性割 434
8.4.2 凹性割方法的收敛性 437
8.4.3 反向凸约束的凹性割 439
8.5 分支定界法 441
8.5.1 基本算法 442
8.5.2 多面体剖分 444
8.5.3 定下界方法 446
8.5.4 有限性和收敛性 447
8.6 习题 449
参考文献 452
索引 455