Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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\}$. –  Git Gud Jan 12 '13 at 13:26
sorry for the typos, you understand now? –  Johan Jan 12 '13 at 13:34
The commands for angle brackets are \langle and \rangle. For operator names that are not built into LaTeX, use \operatorname{diag}. –  user53153 Jan 12 '13 at 23:42
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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