A new polynomial-time algorithm for linear programming.

*(English)*Zbl 0557.90065This 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.

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.

Reviewer: K.G.Murty

##### Keywords:

polynomial time algorithm; interior point method; computational complexity; near optimal solution
Full Text:
DOI

##### References:

[1] | H. S. M. Coxeter,Introduction to Geometry, Wiley (1961). |

[2] | G. B. Dantzig,Linear Programming and Extensions, Princeton University Press, Princeton, NJ (1963). |

[3] | M. Grötschel, L. Lovász andA. Schrijver, The Ellipsoid Method and its Consequences in Combinatorial Optimization,Combinatorica 1 (1981), 169–197. · Zbl 0492.90056 · doi:10.1007/BF02579273 |

[4] | L. G. Khachiyan, A polynomial Algorithm in Linear Programming,Doklady Akademii Nauk SSSR 244:S (1979), 1093–1096, translated inSoviet Mathematics Doklady 20:1 (1979), 191–194. · Zbl 0414.90086 |

[5] | V. Klee andG. L. Minty, How good is the simplex algorithm? inInequalities III, (ed. O. Shisha) Academic Press, New York, 1972, 159–179. |

[6] | O. Veblen andJ. W. Young,Projective Geometry, 1–2, Blaisdell, New York, (1938). |

[7] | R. J. Walker,Algebraic Curves, Princeton University Press (1950). · Zbl 0039.37701 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.