On Central-Path Proximity Measures in Interior-Point Methods

One of the main ingredients of interior-point methods is the generation of iterates in a neighborhood of the central path. Measuring how close the iterates are to the central path is an important aspect of such methods and it is accomplished by using proximity measure functions. In this paper, we propose a unified presentation of the proximity measures and a study of their relationships and computational role when using a generic primal-dual interior-point method for computing the analytic center for a standard linear optimization problem. We demonstrate that the choice of the proximity measure can affect greatly the performance of the method. It is shown that we may be able to choose the algorithmic parameters and the central-path neighborhood radius (size) in such a way to obtain comparable results for several measures. We discuss briefly how to relate some of these results to nonlinear programming problems. The first author was partially supported by Simón Bolívar University, Venezuelan National Council for Sciences and Technology (CONICIT) Grant PG97-000592, Center for Research on Parallel Computing of Rice University, and TU Delft. The authors thank Amr El Bakry, Richard Tapia, Adolfo Quiroz, and Pedro Berrizbeitia for discussions and suggestions. They acknowledge the observations and comments of the editors and an anonymous referee.