ON THE TURING MODEL COMPLEXITY OF INTERIOR POINT METHODS FOR SEMIDEFINITE PROGRAMMING

被引：21

作者：

de Klerk, Etienne ^{[1
]}

Vallentin, Frank ^{[2
]}

机构：

[1] Tilburg Univ, Fac Econ Sci, Dept Econometr & Operat Res, NL-5000 LE Tilburg, Netherlands

[2] Univ Cologne, Math Inst, Weyertal 86-90, D-50931 Cologne, Germany

来源：

SIAM JOURNAL ON OPTIMIZATION | 2016年 / 26卷 / 03期

关键词：

semidefinite programming; interior point method; Turing model complexity; ellipsoid method; FINITE-PRECISION;

D O I：

10.1137/15M103114X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：1944 / 1961

页数：18

共 23 条

[1]

[Anonymous], 1979, Sov. Math. Dokl

[2]

[Anonymous], 2012, APPROXIMATION ALGORI

[3]

[Anonymous], 1998, Theory of linear and integer programming

[4]

de Klerk E, 2007, MATH PROGRAM, V109, P613, DOI 10.1007/s10107-006-0039-7

[5] UPPER BOUNDS FOR PACKINGS OF SPHERES OF SEVERAL RADII [J].

Delaat, David ;

De Oliveira Filho, Fernando Mario ;

Vallentin, Frank .

FORUM OF MATHEMATICS SIGMA, 2014, 2

[6] Some characterizations and properties of the "distance to ill-posedness" and the condition measure of a conic linear system [J].

Freund, RM ;

Vera, JR .

MATHEMATICAL PROGRAMMING, 1999, 86 (02) :225-260

[7] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J].

Goemans, MX ;

Williamson, DP .

JOURNAL OF THE ACM, 1995, 42 (06) :1115-1145

[8] THE ELLIPSOID METHOD AND ITS CONSEQUENCES IN COMBINATORIAL OPTIMIZATION [J].

GROTSCHEL, M ;

LOVASZ, L ;

SCHRIJVER, A .

COMBINATORICA, 1981, 1 (02) :169-197

[9]

Grotschel M., 1988, GEOMETRIC ALGORITHMS

[10] Primal-dual interior-point methods for semidefinite programming in finite precision [J].

Gu, M .

SIAM JOURNAL ON OPTIMIZATION, 2000, 10 (02) :462-502

← 1 2 3 →