Journal of Inequalities and Applications
Volume 2 (1998), Issue 2, Pages 181-194
doi:10.1155/S1025583498000113
A conjugate direction method for approximating the analytic center of a polytope
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.
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 .