*(English)*Zbl 0557.90065

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\left({n}^{3\xb75}L\right)$ 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\left({n}^{2\xb75}\right)\xb7$

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\ge 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\widehat{c}$, where $\widehat{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},\xb7\xb7$.. 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.

##### Keywords:

polynomial time algorithm; interior point method; computational complexity; near optimal solution##### 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. |

[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). |