DIMACS TR: 96-18

On the Complexity of Semidefinite Programs

Authors: Lorant Porkolab and Leonid Khachiyan


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 over $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 $(n,m)$ has a solution $\M{X}$ such that $\log \|\M{X}\| \le ln^{O(\min\{m,n^2\})}$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-18r.ps.gz
DIMACS Home Page