《线性优化及扩展 理论与算法》求取 ⇩

第一章导言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