A CONJUGATE DIRECTION METHOD FOR APPROXIMATING THE ANALYTIC CENTER OFA POLYTOPE

The analytic center omega of an n-dimensional polytope P = {x epsilon R-n:a(i)(T)x-b(i) greater than or equal to 0 (i = 1, 2,...,m)} with a nonempty interior P-int is defined as the unique minimizer of the loga rithmic potential function F(x) = Sigma(i=1)(m) log(a(i)(T)x-b(i)) ove r P-int. It is shown that one cycle of a conjugate direction method, a pplied to the potential function at any v epsilon P-int such that epsi lon = root(v-omega)(T) del(2)F(omega)(v-omega) less than or equal to 1 /6, generates a point (x) over cap epsilon P-int such that root((x) ov er cap-omega)(T) del(2)F(omega)((x) over cap-omega) less than or equal to 23 root n epsilon(2).