4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Right- the polynomial time complexity is in terms of the number of iterations, and the work per iteration is polynomial if you count floating point arithmetic operations as unit operations. $\endgroup$ – Brian Borchers Jan 24 '18 at 21:42
4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you for the link to the textbook. Could you expand on the technical caveat you have mentioned? Is it necessary/sufficient to check that strong duality holds to ensure that the number of iterations is polynomial in the size of the program? $\endgroup$ – user1936752 Jan 5 '20 at 15:53
  • 1
    $\begingroup$ Slater's condition is satisfied if there is a strictly feasible solution to the problem. That is, there is a positive definite (not just positive semidefinite) matrix $X$ that satisfies the linear equation constraints $A(X)=b$. If Slater's condition (or some other constraint qualification) isn't satisfied, then the the primal and dual optimal values may not be equal, the optimal values might not be attained, etc. Unfortunately, many SDP that arise in practice fail to satisfy Slater's condition. $\endgroup$ – Brian Borchers Jan 5 '20 at 16:29
  • $\begingroup$ Thank you. And if Slater's condition holds, is one guaranteed polynomial time convergence? $\endgroup$ – user1936752 Jan 5 '20 at 23:47
  • 1
    $\begingroup$ Yes. if Slater's condition holds than the primal-dual interior point method converges to an $\epsilon$ approximate solution in a polynomial number of iterations. $\endgroup$ – Brian Borchers Jan 6 '20 at 1:00
  • $\begingroup$ The complexity analysis that people working in optimization use is iteration complexity rather than bit-level complexity- it's a more realistic model for computations that are done in limited (double) precision floating-point arithmetic. $\endgroup$ – Brian Borchers Mar 26 '20 at 14:08
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy