Optimization Online


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

J Peng (J.Peng***at***its.tudelft.nl)
C Roos (C.Roos***at***its.tudelft.nl)
T Terlaky (terlaky***at***cas.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society