<p>The ellipsoid method and interior point methods can be extended to solve SDPs as well. You can refer to any standard-texts on SDPs for details. Here's one:</p>
<ul>
<li>Lieven Vandenberghe, Stephen Boyd, <a href="https://web.stanford.edu/%7Eboyd/papers/pdf/semidef_prog.pdf" rel="nofollow noreferrer">Semidefinite Programming</a>, SIAM Review, Volume 38, Number 1, March 1996.</li>
</ul>

CC BY-SA 3.0
2013-03-15T21:40:03.623Z
Nice reference too! Thanks! Was wondering when saying polynomial time algorithm solving SDP, are the algorithms solving for the optimal solution, exactly or approximately?
Tim
CC BY-SA 4.0
2012-11-30T07:04:34.190Z
2023-12-20T15:52:56.603Z
2023-12-20T15:52:56.603Z
Jagadish
<p>We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (exponential) number of variables/constraints can also be solved in polynomial time, provided we can design a polynomial time separation oracle for them.</p>

<p>What about semidefinite programs (SDP)? What classes of SDPs can be solved exactly in polynomial time? When an SDP can't be solved exactly, can we always design an FPTAS/PTAS for solving it? What are the technical conditions under which this can be done? Can we solve an SDP with exponential number of variables/constraints in polynomial time, if we can design a polynomial time separation oracle for it?</p>

<p>Can we solve the SDPs that occur in combinatorial optimization problems (MAX-CUT, graph coloring) efficiently? If we can solve only within a $1+\epsilon$ factor, will it not have an effect on constant factor approximation algorithms (like 0.878 for Goemans-Williamson MAX-CUT algorithm)?</p>

<p>Any good reference on this will be highly appreciated.</p>

CC BY-SA 3.0
2012-11-30T07:07:03.033Z
In fact the method works for convex programming in general
Suresh Venkat
CC BY-SA 3.0
2012-11-30T11:38:44.017Z
There are even libraries for SDP solving available.
adrianN
CC BY-SA 3.0
2012-11-30T15:36:26.390Z
There are at least two reasons you can't solve a general SDP in polynomial time. (1) There exist SDPs whose solution is exponential sized. (2) SDPs can encode the sum of square roots problem, which is not known to be polynomial time solvable.
Robin Kothari
CC BY-SA 3.0
2012-11-30T17:15:53.537Z
@RobinKothari For SDPs, usually "solvable in polynomial time" is replaced by "gets within $\epsilon$ (additive) of OPT in time polynomial in $1/\epsilon$" IIRC. p.s how does an SDP encode sum-of-square-roots ?
Suresh Venkat
CC BY-SA 3.0
2012-11-30T18:40:32.447Z
@SureshVenkat: Say we have a 2x2 matrix with entries [a b; c d]. Impose that this is positive semidefinite and d = 1. This means b = c and a >= b^2. So b is upper bounded by the square root of a. Now we can maximize the sum of several such b's. The optimum value will be the sum of square roots of the respective a's.
Robin Kothari
CC BY-SA 3.0
2012-12-01T02:57:49.400Z
If we can solve only within a $1+\epsilon$ factor, will it not have an effect on constant factor approximation algorithms (like 0.878 for Goemans-Williamson MAX-CUT algorithm)?
Arindam Pal
CC BY-SA 3.0
2012-12-01T03:44:43.783Z
It's not multiplicative but additive. Also, http://en.wikipedia.org/wiki/Semidefinite_programming#Algorithms
Suresh Venkat
CC BY-SA 3.0
2015-12-10T14:56:50.777Z
Does the separation oracle approach work with interior point methods, or is this possible only for the ellipsoid algorithm?
G. Bach
CC BY-SA 4.0
2019-11-12T02:15:20.290Z
Question：Was wondering when saying polynomial time algorithm solving SDP, are the algorithms solving for the optimal solution, exactly or approximately? Answer：It is totally depend on your problem. If your SDP problem is convex, then the solution is exactly for your current problem.
Tong Wai
<optimization><linear-programming><convex-optimization><semidefinite-programming>
Solving semidefinite programs in polynomial time
Arindam Pal
# Solving semidefinite programs in polynomial time

(Asked by: username_0 on 2012-11-30)

We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (exponential) number of variables/constraints can also be solved in polynomial time, provided we can design a polynomial time separation oracle for them.

What about semidefinite programs (SDP)? What classes of SDPs can be solved exactly in polynomial time? When an SDP can't be solved exactly, can we always design an FPTAS/PTAS for solving it? What are the technical conditions under which this can be done? Can we solve an SDP with exponential number of variables/constraints in polynomial time, if we can design a polynomial time separation oracle for it?

Can we solve the SDPs that occur in combinatorial optimization problems (MAX-CUT, graph coloring) efficiently? If we can solve only within a $1+\epsilon$ factor, will it not have an effect on constant factor approximation algorithms (like 0.878 for Goemans-Williamson MAX-CUT algorithm)?

Any good reference on this will be highly appreciated.

**Tags:** optimization, linear-programming, convex-optimization, semidefinite-programming

> **Comments:**
> **username_1**: In fact the method works for convex programming in general  
> **username_2**: There are even libraries for SDP solving available.  
> **username_3**: There are at least two reasons you can't solve a general SDP in polynomial time. (1) There exist SDPs whose solution is exponential sized. (2) SDPs can encode the sum of square roots problem, which is not known to be polynomial time solvable.  
> **username_1**: @RobinKothari For SDPs, usually "solvable in polynomial time" is replaced by "gets within $\epsilon$ (additive) of OPT in time polynomial in $1/\epsilon$" IIRC. p.s how does an SDP encode sum-of-square-roots ?  
> **username_3**: @SureshVenkat: Say we have a 2x2 matrix with entries [a b; c d]. Impose that this is positive semidefinite and d = 1. This means b = c and a >= b^2. So b is upper bounded by the square root of a. Now we can maximize the sum of several such b's. The optimum value will be the sum of square roots of the respective a's.  
> **username_0**: If we can solve only within a $1+\epsilon$ factor, will it not have an effect on constant factor approximation algorithms (like 0.878 for Goemans-Williamson MAX-CUT algorithm)?  
> **username_1**: It's not multiplicative but additive. Also, http://en.wikipedia.org/wiki/Semidefinite_programming#Algorithms  
> **username_4**: Does the separation oracle approach work with interior point methods, or is this possible only for the ellipsoid algorithm?  
> **username_5**: Question：Was wondering when saying polynomial time algorithm solving SDP, are the algorithms solving for the optimal solution, exactly or approximately? Answer：It is totally depend on your problem. If your SDP problem is convex, then the solution is exactly for your current problem.  

---

## 1 answers

### Answer by username_6 on 2012-11-30. Score: 16 | Accepted answer

The ellipsoid method and interior point methods can be extended to solve SDPs as well. You can refer to any standard-texts on SDPs for details. Here's one:

* Lieven Vandenberghe, Stephen Boyd, [Semidefinite Programming](https://web.stanford.edu/%7Eboyd/papers/pdf/semidef_prog.pdf), SIAM Review, Volume 38, Number 1, March 1996.

> **Comments:**
> **username_7**: Nice reference too! Thanks! Was wondering when saying polynomial time algorithm solving SDP, are the algorithms solving for the optimal solution, exactly or approximately?  

---

