I am reading a book about semidefinite programming that states the following:
Every semidefinite program can be solved in polynomial time, up to desired accuracy $\epsilon$.
Is this true? And how we can do it?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityI am reading a book about semidefinite programming that states the following:
Every semidefinite program can be solved in polynomial time, up to desired accuracy $\epsilon$.
Is this true? And how we can do it?
Sort of, if you mean complexity in terms of number of operations. In a stronger notation where you take representation of the involved numbers into account, I think complexity is still unknown if memory serves me right (Ramana 1995, An Exact Duality Theory for Semidefinite Programming and its Complexity Implications)
A related example
\begin{equation} \min_y {y_n} \text{ subject to } {y_1 = 1, \begin{bmatrix} y_i & y_{i-1}\\y_{i-1} & \frac{1}{2} \end{bmatrix}\succeq 0,~i = 2\ldots n} \end{equation}
Nice simple trivial SDP. However, the optimal solution here will be $y_i = 2^{2^{i-1}-1}$, i.e. if you represent numbers in your solution algorithm with standard integers (of course not possible in general), the number of bits required to represent the solution will be exponential in $n$. Same if you use standard floating-point representation as the power still is exponential.
Primal-dual interior-point methods can be used to solve SDP's in a polynomial number of iterations. If you count arithmetic operations (and ignore the bit level complexity of operations on arbitrary precision numbers) then each iteration can be done in polynomial time. This model of computation most accurately reflects practical computation with floating point arithmetic.
Another minor technical caveat is that the SDP needs to satisfy a constraint qualification such as Slater's condition.
See
Yurii Nesterov and Arkadii Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, SIAM, 1993.
In the bit number model of computation, Semidefinite programs can be solved in polynomial time to an arbitrary prescribed precision in the bit model using the ellipsoid method since it is a convex minimization problem.
In the real number model, interior point algorithms for semidefinite programming are shown to be polynomial (assuming Slater's condition holds). In the case that Slater condition fails, then the complexity of interior point algorithms for SDP in the real number model is still open.
Correct me if I am wrong. reference: Semidefinite Programming and Integer Programming Monique Laurent ∗ and Franz Rendl