线性规划的一个扩展型Gay算法及其复杂性分析

A Variant of Gays Linear Programming Algorithm and its Complexity Analysis

给出了一个求线性规划问题初始目标下界的内点算法，将它和Ｇａｙ算法［１］结合起来，可以去掉Ｇａｙ算法中需已知一个初始目标函数下界的条件，并且证明了新算法的迭代次数和原算法相比并没有增加。

Abstract In this paper we show a interior algorithm for finding a initial lower bound of linear programming objective values. When we combine it with Gays algorithm, we remove one condition of Gays algorithm that a inital lower bound of objective values is known. We prove that the total iteration number of the new algorithm do not increse, it is also 4(n+1)L/γ.