数学规划基础PDF电子书下载

第1章 引言 1

1.1数学描述与例子 1

1.2优化问题的分类 3

1.3优化算法 5

1.4数学基础 6

1.5评注和参考 9

习题1 9

第2章 线性规划：基本理论与方法 11

2.1基本性质 11

2.1.1标准形 13

2.1.2基本可行解 15

2.1.3基本定理 16

2.1.4几何直观 17

2.2单纯形法 19

2.2.1既约费用系数 20

2.2.2基本可行解的改进 21

2.2.3计算过程 22

2.2.4退化与循环 25

2.2.5初始基本可行解 27

2.2.6修正单纯形法 29

2.2.7单纯形法的效率 33

2.3对偶 34

2.3.1对偶问题 35

2.3.2对偶定理 36

2.3.3对偶问题与单纯形法的关系 37

2.3.4灵敏度与互补 40

2.3.5对偶单纯形法 41

2.4评注与参考 44

习题2 44

第3章 线性规划：扩展及其应用 54

3.1网络单纯形法 54

3.1.1问题的表述 54

3.1.2生成树与基 55

3.1.3网络单纯形法 57

3.2最小费用流问题的应用 60

3.2.1运输问题和指派问题 60

3.2.2最大流问题 62

3.2.3最短路问题 64

3.3整数线性规划 66

3.3.1简介 66

3.3.2对偶理论 69

3.4整数规划的典型方法 70

3.4.1 Gomory割平面法 71

3.4.2分枝定界法 73

3.5评注与参考 77

习题3 78

第4章 无约束优化：基础 80

4.1极小点的条件 80

4.1.1局部极小点的条件 80

4.1.2凸性与全局极小点 82

4.2算法概述 84

4.2.1概述 84

4.2.2线搜索法 86

4.3非精确线搜索 87

4.3.1一维搜索的终止准则 88

4.3.2下降方法的稳定性 90

4.4线搜索子问题的算法 92

4.5评注与参考 98

习题4 98

第5章 无约束优化：线搜索法 100

5.1基本方法 100

5.1.1最速下降法 100

5.1.2牛顿法 103

5.2共轭梯度法 106

5.2.1扩展子空间定理 106

5.2.2基本的共轭梯度法 107

5.2.3收敛速度与预条件 113

5.3拟牛顿法 116

5.3.1拟牛顿条件 116

5.3.2 DFP法和BFGS法 117

5.3.3 DFP法和BFGS法的性质 120

5.3.4 SR1法 122

5.4最小二乘 124

5.4.1线性最小二乘 124

5.4.2非线性最小二乘 125

5.5评注与参考 128

习题5 130

第6章 无约束优化：信赖域法 136

6.1原型算法 136

6.2信赖域子问题 140

6.2.1解的刻画 140

6.2.2求解子问题的牛顿法 142

6.3求解子问题的近似方法 145

6.3.1柯西点 145

6.3.2 Dog-leg法 146

6.3.3 Steihaug共轭梯度法 147

6.4实用信赖域法 149

6.5评注与参考 150

习题6 150

第7章 约束优化：理论 153

7.1概述 153

7.2 Lagrange乘子 155

7.3一阶条件 160

7.4二阶条件 164

7.5凸规划 167

7.6凸规划和Lagrange乘子 168

7.7对偶 171

7.8半定规划 174

7.8.1半定规划的对偶理论 175

7.8.2最大割问题的0.878近似算法 177

7.8.3半定规划的其他应用 179

7.9评注与参考 181

习题7 182

第8章 约束优化：线性约束规划 186

8.1等式约束二次规划 186

8.2积极集法 191

8.3线性等式约束规划 194

8.4线性不等式约束规划 197

8.5锯齿现象 199

8.6评注与参考 201

习题8 202

第9章 约束优化：非线性约束规划 205

9.1惩罚和障碍函数 205

9.1.1 Courant罚函数 206

9.1.2障碍函数 211

9.2乘子罚函数 212

9.3 e1精确罚函数 218

9.4逐步二次规划法 223

9.4.1 Lagrange-Newton法 223

9.4.2基本逐步二次规划法 223

9.4.3 e1价值函数 227

9.4.4实用逐步二次规划法 230

9.5线性规划的路径跟踪算法 234

9.5.1障碍函数子问题和中心路径 234

9.5.2用牛顿法求解障碍函数子问题 235

9.5.3理论分析 236

9.6评注与参考 239

习题9 239

附录A基础知识 242

A.1集合 242

A.2矩阵 242

A.3空间 243

A.4特征值与二次型 245

A.5拓扑概念 246

A.6函数 247

A.7矩阵分解 250

A.7.1高斯消元法与LU分解 250

A.7.2 Cholesky分解 253

A.7.3 QR分解 254

A.7.4奇异值分解 255

A.8其他 255

A.8.1标量方程求根 255

A.8.2误差分析和浮点计算 256

A.8.3条件数和稳定性 257

附录B阅读材料 259

B.1 KKT条件和对偶理论的应用实例 259

B.1.1 KKT条件的力学解释 259

B.1.2 KKT条件的应用实例 260

B.1.3对偶理论的应用实例 262

B.2 MAX-2-SAT问题的半定规划松弛 263

参考文献 266

索引 269

一画 269

二画 269

三画 270

四画 270

五画 271

六画 272

七画 274

八画 274

九画 276

十画 277

十一画 278

十二画 278

十三画 279

十四画 279

十五画 279

十六画 279

其他 279