ON THE INTERPLAY AMONG ENTROPY, VARIABLE METRICS AND POTENTIAL FUNCTIONS IN INTERIOR-POINT ALGORITHMS

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