第1章 无约束优化 1
1.1 最优性条件 2
1.1.1 主要的最优性条件 9
1.2 梯度方法的收敛性 16
1.2.1 下降方向和步长准则 16
1.2.2 收敛结果 33
1.3 梯度方法的收敛速率 46
1.3.1 局部分析方法 47
1.3.2 条件数的作用 49
1.3.3 关于收敛速率的结论 57
1.4 牛顿方法及其变形 67
1.5 最小二乘问题 78
1.5.1 高斯－牛顿方法 82
1.5.2 增量梯度法 83
1.5.3 高斯－牛顿法的增量形式 92
1.6 共轭方向法 100
1.7 拟牛顿法 114
1.8 非求导方法 122
1.8.1 坐标下降法 123
1.8.2 直接搜索法 124
1.9 离散时间最优控制问题 127
1.10 一些实用的指导准则 140
1.11 注释和参考资料 144
第2章 凸集优化 147
2.1 约束优化问题 147
2.1.1 最优解的充要条件 148
2.1.2 最优解的存在性 156
2.2 可行方向法和条件梯度法 163
2.2.1 下降方向和步长规则 164
2.2.2 条件梯度法 167
2.3 梯度投影法 173
2.3.1 基于投影方法的可行方向和步长规则 174
2.3.2 收敛性分析 182
2.4 双矩阵投影方法 190
2.5 流型子优化方法 195
2.6 线性规划的仿射变换 202
2.7 坐标块下降方法 208
2.8 注释和参考资料 213
第3章 拉格朗日乘子理论 215
3.1 等式约束优化问题的必要条件 216
3.1.1 惩罚法 219
3.1.2 消元法 221
3.1.3 拉格朗日函数 224
3.2 等式约束优化问题的充分条件和灵敏度分析 230
3.2.1 增广的拉格朗日方法 231
3.2.2 可行方向法 234
3.2.3 灵敏度 235
3.3 不等式约束优化问题 239
3.3.1 Karush-Kuhn-Tucker最优性条件 241
3.3.2 转化为等式约束处理 243
3.3.3 二阶充分条件和灵敏度 245
3.3.4 充分性条件及拉格朗日最小化 246
3.3.5 Fritz John最优性条件 247
3.3.6 深化和精练 259
3.4 线性约束和对偶性 279
3.4.1 凸目标函数和线性约束 279
3.4.2 对偶理论：针对简单等式约束的优化问题 281
3.5 注释和参考资料 287
第4章 拉格朗日乘子算法 289
4.1 障碍函数法和内点法 289
4.1.1 线性规划与对数障碍方法 292
4.2 惩罚法和增广的拉格朗日方法 303
4.2.1 二次罚函数方法 305
4.2.2 乘子方法——主要思想 311
4.2.3 乘子方法的收敛性分析 318
4.2.4 对偶性和二阶乘子方法 321
4.2.5 指数乘子方法 323
4.3 精确惩罚——序贯二次规划 329
4.3.1 不可微精确罚函数 330
4.3.2 可微精确罚函数 343
4.4 拉格朗日方法和原始－对偶内点法 348
4.4.1 一阶方法 348
4.4.2 等式约束问题的类牛顿方法 352
4.4.3 全局收敛性 359
4.4.4 原始－对偶内点法 362
4.4.5 不同方法的比较 369
4.5 注释和参考资料 370
第5章 对偶性与凸规划 373
5.1 对偶问题 374
5.1.1 几何乘子 375
5.1.2 弱对偶定理 378
5.1.3 原问题和对偶问题最优解的性质 383
5.1.4 原问题不可行或最优值无界的情形 384
5.1.5 对等式约束的处理 384
5.1.6 可分问题及其几何结构 386
5.1.7 有关对偶性的其他问题 389
5.2 凸目标函数——线性约束问题 394
5.3 凸目标函数——凸约束问题 399
5.4 共轭函数及Fenchel对偶 406
5.4.1 单值规划的对偶性 410
5.4.2 网络优化 413
5.4.3 博弈和最小化最大值定理 415
5.4.4 原函数 417
5.4.5 从对偶的角度看罚函数方法 419
5.4.6 最近邻和熵最小化算法 424
5.5 离散优化及其对偶 437
5.5.1 离散优化问题的举例 438
5.5.2 分枝定界 443
5.5.3 拉格朗日松弛 450
5.6 注释和参考资料 459
第6章 对偶方法 461
6.1 对偶微分及次梯度 462
6.2 可微对偶问题的对偶上升方法 467
6.2.1 二次规划的坐标上升法 467
6.2.2 严格凸的可分问题 469
6.2.3 划分和对偶严格凹性 470
6.3 不可微优化方法 474
6.3.1 次梯度方法 474
6.3.2 近似次梯度法和增量次梯度法 478
6.3.3 割平面方法 481
6.3.4 上升法和近似上升法 486
6.4 分解方法 497
6.4.1 耦合约束的拉格朗日松弛 497
6.4.2 基于约束右侧常数分解的方法 500
6.5 注释和参考资料 502
附录A 数学背景 505
A.1 向量和矩阵 506
A.2 范数、数列、极限和连续性 508
A.3 方阵和特征值 514
A.4 对称和正定矩阵 516
A.5 导数 520
A.6 压缩映射 524
附录B 凸分析 527
B.1 凸集和凸函数 527
B.2 分离超平面 543
B.3 锥和多面体的凸性 546
B.4 极点 553
B.5 可微性问题 557
附录C 线性搜索方法 569
C.1 三次插值法 569
C.2 二次插值法 570
C.3 黄金分割法 571
附录D 牛顿法的运用 575
D.1 Cholesky分解 575
D.2 改进牛顿法的应用 577
参考文献 580