1
$\begingroup$

Assume that $\sum_{i=1}^na_i=1$ and $\sum_{i=1}^nb_i=1$, and $0 \le a_i, b_i \le 1$ for $i=1,\ldots,n$. Can we prove the following lower bound:

$$\frac{1}{n} \le \sum_{i=1}^n{a_ib_i} \,.$$

PS: If $b_i$s do not depend on $a_i$s, then we can easily take derivatives of the right-hand side with respect to $a_i$s, and solve the system to get:

$$b_1=\cdots=b_n = \frac{1}{n} \,.$$

From there, we see that the minimum value of $\sum_{i=1}^n{a_ib_i}$ is $\frac{1}{n}$.

$\endgroup$
  • 1
    $\begingroup$ A counterexample: $b_1 = b_2 = \cdots = b_{n-1} = 0$, $b_n = 1$ and $a_1 = 1$, $a_2 = a_3 = \cdots = a_n = 0$. $\endgroup$ – PSPACEhard Apr 2 '17 at 15:51
  • 1
    $\begingroup$ Or for strictly positive values: $a_1=a_2=\ldots=a_{n-1}=b_2=b_3=\ldots=b_n=\epsilon>0$, $a_n=b_1=1-(n-1)\epsilon$. Then $\sum_i a_i = \sum_i b_i = 1$ and $\sum_i a_i b_i = 2\epsilon - n\epsilon^2$, which can be made arbitrary small. $\endgroup$ – celtschk Apr 2 '17 at 15:59
3
$\begingroup$

We can easily reach $0$ by settings $a_1 := 1,\ a_i := 0\ \forall i > 1$ and $b_1 := 0, \ b_2 = 1,\ \ b_i := 0\ \forall i > 2$. Since all terms must be non-negative, this is an actual lower bound.

Also using Cauchy-Schwarz and the fact that $0 \leq a_i, b_i \leq 1$ : $$ \sum_{i=1}^n a_ib_i \leq \left(\sum_{i=1}^n a_i^2\right)^{1/2}\left(\sum_{i=1}^n b_i^2\right)^{1/2} \leq \left(\sum_{i=1}^n a_i\right)^{1/2}\left(\sum_{i=1}^n b_i\right)^{1/2} = 1 $$ Where the bound can be reached with $a_1 = b_1 = 1, \ a_i = b_i = 0\ \forall i>1$. Overall we have $$ 0 \leq \sum_{i=1}^n a_ib_i \leq 1 $$

$\endgroup$
2
$\begingroup$

You solution is a saddle stationary point, rather than either a minimum or a maximum. You can easily see this by the simply example of $n=2$. That is the very pitfall of using only the first order condition. If you want to use the Lagrangian equation, you have to check the solution is indeed a minimum or maximum by, say, checking the convexity or concavity of the function under the constraint.

$\endgroup$

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.