# Prove two optimization problems are equivalent

Hello! Let $x_1\ge x_2\ge ... \ge x_n>0$. Here are two optimization problems:

P1: Maximize $\Pi _{i=1}^n x_i$ subject to $\sum _{i=1}^n x_i =K$.

P2: Minimize $\sum _{i=1}^n (x_i-K/n)^2$.

As $\sum _{i=1}^n x_i =K$, $K/n$ actually is the mean value of $x_i$. For Problem 1, the maximizer is $x_1=...=x_n=K/n$. For Problem 2, the minimizer is also $x_1=...=x_n=K/n$. Hence P1 and P2 are equivalent when $x_i$ can achieve the mean value.

My question is: There may exist some other constraints such that $x_i$ can not reach the mean. Are the two problems still equivalent when $x_i$ is not able to achieve the mean value? In other words, can P1 and P2 reach optimality simultaneously no matter what other constraints $x_i$ have.Intuitively $\Pi _{i=1}^n x_i$ becomes larger as $x_i$ approach the mean as close as possible. $\sum _{i=1}^n (x_i-\frac{K}{n})^2$ actually is the distance between $x_i$ and the mean value. Intuituvely I believe they are equivalent, but I am not able to prove it.

Edit: Frankly, I am actually interested in the equivalence between P1 and the following P3.

P3: Minimize $\sum _{i=1}^n x_i^2$ subject to $\sum _{i=1}^n x_i =K$.

P2 actually is an intermediate problem. It is easy to show P2 and P3 are equivalent all the time. ($\sum _{i=1}^n (x_i-K/n)^2=\sum _{i=1}^n x_i^2-2K/n\sum _{i=1}^n x_i+K^2/n$). I am trying to prove P1 is equivalent to P2. Of course, it is the best if we can prove P1 is equivalent to P3 directly. But I'm not sure P1 and P3 is equivalent. Intuitively it seems they reach optimality simultaneously.

-
"There may exist other constraints". What other constraints? –  Yemon Choi May 8 '11 at 3:53
Try a constraint which fixes one of the x_i to something other than K/n. –  Aaron Bergman May 8 '11 at 3:58
@Yemon: For example, one of the $xi$ is lower bounded by a value which is larger than $K/n$. The point should be: no matter what the other constraints are, the two problems should reach optimality simultaneously. –  Shiyu May 8 '11 at 5:12
So what about the constraint: $7$ does not occur in the decimal expansion of $x_1$? I suspect this is not the kind of constraint you meant, in which case you should perhaps try to say precisely what kinds of constraint you mean. –  Yemon Choi May 8 '11 at 6:09
@Yemon: Here is the constraint: $x_1 \ge \alpha >K/n$ and $\sum _{i=1}^n x_i=K$. –  Shiyu May 8 '11 at 6:49

Now that the problem has been clarified somewhat, under the particular constraint mentioned here, (but not others of a similar nature), the two problems do have the same solution. Let $K,n,\alpha$ be positive with $\alpha \gt \frac{K}{n}$ and consider these optimization problems over non-negative $n$-tuples.

P1 Maximize $\prod _{i=1}^n x_i$ subject to $\sum _{i=1}^n x_i =K$ AND $x_1 \gt \alpha.$

P3: Minimize $\sum _{i=1}^n x_i^2$ subject to $\sum _{i=1}^n x_i =K$ AND $x_1 \gt \alpha$.

The common extreme is at $x_1=\alpha$ and $x_2=x_3=\cdots=x_n=\frac{K-\alpha}{n-1}.$ To see this, consider any other $n$-tuple. If it has $x_1 \gt \alpha$ then the minimum entry is $x_n \lt \frac{K-\alpha}{n-1}.$ Replace $x_1$ by $x_1-\epsilon$ and $x_n$ by $x_n+\epsilon$ where $\epsilon=\min(x_1-\alpha,\frac{K-\alpha}{n-1}-x_n)$. Observe that this increases what we want to maximize in P1 and decreases what we want to minimize in P2. In the case that $x_1=\alpha$ but $x_2 \gt \frac{K-\alpha}{n-1} \gt x_n$ we replace $x_2$ by $x_2-\epsilon$ and $x_n$ by $x_n+\epsilon$ where now $\epsilon=\min(x_2-\frac{K-\alpha}{n-1},\frac{K-\alpha}{n-1}-x_n).$ After at most $n$ (strict) improvements by $\epsilon$-moves of this sort we arrive at the claimed $n$-tuple.

