  


A New Class of Polynomial PrimalDual Methods for Linear and Semidefinite Optimization
J Peng (J.Pengits.tudelft.nl) Abstract: We propose a new class of primaldual 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 Modify/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  