3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – M.B.M. Apr 12 '12 at 22:44
  • $\begingroup$ 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? $\endgroup$ – M.B.M. Apr 12 '12 at 23:09
  • $\begingroup$ 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$? $\endgroup$ – M.B.M. Apr 12 '12 at 23:23
  • $\begingroup$ I can augment the original question with all these additional queries... $\endgroup$ – M.B.M. Apr 12 '12 at 23:24
  • 1
    $\begingroup$ Here is where this question comes from: I am trying to prove that the trace $Tr[(C+D)^{-1}]$ of the inverse of the circulant matrix $C$ that is perturbed on the diagonal by diagonal matrix $D$ is minimized under constraint $Tr[D]\geq S$ when the perturbations are equal, i.e. $D=dI$ with $d=S/n$, where $I$ is identity matrix. Trace in this case is the sum of the diagonal cofactors of the perturbed matrix $C+D$ divided by the determinant of $C+D$... The sum of cofactors (I think) is symmetric and the determinant looks like is shift-symmetric. Not sure if this is more than you wanted to know.. $\endgroup$ – M.B.M. Apr 12 '12 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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