Back to Search Start Over

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

Authors :
de Klerk, Etienne
Vallentin, Frank
Source :
SIAM J. Optim., 26(3), 1944-1961, 2016
Publication Year :
2015

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.<br />Comment: (v2) some comments added, 16 pages

Details

Database :
arXiv
Journal :
SIAM J. Optim., 26(3), 1944-1961, 2016
Publication Type :
Report
Accession number :
edsarx.1507.03549
Document Type :
Working Paper
Full Text :
https://doi.org/10.1137/15M103114X