线性优化及扩展 理论与算法PDF电子书下载

第一章 导言 1

1.1 线性规划的历史 1

1.2 线性规划问题 3

1.2.1 标准型线性规划 3

1.2.2 隐含式假设 4

1.2.3 转换成标准型 5

1.3 线性规划问题的举例 6

1.4 掌握线性规划 10

进一步阅读的参考文献 11

习题 12

第二章 线性规划的几何解释 16

2.1 线性规划的基本术语 16

2.2 超平面、半空间和多面体集合 17

2.3 仿射集、凸集和锥 19

2.4 顶点和基础可行解 22

2.5 非退化性与相邻性 24

2.6 凸多面体的分解定理 26

2.8 结论——不同方法的机能 28

2.7 线性规划的基本定理 28

进一步阅读的参考文献 30

习题 30

第三章 修正的单纯形方法 33

3.1 迭代算法的构成 33

3.2 单纯形法的基础 35

3.3 单纯形法的代数 36

3.3.1 单纯形法的停止准则——最优性检验 37

3.3.2 单纯形法的迭代——向改进方向移动 38

3.4.1 两阶段法 45

3.4 单纯形法的开始 45

3.4.2 大M法 46

3.5 退化和循环 48

3.6 避免循环 50

3.6.1 字典序规则 50

3.6.2 Bland规则 51

3.7 修正的单纯形法 51

3.8 结论性评语 57

进一步阅读的参考文献 58

习题 58

4.1 对偶线性规划 62

第四章 对偶理论和灵敏度分析 62

4.2 对偶理论 64

4.3 补偿松弛和最优性条件 68

4.4 对偶问题的经济解释 70

4.4.1 对偶变量和影子价格 71

4.4.2 对偶问题的解释 71

4.5 对偶单纯形法 73

4.5.1 对偶单纯形法的基本概念 73

4.5.2 Sherman-Mor rison-Woodbury公式 74

4.5.3 对偶单纯形法的计算机实现 78

4.5.4 寻找初始对偶基础可行解 81

4.6 原-对偶方法 82

4.6.1 原-对偶单纯形法的计算过程 84

4.7 灵敏度分析 87

4.7.1 价格向量的改变 87

4.7.2 右端项向量的改变 89

4.7.3 约束矩阵的改变 92

4.8 结论 96

习题 97

进一步阅读的参考文献 97

第五章 复杂性分析与椭球算法 102

5.1 计算复杂性的概念 102

5.2 单纯形法的复杂性 104

5.3 椭球法的基本思想 107

5.4 线性规划的椭球法 112

5.5 线性规划的椭球法的性能 115

5.6 基本算法的改进 116

5.6.1 深切割 116

5.6.2 替代切割 118

5.6.3 平行切割 119

5.6.4 用单纯形替代椭球 120

5.7 结论 121

进一步阅读的参考文献 122

习题 123

第六章 Karmarkar的投影尺度算法 126

6.1 Karmarkar算法的基本思想 126

6.2 Karmarkar的标准形式 128

6.2.1 单纯形结构 129

6.2.2 单纯形上的投影变换 130

6.3 Karmarkar的投影尺度算法 132

6.4 多项式时间可解性 136

6.5 向Karmarkar标准型的转换 143

6.6 解决最优目标值未知的问题 145

6.7 无约束凸对偶方法 153

6.7.1 8最优解 155

6.7.2 扩展 159

6.8 结论 160

进一步阅读的参考文献 161

习题 162

第七章 仿射尺度算法 164

7.1 原仿射尺度算法 165

7.1.1 原仿射尺度的基本思想 165

7.1.2 原仿射尺度算法的实现 176

7.1.3 计算复杂性 182

7.2 对偶仿射尺度算法 188

7.2.1 对偶仿射尺度的基本思想 188

7.2.2 对偶仿射尺度算法 191

7.2.3 对偶仿射尺度算法的实现 193

7.2.4 改进计算复杂性 196

7.3.1 原-对偶算法的基本思想 203

7.3 原-对偶算法 203

7.3.2 移动的方向和步长 206

7.3.3 原-对偶算法 211

7.3.4 多项式时间终止 211

7.3.5 原-对偶算法的起动 215

7.3.6 实际计算 217

7.3.7 用幂级数加速的方法 222

7.4 结论 223

进一步阅读的参考文献 224

习题 226

第八章 对内点法的深入分析 230

8.1 沿着不同的代数路径移动 230

8.1.1 带有对数壁垒函数的原仿射尺度法 232

8.1.2 带有对数壁垒函数的对偶仿射尺度法 233

8.1.3 原-对偶算法 234

8.2 遗失的信息 236

8.2.1 原方法中的对偶信息 236

8.2.2 对偶方法中的原信息 237

8.3 代数路径的扩展 237

8.4 移动方向的几何解释 239

8.4.1 带有对数壁垒函数的原仿射尺度算法 240

8.4.2 带有对数壁垒函数的对偶仿射尺度算法 242

8.4.3 原-对偶算法 243

8.5 广义理论 247

8.5.1 广义原仿射尺度法 247

8.5.2 广义对偶仿射尺度法 249

8.6 结论 251

进一步阅读的参考文献 252

习题 252

9.1.1 原二次规划 255

9.1 线性约束的凸二次规划 255

第九章 凸二次规划的仿射尺度算法 255

9.1.2 对偶二次规划 257

9.2 二次规划的仿射尺度法 258

9.2.1 二次规划的原仿射尺度法 258

9.2.2 二次规划的仿射尺度算法的改进 269

9.3 二次规划的原-对偶算法 273

9.3.1 基本概念 273

9.3.2 计算实现步骤 275

9.3.3 原-对偶算法的收敛性质 278

9.4.1 基本概念 279

9.4 线性约束的凸规划 279

9.4.2 计算步骤 281

9.5 结论 282

进一步阅读的参考文献 283

习题 284

第十章 内点法的计算方法 287

10.1 计算的瓶颈 287

10.2 Cho1esky分解法 288

10.2.1 计算Chole sky因子 290

10.2.2 分块Cholesky分解 292

10.2.3 稀疏Cholesky分解 294

10.2.4 符号Cholesky分解 300

10.2.5 解三角方程组 301

10.3 共轭梯度法 303

10.4 LQ分解方法 306

10.5 结论 314

进一步阅读的参考文献 315

习题 316

参考文献 319