A new class of polynomial primal-dual methods for linear and semidefinite optimization

J. Peng, C. Roos and T. Terlaky

We propose a new class of primal-dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large update method for LO based on the new search direction has a polynomial complexity $O\br{n^{\frac{4}{4+\rho}}\log\frac{n}{\e}}$ iterations where $\rho\in [0,2]$ is a parameter used in the system defining the search direction. If $\rho=0$, our results reproduce the well known complexity of the standard primal dual Newton method for LO. At each iteration, our algorithm needs only to solve a linear equation system. An extension of the algorithms to semidefinite optimization is also presented.

Faculty of Information Technology and Systems, Delft University of Technology, P.O.Box 5031, 2600 GA Delft, The Netherlands, December, 1999.

Contact: j.peng@its.tudelft.nl