-1
$\begingroup$

Given a multivariable function $\sum_{i=1}^k x_i(n-x_i)$ for $k\geq 3$ where $0\leq x_i \leq n$ and $x_1+\cdots+x_k=n$, what is the absolute maximum value and where is it attained?

$\endgroup$
1
$\begingroup$

Here are two solutions using approaches that also works for some similar problems.

Approach 1:

First, note that $f(x_1,\dots, x_k) = \sum_{i=1}^k x_i(n-x_i)$ is a continuous function on a closed, bounded domain and therefore has an absolute maximum $M$. Suppose $f(a_1,\dots,a_n)=M$. We will show that the $a_i$ must be equal, because the value of $f$ increases if two unequal $x_i$ values are replaced by their average. (This replacement maintains the constraints on the range of the $x_i$ and their sum.)

If two of the $a_i$ values are $a$ and $b$, respectively, with $a\neq b$, the value of $f$ after each of these two values is replaced with their average, $\frac{a+b}2$, is $M-a(n-a)-b(n-b)+2\frac{a+b}2(n-\frac{a+b}2)=M+a^2+b^2-\frac{(a+b)^2}2=M+\frac{(a-b)^2}2>M$.

Thus $f$ attains its maximum $M$ when $x_1=x_2=\cdots=x_k$, or where each $x_i$ equals $\frac{n}k$.

Approach 2:

Again, assume that $f(a_1,\dots,a_k)=M$, where $M$ is the maximum. Note that $\frac{\partial f}{\partial x_i}=n-2x_i$. The directional derivative of $f$ in the $\vec{e_i}-\vec{e_j}$ direction (a direction that maintains the constraint on the sum of the $x_i$) is then $2x_j-2x_i$. This is not zero if $x_i\neq x_j$, so the maximum value of $f$ cannot occur if the $x_i$ are not all the same.


Added later: Another version of Approach 2, appealing to the idea behind the method of Lagrange multipliers as motivation. Maybe this helps a little to understand why what I first wrote is enough.

Your goal is to maximize $f(\vec x)=\sum_{i=1}^k x_i(n-x_i)$ subject to the constraint $g(\vec x)=0$, where $g(\vec x)=x_1+\cdots+x_k-n$.

This is from Wikipedia, with minor edits:

The method of Lagrange multipliers relies on the intuition that at a maximum, $f(x_1,\dots, x_k)$ cannot be increasing in the direction of any neighboring point where $g(x_1,\dots, x_k) = 0$. If it were, we could walk along $g(x_1,\dots, x_k) = 0$ to get higher, meaning that the starting point wasn't actually the maximum.

This intuition leads to the fact that at any local maximum of $f$, the gradients of $f$ and $g$ are parallel. Specifically, $\vec\nabla f=\lambda\vec\nabla g$ for some number $\lambda$.

I want to show that this relationship between the gradients does not hold at a point $\vec x$ with $x_i\neq x_j$ for some $i\neq j$. I can do so by showing that there is a direction $\vec v$ in which the directional derivative of $g$ at $\vec x$ (that is, $D_{\,\vec v} g(\vec x)=(\vec\nabla g)(\vec x)\cdot \vec v$) is zero, while $D_{\,\vec v} f(\vec x)=(\vec\nabla f)(\vec x)\cdot \vec v$ is not zero. (A non-zero value can’t be a multiple of zero.)

It’s easy to see that the directional derivative of $g$ in direction $\vec{e_i}-\vec{e_j}$ at $\vec x$ is zero at any $\vec x$, but if any two coordinates $x_i$ of $\vec x$ are different, the directional derivative of $f$ in the same direction at $\vec x$ is non-zero. [For completeness, it’s probably worth mentioning something about the boundaries, by noting that when $x_i$ or $x_j$ is $0$ or $n$, the direction in which $f$ increases keeps the coordinates of $\vec x$ between $0$ and $n$.]

$\endgroup$
  • $\begingroup$ Have you used the extreme value theorem for multivariable in the approach 2? I am not clear with the approach 2, so can you give me more details? $\endgroup$ – kswim Jan 11 '18 at 16:21
  • $\begingroup$ I’m not sure I know exactly what you want to know, but I added a second version of “Approach 2.” Maybe that will help. $\endgroup$ – Steve Kass Jan 11 '18 at 17:41
  • $\begingroup$ It helps a lot! Thank you $\endgroup$ – kswim Jan 11 '18 at 18:24
2
$\begingroup$

Take $f(x)=\Sigma_{i=1}^{k}x_i(n-x_i)$. Considering $\Sigma_{i=1}^{k}x_i=n$ we can rewrite $f(x)$ as follows: $$f(x)=\Sigma_{i=1}^{k}nx_i-\Sigma_{i=1}^{k}x^2_i=n^2-\Sigma_{i=1}^{k}x^2_i$$ Then maximizing $f(x)$ is equivalent to minimizing $\Sigma_{i=1}^{k}x^2_i$. Also by AM-GM we have: $${{\Sigma_{i=1}^{k}x^2_i}\over{n}}\ge(x^2_1...x^2_n)^{1\over n}$$ with equality iff $x^2_1=...=x^2_n$ and since $x_i\ge0$ we can deduce $x_1=...=x_n$ which by substitution gives us $x_1=...=x_n={n\over k}$ and results $max \ f(x)=n^2(1-{1\over{k^2}})$

$\endgroup$
  • $\begingroup$ I'd use QM-AM inequality to justify $x_i=x_j$. Also, the maximum is $n^2(1-1/k)$. $\endgroup$ – Math Lover Jan 10 '18 at 21:15

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