1
$\begingroup$

From Boyd & Vandenberghe's Convex Optimization:

Suppose $G=\{Q_1,\cdots Q_k\}\subset R^{n\times n}$ is a group. We say that the function $f$ is $G$ invariant or symmetric with respect to $G$ if $f(Q_ix)=f(x)$ holds for all $x$ and $i\in \{1,\cdots k\}$. We define $\bar{x}=(\frac{1}{k})\sum_{i=1}^kQ_ix$, which is the average of $x$ over its $G$-orbit. We define the fixed subspace of $G$ as

$F=\{x, \text{such that } Q_ix=x, i\in\{1,\cdots k\}\}$.

Part d: As an example, suppose $f$ is convex and symmetric for every permutation $P$. Show that if $f$ has a minimizer then it has a minimizer of the form $\alpha [1, 1,\cdots 1]$.

Its solution is as follows:

Suppose $x^*$ is a minimizer of $f$. Let $\bar{x}=\frac{1}{n!}\sum_{P}Px^*$ where the sum is over all permutations. Since $\bar{x}$ is invariant under any permutation we conclude that $\bar{x}=\alpha [1,\cdots,1]$ for some $\alpha$ on real line. (I really do not understand this last sentence how to show that it its true. Any help in this regard will be much appreciated. Thanks in advance.)

$\endgroup$
8
  • 1
    $\begingroup$ All the last sentence is saying is that since the vector $\bar{x}$ never changes if you permute (re-order) its elements, it must be a vector where every element is the same. Can you show this? (If not, consider what would happen if two of the elements happened to be different and you applied a certain permutation of the elements...) Also, make sure you understand why $\bar{x}$ is invariant under any permutation! $\endgroup$ Apr 13 '19 at 11:07
  • $\begingroup$ @MinusOne-Twelfth thank you so much for the prompt response. $\endgroup$ Apr 13 '19 at 11:10
  • $\begingroup$ @MinusOne-Twelfth yes they have explained it in the part (a) of the question. But I have a little confusion about that too. I think that it is assumed in the solution that for a fixed $Q_j$, $Q_jQ_i$ is different for all $i$'s. Is it true? $\endgroup$ Apr 13 '19 at 11:13
  • $\begingroup$ @FrankMoses (d) is a special case. For a general group you don't have the result for (d). $\endgroup$ Apr 13 '19 at 11:22
  • 1
    $\begingroup$ @FrankMoses Group theory time: suppose ab = ac, do we know b=c? Yes, multiply on the left by $a^{-1}$. So yes, if b!=c, then ab!=ac. $\endgroup$ Apr 13 '19 at 11:33
1
$\begingroup$

You put all the permutations in a matrix, with each permutation as a row. You take sums column-wise. Do all the sums equal? Yes, because each column contains the same number of each element of $x^*$. Convince yourself that the number permutations with $x^*_1$ in slot 1 is the the same as that with $x^*_1$ in slot 2, and so on ...

$\endgroup$

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.