A new polynomial-time algorithm for linear programming (Q761967): Difference between revisions

This paper discusses a new polynomial time algorithm for linear programming (LP). It is an interior point method whose worst case computational complexity is \(0(n^{3.5}L)\) arithmetic operations on 0(L) bit numbers, where n is the number of variables and L is the number of bits in the input. The complexity bound for this algorithm is better than that for the ellipsoid algorithm by a factor of \(0(n^{2.5}).\) The author shows that every LP can be transformed into the form: min cx subject to \(x\in \Omega \cap \Delta\), where \(\Omega\) is the subspace \(\{\) \(x: Ax=0\}\) and \(\Delta\) is the simplex \(\{\) \(x: x\geq 0\) and \(\Sigma x_ j=1\}\), and the minimum objective value in the problem is known to be zero. His algorithm solves the LP in this form. Let \(a_ 0=(1/n)e\), where e is the vector of all 1's in \(R^ n\). Let \(B(a_ 0,r)\), \(B(a_ 0,R)\) be respectively the largest sphere with center \(a_ 0\) lying in \(\Delta\), and the smallest sphere with center \(a_ 0\) containing \(\Delta\). Then \(R/r=(n-1)\). Using this he shows that if \(a_ 0\) is feasible, \(a_ 0-r\hat c\), where \(\hat c\) is the normalized vector which in the orthogonal projection of c in \(\Omega\), is chosen to the minimum objective value by a factor of (1-1/(n-1)). This is the main result on which the algorithm is based. The algorithm is initiated with a feasible solution \(x^ 0>0\), and it generates a descent sequence of positive feasible points \(x^ 0,x^ 1,..\).. In the kth step, the point \(x^ k\) is brought into the center of the simplex by a projective transformation, a step of the form described above is taken, and the inverse projective transformation is applied, leading to the next point \(x^{k+1}\), reducing the objective function value by a factor of 0(n). The sequence of points generated, converges to a near optimal solution in polynomial time.