《最优化理论与算法》

第一章　概论1

1.1 实例1

1.2 最优化问题的数学形式4

1.3 二维问题的图解法6

习题一9

第二章 无约束问题的最优性条件及算法概述12

2.1 函数的可微性12

2.2 无约束问题的最优性条件18

2.3 凸函数及其极值性质20

2.4 下降算法26

习题二31

第三章　一维搜索33

3.1 试探法33

3.2　插值法40

习题三47

第四章　最速下降法与Newton法49

4.1 最速下降法49

4.2 最速下降法的收敛性质52

4.3　Newton法56

4.4　Newton法的收敛性质59

4.5 阻尼Newton法与安全Newton法64

习题四68

第五章　共轭梯度法与拟Newton法70

5.1 共轭方向法70

5.2　共轭梯度法76

5.3　拟Newton法的思想82

5.4　Broyden类拟Newton算法84

5.5　Broyden类拟Newton法的性质89

5.6　对称秩1拟Newton算法93

5.7 拟Newton法与共轭梯度法的比较99

习题五103

第六章　Powell方法107

6.1 应用于特殊正定二次函数的Powell基本算法108

6.2 应用于特殊正定二次函数的Powell直接方法110

6.3 应用于一般正定二次函数的Powell直接方法116

6.4 应用于正定二次函数的Brent方法118

习题六122

第七章　约束问题的最优性条件124

7.1　超平面与分离124

7.2　不等式约束问题的一阶最优性条件130

7.3 一般约束问题的一阶最优性条件136

7.4 约束问题的二阶最优性条件141

习题七147

第八章　线性规划150

8.1 线性规划问题及其性质150

8.2 单纯形法156

8.3 改进单纯形法170

8.4　对偶理论175

8.5　对偶单纯形法177

习题八181

第九章　可行方向法185

9.1　Zoutendijk可行方向法185

9.2　Topkis—Veinott可行方向法194

9.3　Rosen投影梯度法199

9.4　Wolfe简化梯度法203

习题九209

第十章　惩罚函数法212

10.1 惩罚函数法212

10.2 障碍函数法222

习题十226

第十一章　整数线性规划228

11.1 整数线性规划模型228

11.2　全单位模性质231

11.3　割平面法233

11.4　分枝定界法247

11.5　0—1规划253

习题十一261

第十二章　图与网络最优化263

12.1 图的基本概念264

12.2　最小支撑树问题273

12.3　最短路问题282

12.4　最大流问题288

12.5 匹配问题300

习题十二308

第十三章　算法与复杂性310

13.1 组合最优化问题310

13.2　算法与复杂性312

13.3 单纯形法的算法复杂性318

13.4　Karmarkar算法324

13.5　NP—完备理论343

习题十三347

主要参考书目349