Journal of Inequalities and Applications
Volume 2 (1998), Issue 2, Pages 181-194

A conjugate direction method for approximating the analytic center of a polytope

Masakazu Kojima,1 Nimrod Megiddo,2,3 and Shinji Mizuno4

1Departments of Mathematical and Computing Science, Tokyo Institute of Technology, Meguro-ku, Tokyo 152, Japan
2IBM Almaden Research Center, 650 Harry Road, San Jose 95120-6099, Cafifonia, USA
3School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel
4The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106, Japan

Received 21 November 1996

Copyright © 1998 Masakazu Kojima et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


The analytic center ω of an n-dimensional polytope P={xRn:aiTxbi0(i=1,2,,m)} with a nonempty interior Pint is defined as the unique minimizer of the logarithmic potential function F(x)=i=1mlog(aiTxbi) over Pint. It is shown that one cycle of a conjugate direction method, applied to the potential function at any vPint such that ε=(vω)T2F(ω)(vω)1/6, generates a point xˆPint such that (xˆω)T2F(ω)(xˆω)23nε2 .