A New Class of Polynomial Primal-Dual Methods for Linear and Semidefinite Optimization

J Peng (J.Pengits.tudelft.nl)
C Roos (C.Roosits.tudelft.nl)
T Terlaky (terlakycas.mcmaster.ca)

Abstract: 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.

Keywords: Linear Optimization, Semidefinite Optimization, Interior Point Method,

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Linear, Cone and Semidefinite Programming

Citation: Manuscript, TU Delft, NL, december 1999

Download: [Postscript][PDF]

Entry Submitted: 08/18/2000
Entry Last Modified: 08/28/2000

Modify/Update this entry