将组合特性引入非线性规划中的一些探讨

Discussion On Introducing Combinatorial Qualities into Nonlinear Programming Problems

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

It is significant to reform a nonlinear programming algorithm to have polynomial time complexity in the sence when it is applied to LP problems. To discuss this reformation, it is necessary to introduce Combinatorial qualitiein to the nonlinear programming algorithm. This paper analyses the existing LP′s polynomial algorithms and presents an extended binarg search method as a clue to introduce combinatorial qualities in to nonlinear programming algorithms. We also Show that Karmarkar′s algorithm produces sequences with linearly convergence rate.