18

A typical problem is MaxCut: output a cut in a graph that (approximately) maximizes the number of edges cut. Goemans and Williamson showed an SDP approximates the value of MaxCut to within a factor at least 0.878. Recently, Chan, Lee, Raghavendra, and Steurer showed that for a natural linear encoding of the MaxCut problem, all polynomial size LPs achieve ...


16

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: Semidefinite Programming. Vandenberge and Stephen Boyd, 1996.


15

No, even if there is a finite number of feasible rank-1 matrices, the feasible region of an SDP does not have to be polyhedral. A spectrahedron you see all the time in applications is $S_n = \{X: X \succeq 0, X_{11} = \ldots = X_{nn} = 1\}$, i.e. the set of Gram matrices of $n$ unit vectors. This is, for example, the feasible region for the Goemans-...


15

There are many examples in quantum information and computation where quantities of interest are expressible as optimal values of semidefinite programs. Here are a few beyond those mentioned in the question: The optimal probability to correctly distinguish states chosen from a known ensemble is expressible as an SDP. (See arXiv:quant-ph/0205178 .) The ...


13

It depends how the polytope is represented. In the V-polytope presentation (i.e. $P$ is given in terms of its vertices), the problem is trivial, as Tim mentioned in the comments. In the H-polytope presentation (i.e. $P$ is given as an intersection of halfspaces defined by inequalities), Brieden proved that a constant factor approximation is impossible ...


12

For many combinatorial optimization problems (for instance Max-Cut), semidefinite programming yields much stronger relaxations than the LP relaxation of IP formulations. This allows the design of approximation algorithms, and of exact algorithms which are more efficient than their linear counterparts due to the better quality of the bounds. Examples can be ...


10

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].) To be honest, I've never tried to understand these papers and would be happy if someone dumbed them down for me. One notable consequence of this work is ...


9

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 definite $X\succ 0$ that satisfies the affine constraints $\mathrm{tr}(A_i^T X) = b_i$. I would guess this is satisfied for any SDP you can find in the ...


8

