# Tag Info

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]...

### 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 ...
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 ...
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 ...

### 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. ...
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$.

### 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 ...
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) ...
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 ...
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 ...
1 vote

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 ... 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.... 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 \...

Only top scored, non community-wiki answers of a minimum length are eligible