线性规划的Karmarkar算法PDF电子书下载

1 引言 1

2 算法概述 4

3 预备知识 5

3.1 Karmarkar标准型 5

3.2 向量在线性空间中的投影 5

3.3 在球上求线性函数的极值 6

3.4 标准单纯型S的内切球与外接球半径 7

3.5 投影变换 8

3.6 势函数 9

3.7 几个不等式 10

3.8 两个矩阵结果 11

4 算法步骤与解释 13

4.1 算法步骤 13

4.2 对算法的解释 14

5 算法证明与计算复杂性分析 17

6 一般情况的处理 24

6.1 理论方法 24

6.2 实用方法 30

7 算法的改进 33

7.1 算法步骤 34

7.2 算法证明 35

7.3 时间复杂性估计 38