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)
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
Post a Comment