一种新的线性规划中原始对偶内点算法的核函数*

摘要

针对线性规划中原始对偶内点法给出了一种新的核函数，并且给出了基于这个新的核函数的原始对偶内点算法。在算法的理论分析中，首先利用该核函数导数的反函数估计出该函数本身的上界；其次利用相关定理给出了最优的迭代步长的下界；最后证明基于牛顿迭代步的原始对偶方法的大步迭代和小步迭代的迭代上界，并通过对不同规模的线性规划问题进行数值计算来说明这个算法的有效性。%A new kernel function is introduced for primal-dual interior methods for linear optimiza-tion and an algorithm of primal-dual interior methods is presented based on this function.In theo-retical analysis of this algorithm,the bound of the kernel function is obtained by using the inverse function of its derivative function and the optimal step size is obtained by combining relevant lem-mas.Finally,the upper bound of large-update iteration and small-update iteration of primal-dual interior method is obtained based on Newton iteration method,and the numerical results are given to analyze the effectiveness of the algorithm.