DIMACS TR: 96-18
On the Complexity of Semidefinite Programs
Authors: Lorant Porkolab and Leonid Khachiyan
ABSTRACT
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