Universität zu Köln

de Klerk, Etienne and Vallentin, Frank ORCID: 0000-0002-3205-4607 (2016). ON THE TURING MODEL COMPLEXITY OF INTERIOR POINT METHODS FOR SEMIDEFINITE PROGRAMMING. SIAM J. Optim., 26 (3). S. 1944 - 1962. PHILADELPHIA: SIAM PUBLICATIONS. ISSN 1095-7189

Full text not available from this repository.

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code de Klerk, Etienne UNSPECIFIED UNSPECIFIED UNSPECIFIED Vallentin, Frank UNSPECIFIED orcid.org/0000-0002-3205-4607 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-288889
DOI:	10.1137/15M103114X
Journal or Publication Title:	SIAM J. Optim.
Volume:	26
Number:	3
Page Range:	S. 1944 - 1962
Date:	2016
Publisher:	SIAM PUBLICATIONS
Place of Publication:	PHILADELPHIA
ISSN:	1095-7189
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Mathematical Institute
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language FINITE-PRECISION Multiple languages Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/28888