Group Actions and Minimums of Convex Functions

In this short article we'll be going over a result from convex optimisation theory that shows that the minimums of convex functions occur exactly in the fixed point set of groups that are G-invariant (symmetric functions). We'll show this result for both discrete and continous group actions.

Let \(f:\mathbb{R}^n\to\mathbb{R}\) be convex, and let \(G\) be a finite group acting linearly on \(\mathbb{R}^n\) such that \(f(g \cdot x) = f(x)\) for all \(g\in G, x \in \mathbb{R}^n\). Define the group average of any point \(x\) as

\[ x_{\text{avg}} := \frac{1}{|G|}\sum_{g \in G} g \cdot x. \]

Then:

\(x_{\text{avg}}\) is fixed under the group action: \(h \cdot x_{\text{avg}} = x_{\text{avg}}\) for all \(h\in G\).
By convexity and symmetry:

\[ f(x_{\text{avg}}) = f\Big(\frac{1}{|G|}\sum_{g\in G} g \cdot x\Big) \le \frac{1}{|G|}\sum_{g\in G} f(g \cdot x) = f(x). \]

Hence, there exists a global minimum of \(f\) in the fixed-point subspace:

\[ \text{Fix}(G) = \{ x : g\cdot x = x \ \forall g \in G \}. \]

For our first example we will derive a classic result of information theory. Let \(f(x_1,\dots,x_n) = -\sum_{i=1}^n x_i \log x_i\) (Shannon entropy), with the domain being the standard simplex

\[ \Delta^{n-1} := \{x_i \ge 0, \sum_{i=1}^n x_i = 1\}. \]

The symmetric group \(S_n\) acts by permuting coordinates. By concavity of \(-\sum x_i \log x_i\) and symmetry, the maximum occurs at the fixed point

\[ x_1 = x_2 = \dots = x_n = \frac{1}{n}. \]

So entropy is maximised by the uniform distribution. Now we'll move onto the derivation of the continous version.

Let \(f:\mathbb{R}^n \to \mathbb{R}\) be convex, and let \(G\) be a compact Lie group acting linearly on \(\mathbb{R}^n\) such that \(f(g \cdot x) = f(x)\) for all \(g \in G, x \in \mathbb{R}^n\). Let \(\mu\) be the Haar measure on \(G\) (normalized so \(\mu(G)=1\)). Define the group average

\[ x_{\text{avg}} := \int_G g \cdot x \, d\mu(g). \]

Then:

\(x_{\text{avg}}\) is fixed under the group: \(h \cdot x_{\text{avg}} = x_{\text{avg}}\) for all \(h \in G\), because the Haar measure is invariant (\(\mu(hS) = \mu(S)\)).
By convexity and Jensen's inequality:

\[ f(x_{\text{avg}}) = f\Big(\int_G g \cdot x \, d\mu(g)\Big) \le \int_G f(g \cdot x) \, d\mu(g) = f(x). \]

Hence, a global minimum exists in the fixed-point subspace

\[ \text{Fix}(G) = \{ x : g \cdot x = x \ \forall g \in G \}. \]

The first really basic example is rotations on the n-dimensional ball. Let \(f:\mathbb{R}^n\to\mathbb{R}, f(x) = \|x\|^2\), with domain the n-dimensional ball \(B_r = \{x: \|x\| \le r\}\). Group \(G = SO(n)\) acts by rotations. By convexity and rotational symmetry, the minimum occurs at the fixed point

\[ x = 0. \]

A common function used in machine learning is the log sum exponential. Let \(f(x_1,\dots,x_n) = \log\big(\sum_{i=1}^n e^{x_i}\big)\), with domain \(\{x_i \ge 0, \sum x_i = 1\}\). This function is convex and symmetric under permutations of the variables, so the minimum occurs at

\[ x_1 = x_2 = \dots = x_n = \frac{1}{n}. \]

Our final example from physics is for a particle in a 3D Hookean potential. Let \(f:\mathbb{R}^3 \to \mathbb{R}\) be the potential energy of a particle in a central force field:

\[ f(\mathbf{x}) = V(\|\mathbf{x}\|), \quad \mathbf{x} \in B_r \subset \mathbb{R}^3, \]

where \(V\) is convex and radially symmetric (e.g., \(V(r)=kr^2\) for a harmonic oscillator). The group \(G = SO(3)\) acts by rotations. By convexity and rotational symmetry, the minimum occurs at the fixed point

\[ \mathbf{x} = 0. \]

As you can see in these cases it can make it quite trivial to figure out where the minimums are and lets us avoid using gradient based methods to find the optimal points. Also important to note is that the opposite of this applies to concave functions where the inequalities are reversed so you can use it to find maximums. You can find some other interesting examples and further theory here.