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

Etienne de Klerk, Frank Vallentin

Research output: Working paperOther research output


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
Publication statusPublished - Jul 2015

Publication series




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

Cite this