On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming.

Etienne de Klerk, Frank Vallentin

Research output: Working paperOther research output

Abstract

It is known that one can solve semidenite programs to within
xed accuracy in polynomial time using the ellipsoid method (under some
assumptions). In this paper it is shown that the same holds true when one uses
the short-step, primal interior point method. The main idea of the proof is to
employ Diophantine approximation at each iteration to bound the intermediate
bit-sizes of iterates.
Original languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages16
DOIs
Publication statusPublished - Jul 2015

Publication series

NamearXiv
Volume1507.03549

    Fingerprint

Keywords

  • semidefinite programming
  • interior point method
  • Turing model complexity
  • ellipsoid method

Cite this