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

[POSTSCRIPT] [IP PAGE] [SEARCH AGAIN]