Symmetric functions and their extreme points

A symmetric function $f(x_1, \dots, x_n)$ is one that is invariant to permutations of $x$.  In the 2D case, this means $f(a,b) = f(b,a)$.  One basic example of a symmetric function is the area of a rectangle as a function of its side lengths, where $f(a,b) = a b$.  It is well known that to maximize the area of a rectangle under a constraint on the perimeter, you should set all side lengths equal, to form a square.  In this case, the maximum of this symmetric function occurs when $a=b$.

While in general it is not always true that the extreme points of a symmetric function occurs when $a=b$, there are special cases when it does hold.  For example, if $f(a,b)$ is a convex (concave) function, then a global minimum (maximum) will occur when $a=b$.  Of course, the function above is not concave, but this property still holds.  So the question arises: in what other situations does this nice property hold?

In this blog post, I will state a general result that I found today regarding this problem. I was studying a symmetric function I encountered in my research, and trying to argue that the minimum occurs when $a=b$, after conjecturing that this was true by checking empirically.  The main theorem is stated below:

Theorem. If $g,h$ are convex, non-negative functions, then a global minimum of the symmetric function $f(a,b) = g(a) h(b) + g(b) h(a) $ occurs when $a=b$.

Proof. It suffices to show that for any $a,b$, there exists a $c$ such that $f(c,c) \leq f(a,b)$.  This implies that a global minimum occurs when $a=b$, because for any $a \neq b$, the solution can be improved.  We prove the statement by separately considering 4 cases.

Case 1: If $g(a) \leq g(b)$ and $h(a) \leq h(b)$, then set $c=a$.  Clearly $f(c,c) \leq f(a,b)$ because both terms in the sum are smaller.
Case 2: If $g(a) \geq g(b)$ and $h(a) \geq h(b)$, then set $c=b$.  Clearly $f(c,c) \leq f(a,b)$ because both terms in the sum are smaller.
Case 3: If $g(a) \leq g(b)$ and $h(a) \geq h(b)$, then set $c = \frac{a+b}{2}$.

$$\begin{align*}
f(c,c) &= 2 g(c) h(c) \\
&\leq 2  \Big[\frac{1}{2} g(a) + \frac{1}{2} g(b)\Big] \Big[\frac{1}{2} h(a) + \frac{1}{2} h(b) \Big] \\
&= \frac{1}{2} g(a) h(a) + \frac{1}{2} g(a) h(b) + \frac{1}{2} g(b) h(a) + \frac{1}{2} g(b) h(b) \\
&\leq g(a) h(b) + g(b) h(a) \\
\end{align*}$$

Above, the first inequality follows from the convexity and non-negativity of $g$ and $h$, and the second inequality follows from the assumptions of case $3$.

Case 4: If $g(a) \geq g(b)$ and $h(a) \leq h(b)$, then set $c = \frac{a+b}{2}$. (see case 3)


Comments

Popular posts from this blog

Multi-Core Programming with Java

Interpolation Search Explained

Beat the Streak: Day Three