3
$\begingroup$

Let $x \succ y $ be the majorization pre-order on real vectors. (Wikipedia link)

We say a function from real vectors to the reals is Schur convex if $x\succ y$ implies $f(x) ≥ f(y)$. With the result that if $x \succ y$ the vector $y$ is in the convex hull of permutations of $x$ is is easy to show that each convex and symmetric function is Schur convex.

Wikipedia states that the converse is not true (link). However each Schur-convex function is supposed to be symmetric.

Can anyone provide an example of a Schur-convex function that is not convex?

I know about the extra condition

$$(x_1 - x_2)\left(\frac{\partial{f}}{\partial{x_1}} - \frac{\partial{f}}{\partial{x_2}}\right) \le 0$$

for Schur-convexity but failed to construct a counter example with it for now. Maybe just some intuition is missing on how to use it?

$\endgroup$
  • $\begingroup$ $f(x)=\log\sum_i x_i$, perhaps? $\endgroup$ – Michael Grant Feb 28 '15 at 23:14
  • $\begingroup$ Also: $f(x)=-\prod_i x_i$ (defined for positive $x$). $\endgroup$ – Michael Grant Feb 28 '15 at 23:17
  • 1
    $\begingroup$ @Michael While the $\log \sum_i x_i$ seems to me quite convex (as log of a convex function?) the second one does the job. Thank you! Do you want provide it as an answer? So i could accept it. $\endgroup$ – Permutation Mar 1 '15 at 11:20
  • 1
    $\begingroup$ @Permutation $\log x$ is not convex... $\endgroup$ – Macavity Mar 1 '15 at 12:17
  • $\begingroup$ The logarithm is definitely not convex. Indeed it seems to me that your stumbling block is an improper understanding of convexity, if you think that the log of a convex function should automatically be convex. $\endgroup$ – Michael Grant Mar 1 '15 at 15:09
3
$\begingroup$

Here's a straightforward way to construct a counterexample.

  1. Select any nondecreasing non-convex real scalar function: $\log x$, $\sqrt{x}$, $-e^{-x}$, $\min\{x,0\}$, $x^3$, etc. Note that the first two of these are defined for positive/nonnegative $x$.
  2. Apply that function to $\sum_i x_i$: $\log \sum_i x_i$, $\sqrt{\sum_i x_i}$, $-e^{-\sum_i x_i}$, $\min\{\sum_i x_i,0\}$, $\left(\sum_i x_i\right)^3$, etc.

The resulting functions are Schur-convex but not convex. That said, they are somewhat trivially Schur-convex, because $f(x)=f(y)$ if $\sum_i x_i=\sum_i y_i$, and the remaining conditions for majorization are irrelevant. In particular, they are not strictly Schur-convex.

$f(x)=-\prod_i x_i$ is an example that doesn't fit this mold, and is non-trivially Schur convex. Note that $f(x)=-\left(\prod_i x_i\right)^{1/n}$ is actually concave in $x$.

$\endgroup$
  • 1
    $\begingroup$ May i add a suggestion how to generate examples that are strictly Schur-convex but not convex? Wouldn't this be possible by replacing in your step 2 the $\sum_i x_i$ by any strictly Schur-convex function like $\sum_i x_i^2$ for example? (And in addition choosing in step 1 an increasing function.) $\endgroup$ – Permutation Mar 2 '15 at 0:10
  • $\begingroup$ Yes, it would seem to me something like that will work, some of the time. There will be certain cases where the composition will happen to turn out convex, though. For instance, $\sqrt{x}$ composed with $\sum_i x_i^2$ is the Euclidean norm! and therefore convex. The minimum and the cube will also be convex in that case. $\endgroup$ – Michael Grant Mar 2 '15 at 3:42

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.