×

zbMATH — the first resource for mathematics

On the complexity of semidefinite programs. (English) Zbl 0881.90127
Summary: We show that the feasibility of a system of \(m\) linear inequalities over the cone of symmetric positive semidefinite matrices of order \(n\) can be tested in \(mn^{O(\min\{m,n^2\})}\) arithmetic operations with \(ln^{O(\min\{m,n^2\})}\)-bit numbers, where \(l\) is the maximum binary size of the input coefficients. We also show that any feasible system of dimension \((m,n)\) has a solution \({\mathbf X}\) such that \(\log|{\mathbf X}|\leq ln^{O(\min\{m,n^2\})}\).

MSC:
90C60 Abstract computational complexity for mathematical programming problems
PDF BibTeX XML Cite
Full Text: DOI