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

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.

(v2) some comments added, 16 pages

Cited by in corpus (11)

• Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
• Complete positivity and distance-avoiding sets
• Semidefinite programming formulations for the completely bounded norm of a tensor
• Minimizing rational functions: a hierarchy of approximations via pushforward measures
• Semidefinite programming bounds for error-correcting codes
• On Exact Reznick, Hilbert-Artin and Putinar's Representations
• An efficient sum of squares nonnegativity certificate for quaternary quartic
• A recursive theta body for hypergraphs
• Condition numbers of stochastic mean payoff games and what they say about nonarchimedean semidefinite programming
• The Augmented Mixing Method: Computing High-Accuracy Primal-Dual Solutions to Large-Scale SDPs via Column Updates
• An SDP Relaxation for the Sparse Integer Least Squares Problem