1
$\begingroup$

I have been thinking about it for several days and still have not solved it completely. This is the problem:

My formula: Outcome=$(a_1*b_1)+(a_2*b_2)+(a_3*b_3)...+(a_n*b_n),$ where $0\le a\le 1,$ $0\le b\le1, ~~a+b\le 1, ~~a_1+a_2+a_3...+a_n\le 1.$

I would like to find the maximum of this function based on the value of n. Just by trying out different numbers, I have found that the maximum should be (n-1)/n, but I have not been able to prove it mathematically yet. Any help is very much appreciated!

$\endgroup$

closed as unclear what you're asking by kjetil b halvorsen, Chris Godsil, hardmath, JonMark Perry, user223391 Oct 22 '17 at 14:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ what is $a$? is it a vector? does $0\leq a \leq 1$ means it is bounded by $0$ and $1$ element wise? $\endgroup$ – Siong Thye Goh Oct 15 '17 at 17:35
  • $\begingroup$ Finding the maximum of a multivariable function (you say there are $n$ parameters) is naturally more difficult than the single-variable function cases. In this case you have some restrictions on the parameters. But you should try to clarify the problem. I'm guessing the $n$ parameters are $a_1,a_2,\ldots,a_n$ since you say that there are $n$ parameters, and then $b_i$'s would be fixed. But that's just guesswork. $\endgroup$ – hardmath Oct 16 '17 at 2:26
4
$\begingroup$

Since $0\leq a_i\leq 1$, we have from $a_i+b_i\leq 1$ that

$$\sum_{i=1}^na_ib_i\leq\sum_{i=1}^na_i(1-a_i).$$

Next assume $\sum_ia_i=x\in[0,1]$. Then use

$$\frac{1}{n}\sum_{i=1}^n a_i^2\geq\left(\frac{1}{n}\sum_{i=1}^na_i\right)^2=\frac{x^2}{n^2},$$

we obtain

$$\sum_{i=1}^na_ib_i\leq x-\frac{x^2}{n}.$$

The right-hand side is monotonically increasing over $x\in[0,\frac{n}{2}]$. Therefore it is bounded by its endpoint value at $x=1$ so long as $n\geq 2$. Therefore

$$\sum_{i=1}^na_ib_i\leq 1-\frac{1}{n}.$$

For all three inequalities to take equal sign, we have $b_i=1-a_i$, $a_i=\frac{x}{n}$ and $x=1$. Therefore $a_i=\frac{1}{n}$ and $b_i=\frac{n-1}{n}$. Since equality is achievable, the upper bound is the maximum.

$\endgroup$
  • $\begingroup$ $\sum_ia_i$ is supposed to be $\le 1$, not $=1$. $\endgroup$ – amsmath Oct 15 '17 at 17:45
  • $\begingroup$ I assumed $a_1+a_2+\cdots+a_n=1$. In fact the condition is $\leq 1$. You can change it to $a_1+a_2+\cdots+a_n=x\in[0,1]$, go through the same process and then try to maximize the upper bound as a function of $x$. Then you'll see the maximum is achieved at $x=1$. $\endgroup$ – Zhuoran He Oct 15 '17 at 17:46
  • $\begingroup$ But when you go through the same process with $x$, then you get the upper bound $1-x^2/n$, which is larger than $1-1/n$. $\endgroup$ – amsmath Oct 15 '17 at 17:53
  • $\begingroup$ No you should get $x-\frac{x^2}{n}$ The function is monotonically increasing for $x\leq\frac{n}{2}$. So long as $n\geq 2$, the argument holds. $\endgroup$ – Zhuoran He Oct 15 '17 at 17:54
  • $\begingroup$ The math looks prettier without the $x$. But should I really edit it? $\endgroup$ – Zhuoran He Oct 15 '17 at 17:56
0
$\begingroup$

Hint :

it's just an application of the inequality of Chebyshev.

You have just to remark that we have this :

$a_1\geq a_2 \cdots \geq a_n$

And

$b_1\leq b_2 \cdots \leq b_n$

Finally conclude .

$\endgroup$

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