Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you trying to find the extreme value of some function $f(x_1,x_2,\ldots,x_n)$ over the set $\{x_i\}_n$ that is constrained by an unweighted sum as follows $\sum_n x_i=S$. Let's assume that $f(\cdot)$ is differentiable and convex.

Problems like these commonly arise in engineering and other disciplines, and one usually solves them using the method of Lagrange multipliers by constructing a Lagrangian multiplier $\mathcal{L}(\lambda,x_1,x_2,\ldots,x_n)=f(x_1,x_2,\ldots,x_n)+\lambda(\sum_n x_i-S)$ and finding the stationary point by solving a system of $n+1$ equations $\frac{\partial \mathcal{L}}{\partial x_i}=0~\mbox{for}~i=1,2,\ldots,n; \frac{\partial \mathcal{L}}{\partial \lambda}=0$.

I am interested in $f(\cdot)$'s for which the result is equal $x_i$'s: $x_1=x_2=\ldots=x_n$ (under unweighted sum constraint). Is there a way to "test" $f(\cdot)$ (or its derivates) to infer that the variable assignments must be equal at the stationary point? Seems to me that some kind of symmetry property is required in $f(\cdot)$ for that to occur, but I can't quite formulate it.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The definite articles seem to reflect an implicit assumption that there is exactly one stationary point. If this is the case, then there is indeed a simple sufficient but not necessary condition for all arguments to be equal at the stationary point: If $f$ is invariant under permutations of its arguments and there is only one stationary point, then this must necessarily have all arguments equal, since permuting any other tuple of arguments would lead to further stationary points.

This condition is clearly not necessary; for instance $f(x,y)=x^2+2y^2$ has a single stationary point at $x=y=0$ but no permutation symmetry.

If you don't know that there's only one stationary point, then all bets are off. For instance, the function $f(x,y)=(x^2+y^2-1)^2$ (plot) has permutation symmetry and rotation symmetry and has an entire circle of minima at $x^2+y^2=1$, most of which don't have equal arguments, and the function $f(x,y)=\mathrm e^{-2((x-1)^2+y^2)}+\mathrm e^{-2((x+1)^2+y^2)}+\mathrm e^{-2(x^2+(y-1)^2)}+\mathrm e^{-2(x^2+(y+1)^2)}$ (plot) has permutation symmetry and has four maxima, none of which have equal arguments. However, generally speaking, if a function has permutation symmetry, there's a good chance that the stationary point you're interested in will have all arguments the same.

Also, if a function has rotation symmetry, the centre of rotation is necessarily a stationary point.

share|improve this answer
    
Hmmm. Now, suppose that I know that $f(\cdot)$ is a polynomial of degree 1 (i.e., there are no instances of $x_i$ that are powers of anything other than zero or one). Does this make the problem easier? –  M.B.M. Apr 12 '12 at 22:44
    
Also, is a function with rotation symmetry as follows: $f(x_1,x_2,\ldots,x_n)=f(x_2,x_3,\ldots,x_n,x1)=f(x_3,x_4,\ldots,x_1,x_2)=\ldots‌​=f(x_n,x_1,\ldots,x_{n-1})$? What do you mean by centre of rotation then? Or did you mean an odd function? –  M.B.M. Apr 12 '12 at 23:09
    
Another supposition: $f(\cdot)$ is a ratio of two polynomials of degree 1, with the numerator having permutation symmetry and the denominator having the following symmetry: $f_d(x_1,x_2,…,x_n)=f_d(x_2,x_3,…,x_n,x_1)=f_d(x_3,x_4,…,x_1,x_2)=…‌​=f_d(x_n,x_‌​1,…,x_{n−1})$. Are those conditions sufficient to prove that stationary point is found at $x_1=x_2=\ldots=x_n$? –  M.B.M. Apr 12 '12 at 23:23
    
I can augment the original question with all these additional queries... –  M.B.M. Apr 12 '12 at 23:24
    
@M.B.M.: I just noticed that I forgot to address the fact that your question was specifically about optimization under a constraint on the sum of the arguments. However, the same sort of considerations apply; for instance, in my last example, the sum of four Gaussians, if you add the constraint $x+y=1$ you get two maxima that don't have equal arguments. –  joriki Apr 12 '12 at 23:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.