Interior-Point Abstracts

On the interplay among entropy, variable metrics and potential functions in interior-point algorithms

L. Tuncel and M. J. Todd

We are motivated by the problem of constructing a primal-dual barrier function whose Hessian induces the (theoretically and practically) popular symmetric primal and dual scalings for linear programming problems. Although this goal is impossible to attain, we show that the primal-dual entropy function may provide a satisfactory alternative. We study primal-dual interior-point algorithms whose search directions are obtained from a potential function based on this primal-dual entropy barrier. We provide polynomial iteration bounds for these interior-point algorithms. Then we illustrate the connections between the barrier function and a reparametrization of the central path equations. Finally, we consider the possible effects of more general reparametrizations on infeasible-interior-point algorithms.

Research Report CORR 95-20, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, September 1995. Also available as Technical Report 1135, School of OR and IE, Cornell University, Ithaca, NY, September 1995.