ramana-dual

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

  • Imre Pólik
  • Tamás Terlaky
    • Categories Semi-definite Programming Tags , , , , ,

    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. CitationCOR@L Technical Report, Lehigh UniversityArticleDownload View PDF

    Exact duality for optimization over symmetric cones

  • Imre Pólik
  • Tamás Terlaky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We present a strong duality theory for optimization problems over symmetric cones without assuming any constraint qualification. We show important complexity implications of the result to semidefinite and second order conic optimization. The result is an application of Borwein and Wolkowicz’s facial reduction procedure to express the minimal cone. We use Pataki’s simplified analysis and … Read more