10
votes
Accepted
When is the duality gap of semidefinite programming (SDP) zero?
There is a more complicated theory of duality for SDPs that is exact: there is no 'extra condition' like Slater's condition. This is due to Ramana. (For another take on this involving SOS, see [KS12]...
- 1,801
9
votes
When is the duality gap of semidefinite programming (SDP) zero?
For the SDP in standard form
$$
\min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\},
$$
Slater's condition reduces to the existence of a positive ...
- 18.1k
9
votes
Accepted
Positivstellensatz and sum of squares method
As already noted in the comments, the question is based on a misunderstanding; the actual Positivstellensatz is a stronger statement than Artin’s theorem on nonnegative polynomials, and the real ...
- 16.9k
6
votes
Accepted
How is SDP an extension of spectral algorithms?
This is not a precise statement so it's hard to give a precise answer, but I think what is meant is that SDPs are powerful enough to express both linear programs, and problems like "compute the ...
- 18.1k
5
votes
Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?
Theorem. The problem in the post is NP-hard, by reduction from Subset-Sum.
Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op.
Here is the intuition. ...
- 9,595
3
votes
Accepted
What is wrong with this procedure to convert quadratic programming to convex quadratic programming?
The constraint $x_i x_j = y_{ij}$ isn't convex. Indeed, even the simpler constraint $ab = 8$ isn't convex. Let $C = \{(a,b) : ab = 8\}$. Then $(4,2),(2,4) \in C$ but $(3,3) \notin C$.
- 14.3k
3
votes
SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?
We don't have integrality gaps even for Max-CUT, even for degree 4. See Barak and Steurer's notes, at the end.
You might be interested in Lee Raghavendra Steurer '14. They seem to be saying there can ...
- 513
3
votes
Accepted
Approximation algorithm for balanced bipartite independent set?
There is a nice reduction by Chalermsook et al. (WG 2020) that can give the kind of approximation you want. I'll describe it below in terms of finding balanced complete bipartite subgraph (biclique) ...
- 306
3
votes
Accepted
Max-k-cut with negative edge weights
There is no approximation algorithm for the problem of maximizing $\sum_{(i,j)\text{ is cut}} w_{ij}$, since it's even NP-hard to determine whether the optimal value is positive. However, there is a ...
- 3,899
1
vote
Solving non-linear programming with large number of variables
This is a quadratic program (QP). If the matrix $C$ where $(C)_{i,j} = c_{i,j}$ is positive semi definite, then the problem is convex. It seems that your problem should have non-empty interior, so if ...
- 226
1
vote
When is the duality gap of semidefinite programming (SDP) zero?
There is a nice (I think....) characterization of when strong duality holds, or fails for {\em all} objective functions.
We say that the semidefinite {\em system}
$(P_{SD}) \,\, \sum_{i=1}^m x_i ...
- 11
1
vote
Brute force search algorithm for semidefinite programming (representation of spectrahedron)
The question is not very well defined. E.g., if the SDP has an optimal solution, then "searching" that one optimal solution is (trivially) enough to find a good approximate (in fact optimal) solution....
- 9,595
1
vote
Optimal value of a semidefinite program
Here are a few more details for Suresh and Yoshio's answer. Following e.g. https://en.wikipedia.org/wiki/Semidefinite_programming, an SDP is of the form
$$\begin{array}{rl}
{\displaystyle\min_{X \in \...
- 9,595
Only top scored, non community-wiki answers of a minimum length are eligible