A new class of polynomial primal–dual methods for linear and semidefinite optimization

A new class of polynomial primal–dual methods for linear and semidefinite optimization

0.00 Avg rating0 Votes
Article ID: iaor20032047
Country: Netherlands
Volume: 143
Issue: 2
Start Page Number: 234
End Page Number: 256
Publication Date: Dec 2002
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: linear
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 of O(n4/(4+ρ)log(n/ϵ)) iterations, where ρ∈[0,2] is a parameter used in the system defining the search direction. If ρ=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.

Reviews

Required fields are marked *. Your email address will not be published.