3
$\begingroup$

Let's say that we want to design a semi-definite programming approximation for an optimization problem such as MAX-CUT or MAX-SAT or what have you.

So, we first write down an integer quadratic program that solves the problem exactly. For example, in the case of MAX-CUT we would write: $$ \max \sum_{\{u,v\} \in E}{\frac{1 - x_u x_v}{2}} $$ $$ x_v \in \{-1,+1\}. $$

Then we relax the program by allowing the variables to take on vector values in the sphere $S^{n-1}$, and replacing products with scalar products, obtaining a semi-definite program that can be solved precisely.

Our approximation proceeds by solving the SDP and rounding the solution to obtain a legal solution for the original problem whose distance from the SDP solution can be bounded.

My question is: What is the importance of the dimension of the vectors? In all the cases I have seen, the analysis would stay the same if we assume that the vectors are all unit vectors in $\mathbb{R}^2$. So why do people always take vectors in $S^{n-1}$?

$\endgroup$
  • 3
    $\begingroup$ (1) The reduction of the relaxation to SDP requires that the vectors be in R^n (if you restrict the vectors to a smaller space you don't get an SDP). (2) I believe (?) that, if you constrain the vectors to a space smaller than R^(n-1), then the relaxation can give you a better approximation ratio, and (in general) remains NP-hard. $\endgroup$ – Neal Young May 31 '14 at 15:28
  • 1
    $\begingroup$ @NealYoung: Turn into an answer? $\endgroup$ – Louis May 31 '14 at 21:20
  • $\begingroup$ Essentially the same question is asked in this later post: cs.stackexchange.com/questions/86043/… $\endgroup$ – Neal Young Jan 10 '18 at 14:03
2
$\begingroup$

Vector programs are solved by solving semidefinite programs. The basic idea is that if $v_1,\ldots,v_n$ are vectors, then the matrix $V_{ij} = \langle v_i,v_j \rangle$ is positive semidefinite: $$ \alpha' V \alpha = \sum_{i,j} \alpha_i \alpha_j \langle v_i, v_j \rangle = \left\|\sum_i \alpha_i v_i\right\|^2. $$ The converse is also true: a positive semidefinite $n \times n$ matrix $V$ of rank $r$ can be written as $V = LL'$, where $L$ is $n \times r$ (this is known as the Cholesky decomposition). Furthermore, $L$ can be found effectively given $V$. If $\ell_1,\ldots,\ell_n$ are the $r$-dimensional rows of $L$, then $V_{ij} = \ell_i \ell'_j = \langle \ell_i, \ell_j \rangle$. We can therefore optimize a vector program involving inner products of vectors $v_i$ by solving a semidefinite program. Rank constraints are not convex, and so we cannot really control the dimension of the vectors other than the trivial bound $n$.

As you mention, the analysis in the particular case of MAX-CUT only uses the two-dimensional projections. This shows that even if you could somehow guarantee that $\operatorname{rank} V = 2$ (recall that the rank corresponds to the dimension), the analysis wouldn't get better. On the other hand, if you could guarantee than $\operatorname{rank} V = 1$, you will have solved MAX-CUT exactly. This shows that the latter constraint is NP-hard to realize. It is probably the case that any non-trivial rank constraint cannot be enforced in polynomial time, and any constant rank constraint is NP-hard.

$\endgroup$
  • $\begingroup$ Thanks! I forgot/ didn't understand the significance of the fact that we solve vector programs like the above via optimization over a positive semidefinite matrix and then performing a Cholesky decomposition. $\endgroup$ – Zur Luria Jun 1 '14 at 9:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.