On the Turing model complexity of interior point methods for semidefinite programming

Etienne de Klerk, Frank Vallentin

Research output: Contribution to journalArticleScientificpeer-review

20 Citations (Scopus)

Abstract

It is known that one can solve semidefinite programs to within fixed 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
Pages (from-to)1944-1961
JournalSIAM Journal on Optimization
Volume26
Issue number3
DOIs
Publication statusPublished - Sept 2016

Keywords

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

Fingerprint

Dive into the research topics of 'On the Turing model complexity of interior point methods for semidefinite programming'. Together they form a unique fingerprint.

Cite this