On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming.

Etienne de Klerk, Frank Vallentin

Research output: Working paperOther research output

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.
Original language English Ithaca Cornell University Library 16 https://doi.org/10.1137/15M103114X Published - Jul 2015

Publication series

Name arXiv 1507.03549

Fingerprint

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

Keywords

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

Cite this

de Klerk, E., & Vallentin, F. (2015). On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming. (arXiv; Vol. 1507.03549). Ithaca: Cornell University Library. https://doi.org/10.1137/15M103114X
de Klerk, Etienne ; Vallentin, Frank. / On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming. Ithaca : Cornell University Library, 2015. (arXiv).
@techreport{137262a3555245f9b41f212a67376587,
title = "On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming.",
abstract = "It is known that one can solve semidenite programs to withinxed accuracy in polynomial time using the ellipsoid method (under someassumptions). In this paper it is shown that the same holds true when one usesthe short-step, primal interior point method. The main idea of the proof is toemploy Diophantine approximation at each iteration to bound the intermediatebit-sizes of iterates.",
keywords = "semidefinite programming, interior point method, Turing model complexity, ellipsoid method",
author = "{de Klerk}, Etienne and Frank Vallentin",
year = "2015",
month = "7",
doi = "https://doi.org/10.1137/15M103114X",
language = "English",
series = "arXiv",
publisher = "Cornell University Library",
type = "WorkingPaper",
institution = "Cornell University Library",

}

Ithaca : Cornell University Library, 2015. (arXiv; Vol. 1507.03549).

Research output: Working paperOther research output

TY - UNPB

T1 - On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming.

AU - de Klerk, Etienne

AU - Vallentin, Frank

PY - 2015/7

Y1 - 2015/7

N2 - It is known that one can solve semidenite programs to withinxed accuracy in polynomial time using the ellipsoid method (under someassumptions). In this paper it is shown that the same holds true when one usesthe short-step, primal interior point method. The main idea of the proof is toemploy Diophantine approximation at each iteration to bound the intermediatebit-sizes of iterates.

AB - It is known that one can solve semidenite programs to withinxed accuracy in polynomial time using the ellipsoid method (under someassumptions). In this paper it is shown that the same holds true when one usesthe short-step, primal interior point method. The main idea of the proof is toemploy Diophantine approximation at each iteration to bound the intermediatebit-sizes of iterates.

KW - semidefinite programming

KW - interior point method

KW - Turing model complexity

KW - ellipsoid method

U2 - https://doi.org/10.1137/15M103114X

DO - https://doi.org/10.1137/15M103114X

M3 - Working paper

T3 - arXiv

BT - On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming.

PB - Cornell University Library

CY - Ithaca

ER -