Consider non-negative triples with $x_1+x_2+x_3=4.46$ and the constraint that at least one of $x_1 \ge 2$ or $x_3 \le 1$ must be true. By an $\epsilon$ argument as above, a maximum for P1 is at either $\mathbf{x}=(2,1.23,1.23)$ or $\mathbf{y}=(1.73,1.73,1)$ and the same is true of a minimum for P3. It turns out that these extremes do not occur at the same place: the maximum for P1 is at $\mathbf{x}$ since $3.0258 \gt 2.9929$ but the minimum for P3 is at $\mathbf{y}$ since $7.0258 \gt 6.9858$

Notes:

1. As far as the result, we could also have used this constraint: at least one of $x_1,x_2,x_3$ is an integer.

2. For this example to work with $K$ slightly larger than $4$ requires $4.414 \lt 3+\sqrt{2} \lt K \lt 4.5.$ In my experience (see the example in my old answer below) things are this delicate and using a larger $K$ makes them even more delicate. Another example with $n=3$ is $K=1.2$ with contenders $(0,0.6,0.6)$ and $(0.1,0.1,1).$

Dropping the new constraints, The first problem can be equivalently rewritten as

P1 Maximize $\sum _{i=1}^n \ln(x_i)$ subject to $\sum _{i=1}^n x_i =K$.

Then it has the form: Maximize $\sum _{i=1}^n f(x_i)$ subject to $\sum _{i=1}^n x_i =K$ where $f$ is a concave function in the sense that $f(u+\epsilon)+f(v-\epsilon) \gt f(u)+f(v)$ provided $u \lt u+\epsilon \lt v-\epsilon \lt v.$ Other examples include $f(x)=\arctan(x)$ and $f(x)=x^p$ with $0 \lt p \lt 1.$ Note than $\ln(x)=\lim \frac{x^p-1}{p}$ as $p$ approaches $0$ from above.

And P2 has the form: Minimize $\sum _{i=1}^n g(x_i)$ subject to $\sum _{i=1}^n x_i =K$ where $g$ is a convex function in the sense that $g(u+\epsilon)+g(v-\epsilon) \lt g(u)+g(v)$ provided $u \lt u+\epsilon \lt v-\epsilon \lt v.$ Here we have essentially the $\ell_2$ norm and $g(x)=|x|^p$ for $p>1$ gives the $\ell_p$ norm. Another example is $g(x)=x\ln(x)$

Call a replacement of $u \lt v$ by $u+\epsilon \lt v-\epsilon$ an $\epsilon$-move and call an $n$-tuple $\epsilon$-optimal if no move of this type is possible (subject to any further constraints). Then any optimization problem as above will attain its extreme value at an $\epsilon$-optiml tuple. So all achieve their extreme value at $x_1=\cdots=x_n=\frac{K}{n}$ if that is possible. When there are several $n$-tuples which are optimal in that no further $\epsilon$ moves are possible, then it may be that some optimize one function and others optimize another.

OLD ANSWER I will alter the question and then give an answer of NOT ALWAYS.

I will take the question to be this: Given an $n$-tuple $\mathbf{x}=x_1,x_2,\cdots,x_n$ with $K=\sum _{i=1}^n x_i$, let $\alpha(\mathbf{x})=\Pi _{i=1}^n x_i$ and $\beta(\mathbf{x})=\sum _{i=1}^n (x_i-K/n)^2.$ Suppose we have a set of positive $n$-tuples all with the same sum $K$. We can define a preorder on them by $\mathbf{x} \ge \mathbf{y}$ when $\alpha(\mathbf{x}) \ge \alpha(\mathbf{y})$ OR by $\mathbf{x} \ge \mathbf{y}$ when $\beta(\mathbf{x}) \le \beta(\mathbf{y})$.

Question: does $\alpha(\mathbf{x}) \le \alpha(\mathbf{y})$ always imply $\beta(\mathbf{x}) \ge \beta(\mathbf{y})?$

The question is really about the maximal elements in these two orders but we can always make rules to eliminate the ties.

I wish I had a more natural seeming example but: Consider these triples with sum $30$: $\mathbf{x}=[8.1,10.95,10.95]$ and $\mathbf{y}=[9,9,12]$ then $\alpha(\mathbf{x})=971.21025<972=\alpha(\mathbf{y})$ but also $\beta(\mathbf{x})=5.415<6=\beta(\mathbf{y}).$

-
@Aaron: Thank you very much for your excellent answer. It will help a lot. –  Shiyu May 10 '11 at 13:19