- 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/2000Entry Last Modified: 08/28/2000Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.