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