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: [email protected]
![[PS]](../gif/PS.gif)
![[IP PAGE]](../gif/HOME.gif)
![[SEARCH AGAIN]](../gif/SEARCH.gif)