Masakazu Kojima,¹ Nimrod Megiddo,^2,3 and Shinji Mizuno⁴

Abstract

The analytic center ω of an n-dimensional polytope P={x∈Rn:aiTx−bi≥0 (i=1,2,⋯,m)} with a nonempty interior Pint is defined as the unique minimizer of the logarithmic potential function F(x)=∑i=1mlog(aiTx−bi) over Pint. It is shown that one cycle of a conjugate direction method, applied to the potential function at any v∈Pint such that ε=(v−ω)T∇2F(ω)(v−ω)≤1/6, generates a point xˆ∈Pint such that (xˆ−ω)T∇2F(ω)(xˆ−ω)≤23nε2 .