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

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.