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.
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 language | English |
|---|---|
| Place of Publication | Ithaca |
| Publisher | Cornell University Library |
| Number of pages | 16 |
| DOIs | |
| Publication status | Published - Jul 2015 |
Publication series
| Name | arXiv |
|---|---|
| Volume | 1507.03549 |
Keywords
- semidefinite programming
- interior point method
- Turing model complexity
- ellipsoid method