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 language | English |
---|---|
Pages (from-to) | 1944-1961 |
Journal | SIAM Journal on Optimization |
Volume | 26 |
Issue number | 3 |
DOIs | |
Publication status | Published - Sept 2016 |
Keywords
- semidefinite programming
- interior point method
- Turing model complexity
- ellipsoid method