On the long-step path-following method for semidefinite programming

On the long-step path-following method for semidefinite programming

0.00 Avg rating0 Votes
Article ID: iaor20011034
Country: United States
Volume: 22
Issue: 4/5
Start Page Number: 145
End Page Number: 150
Publication Date: May 1998
Journal: Operations Research Letters
Authors: ,
Keywords: semidefinite programming
Abstract:

It has been shown in various recent research reports that the analysis of short-step primal–dual path-following algorithms for linear programming can be nicely generalized to semidefinite programming. However, the analysis of long-step path-following algorithms for semidefinite programming appeared to be less straightforward. For such an algorithm, Monteiro obtained an O(n1.5 log(1/ε)) iteration bound for obtaining an ε-optimal solution, where n is the order of the semidefinite decision variable. In this paper, we propose to use a different search direction, viz. the so-called V-space direction. It is shown that this modification reduces the iteration complexity to O(n log(1/ε)). Independently, Monteiro and Y. Zhang obtained a similar result using Nesterov–Todd directions.

Reviews

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