On the computational complexity of gap-free duals for semidefinite programming

Imre Pólik(imrepolik.net)
Tamás Terlaky(terlakylehigh.edu)

Abstract: We consider the complexity of gap-free duals in semidefinite programming. Using the theory of homogeneous cones we provide a new representation of Ramana's gap-free dual and show that the new formulation has a much better complexity than originally proved by Ramana.

Keywords: gap-free duals, Ramana-dual, semidefinite optimization, Schur complement, Siegel cone, homogeneous cones

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: COR@L Technical Report, Lehigh University

Download: [PDF]

Entry Submitted: 08/05/2009
Entry Accepted: 08/05/2009
Entry Last Modified: 08/05/2009

Modify/Update this entry