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

Etienne de Klerk, Frank Vallentin

Research output: Contribution to journalArticleScientificpeer-review

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 languageEnglish
Pages (from-to)1944-1961
JournalSIAM Journal on Optimization
Volume26
Issue number3
DOIs
Publication statusPublished - Sep 2016

Fingerprint

Ellipsoid Method
Semidefinite Program
Diophantine Approximation
Model Complexity
Interior Point Method
Semidefinite Programming
Turing
Iterate
Polynomial time
Polynomials
Iteration

Keywords

  • semidefinite programming
  • interior point method
  • Turing model complexity
  • ellipsoid method

Cite this

@article{d24dc98237c148cb817d3afbae6b2125,
title = "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.",
keywords = "semidefinite programming, interior point method, Turing model complexity, ellipsoid method",
author = "{de Klerk}, Etienne and Frank Vallentin",
year = "2016",
month = "9",
doi = "10.1137/15M103114X",
language = "English",
volume = "26",
pages = "1944--1961",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

On the Turing model complexity of interior point methods for semidefinite programming. / de Klerk, Etienne; Vallentin, Frank.

In: SIAM Journal on Optimization, Vol. 26, No. 3, 09.2016, p. 1944-1961.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

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

AU - de Klerk, Etienne

AU - Vallentin, Frank

PY - 2016/9

Y1 - 2016/9

N2 - 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.

AB - 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.

KW - semidefinite programming

KW - interior point method

KW - Turing model complexity

KW - ellipsoid method

U2 - 10.1137/15M103114X

DO - 10.1137/15M103114X

M3 - Article

VL - 26

SP - 1944

EP - 1961

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 3

ER -