38
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 15
    $\begingroup$ See the Monthly article "Do symmetric problems have symmetric solutions?" by William Waterhouse (jstor.org/pss/2975573). $\endgroup$
    – Henry Cohn
    Commented Mar 17, 2011 at 5:27
  • $\begingroup$ @Henry: Would you be willing to summarize the main results of that paper as an answer? I would upvote it, and it might turn out to be the best answer to my question. $\endgroup$
    – Mike Spivey
    Commented Mar 17, 2011 at 9:03

5 Answers 5

Reset to default
48
$\begingroup$

The Monthly article "Do symmetric problems have symmetric solutions?" by William Waterhouse 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What François G. Dorais said. :) And thank you for taking the time to summarize the article so well. $\endgroup$
    – Mike Spivey
    Commented Mar 18, 2011 at 2:20
  • $\begingroup$ I would love to read more about this principle. But the Waterhouse paper does not appear to be widely cited. Perhaps you can suggest further related references? Thanks! $\endgroup$
    – valle
    Commented Jul 11 at 14:00
15
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ Or more precisely, at least one minimizer is invariant. If the objective function is strictly convex, the minimizer is unique, and then it must be invariant, but otherwise there could also be non-invariant minimizers. For example, in two dimensions take f(x,y) = max(x^2 + y^2 - 1, 0) which is convex and invariant under rotations; the minimizers constitute the closed unit disk, and only (0,0) is invariant. $\endgroup$
    – Robert Israel
    Commented Mar 18, 2011 at 0:01
  • $\begingroup$ @Robert indeed, that is the precise statement... $\endgroup$
    – Igor Rivin
    Commented Mar 18, 2011 at 14:18
14
$\begingroup$

The assumption of convexity can be weakened to quasiconvexity.

Improve this answer
$\endgroup$
0
13
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Dirk, your answer sounds interesting. Would you mind elaborating, for my sake? For instance, I don't think I could look at an optimization problem and recognize when your criterion applies. (My background is operations research, and my abstract algebra is unfortunately quite rusty.) $\endgroup$
    – Mike Spivey
    Commented Mar 17, 2011 at 9:19
  • 3
    $\begingroup$ Maybe I just illustrate with your example: The symmetry you had in your question is the symmtery under the action of the permutation group. The optimization variable is $(x,y)$ and the objective $f(x,y) =x+y$ does not change under the mapping $P(x,y)= (y,x)$, i.e. $f(x,y) = f(y,x)$. Moreover, the mapping $P$ maps the feasibile region $x^2+y^2\geq 1$, $x,y\geq 0$ one-to-one and onto itself. Consequently, if $(x^*,y^*)$ is a solution, $P(x^*,y^*) = (y^*,x^*)$ also is. $\endgroup$
    – Dirk
    Commented Mar 17, 2011 at 9:39
  • $\begingroup$ Thanks, Dirk; now I see what you mean. That's an interesting generalization. $\endgroup$
    – Mike Spivey
    Commented Mar 17, 2011 at 16:21
2
$\begingroup$

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$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .