I run into the following reading some optimization papars:

$$\min_x x^TAx $$ where $x\in\{-1,1\}^n$ and $A\in S_n$, Is equivalent to $$ \min <X,A>$$ s.t $diag(X) = (1,1,...,1)\;\; rank(X) = 1$. I guess $<.,.>$ is the Frobenius scalar product. How can we see that those are the same? Through the Lagrangian? Sorry for bad Latex I could not find anywhere how to write in optimization problems.

  • $\begingroup$ I don't get it, $x\in \{-1,1\}$? If that's the case, in order to $x^TAx$ be defined it's necessary that $A$ is a $1\times 1$ matrix. Is that the case? And if it is, then $x^TAx=A$, for any $x\in \{-1,1\}$. $\endgroup$ – Git Gud Jan 12 '13 at 13:26
  • $\begingroup$ sorry for the typos, you understand now? $\endgroup$ – Johan Jan 12 '13 at 13:34
  • $\begingroup$ The commands for angle brackets are \langle and \rangle. For operator names that are not built into LaTeX, use \operatorname{diag}. $\endgroup$ – user53153 Jan 12 '13 at 23:42

Notice that in general $(A \in S_n)$

$$\min_x x^TAx = \min_x tr(x^TAx) = \min_x tr(Axx^T)=\min_X \langle A,X \rangle,$$ where $X=xx^T$ so obviously $rank(X)=1$. Now the following sets in $\mathbb{R}^n$ $\{x:x_i\in\{-1,1\}\},\{x:x^2_i=1\},\{x:\operatorname{diag}(xx^T)=1\}$ are equivalent so therefore the constraint $x\in\{-1,1\}^n$ is equivalent to $\operatorname{diag}(X) = (1,1,...,1)$. It follows that the problems are equivalent.


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.