When does symmetry in an optimization problem imply that all variables are equal at optimality? - MathOverflow

When does symmetry in an optimization problem imply that all variables are equal at optimality?

2011-03-17T04:51:07Z

There are many optimization problems in which the variables are symmetric in the objective and the constraints; i.e., you can swap any two variables, and the problem remains the same. Let's call such problems symmetric optimization problems. The optimal solution for a symmetric optimization problem - like many of the ones that show up in calculus texts - frequently has all variables equal. To take some simple examples,

The rectangle with fixed area that minimizes perimeter is a square. (Minimize $2x+2y$ subject to $xy = A$ and $x,y \geq 0$.)
The rectangle with fixed perimeter that maximizes area is a square. (Maximize $xy$ subject to $2x + 2y = P$ and $x,y \geq 0$.)
The difference between the arithmetic mean and the geometric mean of a set of numbers is minimized (and equals $0$) when all the numbers are equal.

There are also more complicated symmetric optimization problems for which the variables are equal at optimality, such as the one in this recent math.SE question.

However, it is not true that every symmetric optimization problem has all variables equal at optimality. For example, the problem of minimizing $x +y$ subject to $x^2 + y^2 \geq 1$ and $x, y \geq 0$ has $(0,1)$ and $(1,0)$ as the optimal solutions.

Does anyone know of general conditions on a symmetric optimization problem that guarantee the optimal solution has all variables equal?

The existence of such conditions might be very nice. Unless the conditions themselves are ugly, they ought to vastly simplify solving a large class of symmetric optimization problems.

(Maybe convexity plays a role? My last example has a nonconvex feasible region.)

Answer by Dirk for When does symmetry in an optimization problem imply that all variables are equal at optimality?

2011-03-17T08:03:43Z

A bit too long for a comment: Let's consider a optimization problem of the form $$ \min_x f(x)\quad \text{s.t.}\quad x\in C. $$

If we now consider "symmetry" a bit more abstract by saying that you have a group $G$ acting on the set $C$ such that the objective is invariant under the group action, i.e. for $g\in G$ we have $f(gx) = f(x)$ then you see that the set of minimizers is also invariant under the group action.

Answer by Igor Rivin for When does symmetry in an optimization problem imply that all variables are equal at optimality?

2011-03-17T14:20:54Z

The most common condition for symmetry in my experience is convexity: if the feasible region is symmetric and convex, and the objective function is convex, it is immediate that argmin has all variables equal (or invariant by whatever your symmetry group is).

Answer by Henry Cohn for When does symmetry in an optimization problem imply that all variables are equal at optimality?

2011-03-18T00:08:33Z

The Monthly article "Do symmetric problems have symmetric solutions?" by William Waterhouse (http://mathdl.maa.org/images/upload_library/22/Ford/Waterhouse378-387.pdf) discusses this issue. For global optimality one really needs strong global constraints on the objective function, such as convexity (as in Igor's answer), and there's nothing one can say otherwise. However, local results hold in considerably greater generality. Waterhouse calls this the Purkiss Principle: in a symmetric optimization problem, symmetric points tend to be either local maxima or local minima.

Specifically, suppose we are optimizing a smooth function $f$ on a manifold $M$. The symmetry can be expressed by saying some finite group $G$ acts on $M$ and preserves $f$. If $x$ is a point in $M$ that is fixed by $G$, we would like to understand the behavior of $f$ near $x$. To analyze it, we can study the action of $G$ on the tangent space $T_x M$. The key hypothesis is that $T_x M$ should be a nontrivial irreducible representation of $G$. In that case, $x$ is automatically a critical point for $f$, and if it is a nondegenerate critical point, then it must be a local maximum or minimum (i.e., not a saddle point). In fact, even more is true: the Hessian matrix will have only one eigenvalue, which is either zero (degenerate), positive (local minimum), or negative (local maximum).

This is one of those results where finding the right statement is the real issue, and once the statement has been found it takes just a few lines to prove it. In his article, Waterhouse builds up to this formulation in several steps, and he shows how it encompasses various more concrete cases and applications. He also gives a wonderful historical overview.

If the representation on the tangent space is reducible, then the Purkiss Principle can fail. If we break the representation into a direct sum of irreducible subrepresentations, then the Hessian matrix for $f$ will have an eigenvalue for each irreducible (with multiplicity equal to the dimension of the irreducible), and there's no reason why they should all have the same sign. However, this decomposition is nevertheless very useful for doing local calculations, because even if $M$ is high-dimensional, $T_x M$ may decompose into just a few irreducibles.

So the upshot is this: if you are applying the second derivative test to a symmetric optimization problem, then representation theory will tell you what the symmetry implies, and irreducibility leads to the simplest possible answer.

Answer by Robert Israel for When does symmetry in an optimization problem imply that all variables are equal at optimality?

2011-03-20T22:22:17Z

The assumption of convexity can be weakened to quasiconvexity.

Answer by Bigfella for When does symmetry in an optimization problem imply that all variables are equal at optimality?

2011-11-09T11:47:09Z

Suppose you have any optimization problem that is symmetric. I somehow weaker question is: How much of the original symmetry carries over to the solutions? For the symmetric group $S_n$ if the degree $d$ of the polynomials that describe the problem is low (compared to the number of variables) the "degree and half principle" says that one always finds minimizers contained in the set of points invariant by a group $S_{l_1}\times\ldots\times S_{l_d}$ where $l_1+\ldots+l_d=n$