MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 remove duplicate tag
1

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

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.)