论文部分内容阅读
能否把一个非线性规划的算法进行改造后用于线性规划,使算法在解线性规划时的时间为问题大小的一个多项式阶,这是一个很有意义的研究方向。为了讨论这种改进,就要对本来是针对连续优化问题的算法以及问题本身的表达引入组合特性。本文通过对目前存在的线性规划的多项式时间算法的组合特性的分析,提出对一般算法引入组合特性的可能途径。这种途径主要是利用广义的二分搜索的一些性质。文中还分析了Karmarkar算法的非线性收敛性质。