##
An O(\sqrt{n}L) Iteration Bound Primal-Dual Cone
Affine Scaling Algorithm for Linear Programming

###
Jos F. Sturm and Shuzhong Zhang

In this paper we introduce a primal-dual affine scaling method. The method
uses a search-direction obtained by minimizing the duality gap over a linearly
transformed conic section. This direction neither coincides with known primal-
dual affine scaling directions, nor does it fit in the generic primal-dual
method. The new method requires O(\sqrt{n}L) main iterations. It is shown that
the iterates follow the primal-dual central path in a neighbourhood which is
larger than the conventional close neighbourhood (e.g. the N_2 neighborhood).
The proximity to the primal-dual central path is measured by trigonometric
functions.
Contact: sturm@opres.few.eur.nl, zhang@opres.few.eur.nl