From any choice of a polytope $P$ in ${\mathbb R}^k$, $\epsilon$, and a point $q$ in ${\mathbb R}^k$ it is possible to find a polytope $\hat P$ in ${\mathbb R}^{k+1}$, together with an embedding of ${\mathbb R}^k$ into ${\mathbb R}^{k+1}$, such that $\hat P$ is within $\epsilon$ Hausdorff distance of (the embedded image of) $P$ and such that (the embedded ...


8

To make it easier let's assume $X$ is finite, of size $n$ and associate the density of $Q$ with an $n$-dimensional vector $q$. Assume also that $q$ is everywhere positive - otherwise replace $X$ with the support of $q$. Then the conjugate is $$ f^*_q(x) = \sup_p\ \langle x, p \rangle - \sum_{i = 1}^n{p_i\log(p_i/q_i)}. $$ where the supremum is over the ...


7

For your second question, the number of bits is $O(n^2 \log n)$ (i.e. $O(n\log n)$ per coefficient) and there are examples where it is $\Omega(n^2\log n)$, i.e. the bound is tight. See Corollary 26 here. The ideas are standard, and anyone who has seen an analysis of the ellipsoid algorithm will be familiar with this. Say you have a facet in the hyperplane ...


6

Answer: $\alpha = - 1/(k-1)$. This value is attained when vectors $v_i$ are the vertices of a regular simplex, centered at the origin. This follows from symmetry: given a set of vectors $u_i$ consider new vectors $u_i'= \frac{1}{\sqrt{k}}\left( u_i \oplus u_{i+1} \oplus \dots \oplus u_{i-1} \right)$ (where we add up all vectors $u_i$ in the cyclic order ...


6

This seems to be NP-hard to do exactly, by reduction from subset sum. Suppose we had an efficient procedure to compute $O$. Given positive integers $v_1,\dots,v_n$ encoded in binary, we wish to test whether there is a subset summing to $s$. Preprocess by throwing out any integers larger than $s$. Call the procedure to obtain a small set $O$ of points ...


6

In Quadratic Programming is in NP, it is shown that a slight variant of this problem (QPL) is in NP. The question can be formulated as follows: does there exist a point $x \in \mathbb{R}^n$ such that $ Ax \leq b $ and $x^T Q x \leq K$, where $K$ is a rational number. In the section 2 of this paper, they prove that, when the minimum exists, then there is a ...


6

Well, there are cases where LP gives you no useful information. Consider a graph $G$ with $n$ vertices, and the problem of finding a maximum independent set in $G$. The LP gives you a solution of value at least $n/2$ (give every vertex a value of $1/2$). But the optimal independent set might be of size between $1$ and $n$. On the other hand, the greedy ...


6

A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints. In particular, they prove: Let $G$ be a graph with vertices $1,\ldots,n$ and edge set $E$. Then $G$ contains a $k$-clique, if and only if there exist real numbers $x_1,\ldots,x_n$ that ...


5

Consider the plane through the points $(1,0,0,0)$, $(0,1,0,0)$, $(0,0,1,0)$, $(1,1,1,1)$. If you add the origin to this set of points, the hyperplane is a facet of the convex hull. The equation is $x_1 + x_2 + x_3 - 2x_4 = 1$. The coefficient on $x_4$ is not $0$ or $\pm 1$.


5

The problem you describe is called "stochastic convex optimization in the bandit setting". This is the problem considered and solved here: http://arxiv.org/pdf/1107.1744v2.pdf They show that after $k$ queries, you can get within $O(1/\sqrt{k})$ of the minimum value of the function (ignoring a poly$(d)$ dependence on the dimension $d$ of the domain of the ...


5

In 1998, Michel X. Goemans gave an ICM talk, in which, he addressed this issue:"Semidefinite programs can be solved(or more precisely, approximated) in polynomial-time within any specific accuracy either by the ellipsoid algorithm or more efficiently through interior-point algorithms...The above algorithms produce a strictly feasible solution(or slightly ...


4

First, notice that the first objective is a minimization problem, who's solution is a vector $x$, while the second is merely a number. The objective $\min_{x} E\left( \parallel Ax-b \parallel_2^2 \right)$ asks for the vector $x$ which best explains the data. If $A$ is stochastic, it still looks for the best $x$ which, on average, is the best one. The ...


4

Your problem in revision 3 of the question is NP-hard by a reduction from the vertex cover problem. Slightly more precisely, even if aip’s are restricted to 0 or 1, it is NP-complete to decide whether the maximum value in the question is equal to N or less than N. (Note that the maximum value cannot be greater than N if aip’s are 0 or 1.) The detail is ...


4

The books below may be more to your liking, but in general, the texts/lecture notes are written for the use of (mainly) postgraduate students in engineering and cannot presume deep knowledge of convex analysis. Csizsar, I., and Korner, J., Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd Ed, Cambridge. Berger, T., Rate Distortion ...


4

The notion of sub-modularity you use is non-standard. Usually you consider set functions with domain $\lbrace 0, 1\rbrace^n$. But to answer your questions, the Lovász extension establishes the following relationship between sub-modularity and convexity: A set-function $F$ is sub-modular if and only if its Lovász extension $f$ is convex. For a proof see ...


4

Introduce variables $y_{hi}$ together with constraints $y_{hi}=\sum_j (a_{hij} x_j + b_{hj})$ for all $h$ and $i$. Introduce variables $z_h$ together with constraints $z_h\ge y_{hi}$ for all $h$ and $i$. Then minimize $\sum_h z_h$. The resulting linear program can be solved in time polynomially bounded in $\ell, m, n$ and the logarithm of the largest cost ...


4

$\chi^2$-divergence is not a Bregman divergence. I'll show it for sample size $n=1$. We would have $$ (x-y)^2/x=f(x)-f(y)-f'(y)(x-y)$$ If $y=0$ and $x>0$ this says $$x=f(x)-f(0)-xf'(0),$$ $$1=\frac{f(x)-f(0)}x-f'(0).$$ Taking $x\to 0^+$ this gives the contradiction $1=0$.


3

If I understand your problem correctly, we can formulate it like so: given pairs $(\alpha_k,\beta_k)$ and $\Delta_0$, find $s > 0$ such that $\max_k (s\alpha_k + \beta_k) = \Delta_0$. Here is one way to solve this (this algorithm can be made more efficient). Go over all possible $k$. For each $k$, find the value of $s$ such that $s\alpha_k + \beta_k = \...


3

The problem as stated now is solvable in linear time. To see this, suppose $p\in P$ is such that there are $x\in X$ and $w\in W$ with $p_i=x_iw_i$ for all $i$. This means on the one hand that $1=\sum_{i=1}^np_i=\sum_{i=1}^nx_iw_i$, but on the other hand because of $1 = \sum_{i=1}^nx_i$ and $1 = \sum_{i=1}^nw_i$ we have $1 = \sum_{i=1}^n\sum_{j=1}^nx_iw_j$, ...


3

Sasho already gave you a yes/no answer, but here's an actual convex combination for you: If $B_\ell$ is the $k \times k$ matrix which is $1$ when $|S_i \cap S_j| \ge \ell$ and zero otherwise, then $M = \sum_{\ell=1}^{n'} \frac{1}{n'} B_\ell$.


3

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


2

Arnaud is correct. The critical piece I was missing is that for any $z$, $z^\top x > 0 \iff z^\top x / \|x\| > 0.$ So pick $z \in S$. Let $x_0 = \text{arg inf } \{ z^\top x \mid x \in \text{cl}(K) \cap \{0\}, \|x\|=1 \}$ and let $c_{x_0} = z^\top x_0 > 0$. We know $x_0$ exists because the set $\text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ is closed and ...


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