A class of polynomial variable metric algorithms for linear optimization

In the paper, the behaviour of interior point algorithms is analyzed by using a variable metric method approach. A class of polynomial variable metric algorithms is given achieving O((n/β)L) iterations for solving a canonical form linear optimization problem with respect to a wide class of Riemannian metrics, where n is the number of dimensions and β a fixed value. It is shown that the vector fields of several interior point algorithms for linear optimization is the negative Riemannian gradient vector field of a linear, a potential or a logarithmic barrier function for suitable Riemannian metrics.