第1章 引言 1
1.1最优化问题 1
1.2问题的分类 2
1.3问题的规模 4
1.4迭代算法及收敛性 5
第1部分 线性规划 7
第2章 线性规划的基本性质 9
2.1导论 9
2.2线性规划问题举例 11
2.3基础解 15
2.4线性规划基本定理 17
2.5凸性相关分析 18
2.6习题 22
第3章 单纯形法 26
3.1主元旋转 26
3.2相邻极点 30
3.3确定最小可行解 33
3.4单纯形法——计算过程 36
3.5寻找基础可行解 39
3.6单纯形法的矩阵形式 43
3.7运输问题的单纯形法 45
3.8分解 54
3.9总结 57
3.10习题 58
第4章 对偶与互补理论 67
4.1对偶线性规划 67
4.2对偶定理 69
4.3与单纯形法的关系 71
4.4灵敏度与互补松弛分析 75
4.5最大流—最小割定理 76
4.6对偶单纯形法 80
4.7原始—对偶算法 82
4.8总结 86
4.9习题 87
第5章 内点法 94
5.1复杂性理论的要素 95
5.2单纯形法不是多项式时间的 96
5.3椭球算法 98
5.4分析中心 100
5.5中心路径 102
5.6解策略 107
5.7终止和初始化 112
5.8总结 116
5.9习题 117
第6章 锥线性规划 121
6.1凸锥 121
6.2锥线性规划问题 122
6.3锥线性规划的Farkas引理 125
6.4锥线性规划的对偶 128
6.5 SDP问题的互补性与解的秩 135
6.6锥线性规划的内点算法 139
6.7总结 142
6.8习题 142
第2部分 无约束问题 147
第7章 解和算法的基本性质 149
7.1一阶必要条件 150
7.2无约束问题举例 152
7.3二阶条件 154
7.4凸函数和凹函数 156
7.5凸函数的极小化与极大化 160
7.6零阶条件 161
7.7下降算法的全局收敛性 163
7.8收敛速度 169
7.9总结 173
7.10习题 173
第8章 基本下降法 176
8.1线搜索算法 176
8.2最速下降法 189
8.3收敛理论的应用 199
8.4加速最速下降法 202
8.5牛顿法 204
8.6坐标下降法 209
8.7总结 213
8.8习题 214
第9章 共轭方向法 219
9.1共轭方向 219
9.2共轭方向法的下降性质 221
9.3共轭梯度法 223
9.4共轭梯度法——一种最佳方法 226
9.5部分共轭梯度法 228
9.6非二次问题上的推广 230
9.7平行切线法 232
9.8习题 234
第10章 拟牛顿法 237
10.1修正牛顿法 237
10.2逆阵的构造 239
10.3 Davidon-Fletcher-Powell法 241
10.4 Broyden族方法 243
10.5收敛性质 246
10.6尺度法 249
10.7无记忆的拟牛顿法 252
10.8最速下降法与拟牛顿法的组合 254
10.9总结 258
10.10习题 259
第3部分 约束最小化问题 265
第11章 约束最小化问题的条件 267
11.1约束 267
11.2切平面 268
11.3一阶必要条件（等式约束） 271
11.4例子 272
11.5二阶条件 276
11.6切子空间中的特征值 278
11.7灵敏度 281
11.8不等式约束 282
11.9零阶条件和拉格朗日松弛 285
11.10总结 291
11.11习题 292
第12章 原始方法 295
12.1原始方法的优点 295
12.2可行方向法 296
12.3起作用集方法 297
12.4梯度投影法 300
12.5梯度投影法的收敛速度 305
12.6简化梯度法 311
12.7简化梯度法的收敛速度 315
12.8变形 321
12.9总结 322
12.10习题 322
第13章 罚函数法和障碍函数法 326
13.1罚函数法 327
13.2障碍函数法 329
13.3罚函数法和障碍函数法的性质 331
13.4牛顿法和罚函数 338
13.5共轭梯度法和罚函数法 339
13.6罚函数的规范化 341
13.7罚函数法和梯度投影法 342
13.8精确罚函数 345
13.9总结 348
13.10习题 348
第14章 对偶与对偶方法 352
14.1全局对偶 353
14.2局部对偶 357
14.3对偶最速上升的标准收敛速度 361
14.4可分离问题及其对偶 362
14.5增广拉格朗日函数 365
14.6乘子法 369
14.7乘子的交替方向法 372
14.8切平面法 376
14.9习题 380
第15章 原始—对偶法 383
15.1标准形式问题 383
15.2一种简单的优值函数 385
15.3基本的原始—对偶法 386
15.4修正牛顿法 391
15.5下降性质 392
15.6收敛速度 396
15.7原始—对偶内点法 397
15.8总结 400
15.9习题 401
附录A 数学知识回顾 406
A.1集合 406
A.2矩阵记号 407
A.3空间 408
A.4特征值和二次型 409
A.5拓扑概念 410
A.6函数 410
附录B 凸集 414
B.1基本概念 414
B.2超平面和多面体 415
B.3分离超平面和支撑超平面 417
B.4极点 419
附录C 高斯消元法 421
附录D 基本的网络概念 424
D.1网络流 425
D.2树程序 426
D.3配送网络 427