Supremum question with Arithmetic-Geometric means

129 Views Asked by At

Let $n\ge2$ fixed. How do you find the least $\alpha(n)$ such that, for any numbers $0<a_1,...,a_n$ and $0\le b_1,...,b_n\le1/2$, with $\sum_{i=1}^n a_i=\sum_{i=1}^n b_i=1$, we have $\prod_{i=1}^na_i\le\alpha(n)\sum_{i=1}^na_ib_i$.

I was thinking use the generalized AM-GM inequality, but i can't finish it.

2

There are 2 best solutions below

3
On

Very nice question!! However, this is only interesting if $n=3.$ Indeed, if $n=2,$ then it can only be $$a_1=a_2=b_1=b_2=\frac{1}{2}.$$ Hence in this case
$$\prod_{i=1}^2 a_i= \frac{1}{4}, \; \sum_{i=1}^n a_ib_i =\frac{1}{2},$$ and this means that $\alpha(2)=\frac{1}{2}$

On the other hand, there is no such constant for $n\geq 4.$ To see this, take $a=(\frac{1}{2},\frac{1}{2},0,\ldots,0)$ and $b=(0,\ldots,0, \frac{1}{2},\frac{1}{2}). $ Then $$\prod_{i=1}^n a_i= \frac{1}{4}, \; \sum_{i=1}^n a_ib_i =0,$$ and this would contradict the existence of such a constant.

Now we will focus on the case $n=3.$ For this, we define the set

$$\Omega= \{x\in \Bbb R^3: 0\leq x_i\leq \frac{1}{2},\; x_1+x_2+x_3=1 \}.$$ We start with the following lemma:

$\textbf{Lemma:}$ Let $a,b\in \Omega.$ Then

$$\sum a_ib_i \geq \frac{1}{2}(1- \max\{a_i\}).$$ $\textbf{Proof:}$ Fix any $a \in \Omega.$ Then, the optimization problem

$$\min \;\; g(b)= a^Tb,\; s.t\;\; b\in \Omega$$ is a linear programming problem, and hence a solution can always be found that is an extreme point of the feasible set, i.e, an extreme point of $\Omega.$ The only extreme points of this set are $ext(\Omega)= \left\{\left(\frac{1}{2},\frac{1}{2},0\right),\left(\frac{1}{2},0,\frac{1}{2}\right),\left(0,\frac{1}{2},\frac{1}{2}\right)\right\}.$ Hence, the desired minimum is $$\min \left\{g\left(\frac{1}{2},\frac{1}{2},0\right),g\left(\frac{1}{2},0,\frac{1}{2}\right),g\left(0,\frac{1}{2},\frac{1}{2}\right)\right\}= \frac{1}{2}(\min\{a_i\}+ \textrm{mid}\{a_i\} )= \frac{1}{2}(1- \max\{a_i\}),$$ where mid$\{a_i\}$ is the middle number of the $a_i$'s, i.e, mid$\{a_i\}=a_j$ iff $$\min\{a_i\}\leq a_j \leq \max\{a_i\}.$$ This proves the lemma. $\Box$

Now note that, in virtue of the previous lemma, if $\alpha(3)$ exists, it must satisfy

$$a_1a_2a_3\leq \frac{\alpha(3)}{2} (1-\max\{a_i\}) \;\forall\; a\in \Omega,$$ and that this inequality is sharp. This means that $\alpha(3)$ is the optimal value of the optimization problem

$$\max F(a)=\frac{2a_1a_2a_3}{1-\max\{a_i\}}, \;\;s.t\;\; a\in \Omega.$$ Now we proceed to solve this problem. The first thing is to get rid of the smoothness of the objective function and of the equality constraint. Due to the symmetry of the objective function, we may assume without loss of generality that $a_3= \max\{a_i\}.$ So, the problem is equivalent to find

$$\max F(a)= \frac{2a_1a_2a_3}{1-a_3} \;\; s.t\; a \in \Omega,\; a_1\leq a_3,\;a_2\leq a_3. $$ Note that the constraints $a_1\leq a_3,\;a_2\leq a_3$ where added in order to ensure that $a_3=\max\{a_i\}.$ Next, we deal reduce the dimension of the problem by eliminating the equality constraint. For this, we can put $a_3= 1-(a_1+a_2)$ and after rearranging the terms the problem will be equivalent to

$$(\mathcal{P})\;\max f(a_1,a_2)= \frac{2a_1a_2}{a_1+a_2}-2a_1a_2, \; \;s.t\; (a_1,a_2)\in S,$$ where

$$S=\{(a_1,a_2)\in \Bbb R^2: a_i\geq 0, a_1+a_2\geq \frac{1}{2},\;2a_1+a_2\leq 1,\; a_1+2a_2\leq 1.\}$$ Note that the constraints $a_i\leq \frac{1}{2}$ are redundant, i.e, they can be obtained from the rest of the constraints. To see this, take $(a_1,a_2)\in S.$ Then, $a_i+\frac{1}{2}\leq a_i +a_1 +a_2\leq 1$ and this will imply $a_i\leq \frac{1}{2}.$

The rest of the proof consists in solving the optimization problem $(\mathcal{P}).$ For this, note that $S$ is the triangle with vertices $\{(\frac{1}{2},0),(0,\frac{1}{2}),(\frac{1}{3},\frac{1}{3})\}.$ Hence this set is compact and that means that the optimization prolem has a solution by Weirstrass's Theorem.

We will analyze four cases: three cases are related to finding the maximum on the edges of $S$ and one case to find the maximum on the interior of $S.$ Obviously, the solution of the problem will be the maximum among all the maximums found.

$\textbf{Case 1:} \; a_1+a_2=\frac{1}{2}.$

In this case the problem reduces to find

$max \;f(a_1)=-4a_1^2+2a_1, \;s.t\; a_1\in [0,\frac{1}{2}].$ The objective function is a parabola with vertex at $a_1= \frac{1}{4} \in [0,\frac{1}{2}],$ and hence the maximum is attained at this point. Hence

$$M_1= max\; f(a_1)=-4a_1^2+2a_1, \;s.t\; a_1\in [0,\frac{1}{2}]=f(\frac{1}{4})=\frac{1}{4}. $$

$\textbf{Case 2:} \;2a_1+a_2=1.$

After putting $a_2= 1-2a_1$ in the problem we get that it is equivalent to $$\max \;f(a_1)=\frac{2a_1-4a_1^2}{1-a_1}-(2a_1-4a_1^2), \; s.t\; a_1\in [\frac{1}{3},\frac{1}{2}].$$ Here, the maximum is attained either at an interior point of the interval or at one of the extreme points, i.e, $\frac{1}{3}$ or $\frac{1}{2}.$

We have $f(\frac{1}{3})= \frac{4}{9}, \; f(\frac{1}{2})=0.$ If the extremum is attained in the interior of the interval, we must have $f'(a_1)=0$ at this point. Solving the system $f'(a_1)=0$ gives

$$a_1=\frac{7- \sqrt{17}}{8}$$(another solution of the resulting quadratic equation is rejected because it doesn't belong to the interval). Moreover, we can compute $f(\frac{7- \sqrt{17}}{8})= 0.11340. $ Hence

$$M_2= \max \;f(a_1)=\frac{2a_1-4a_1^2}{1-a_1}-(2a_1-4a_1^2), \; s.t\; a_1\in [\frac{1}{3},\frac{1}{2}]= \max \{f(\frac{1}{3}),f(\frac{1}{3}),f(\frac{7- \sqrt{17}}{8})\}=\max \{\frac{4}{9}, 0, 0.11340\}= \frac{4}{9}.$$

$\textbf{Case 3:}\; a_1+2a_2=1.$

This case is the same as Case 2 due to the simmetry. Hence $M_3=\frac{4}{9}.$

$\textbf{Case 4:}\; (a_1,a_2) \in int(S)$

Here the necessary optimality considtion is $\nabla f(a_1,a_2)=0.$ After solving this equation you will get $a_1=a_2= \frac{1}{4},$ and hence $M_4=\frac{1}{4}$(See case 1).

This means that the desired value is $$\alpha(3)=\max\{M_1,M_2,M_3,M_4\}=\max\{\frac{1}{4}, \frac{4}{9}\}=\frac{4}{9}.$$ We want to mention that we never checked the sufficiency of the optimality condition because it wouldn't alter the maximum in the final result, otherwise we should have checked that.

All in all, we can say that $\alpha(2)=\frac{1}{2}, \;\alpha(3)= \frac{4}{9}$ and $\alpha(\cdot)$ is not defined for $n\geq 4.$

I hope this clears your question. Merry Christmas!

2
On

Let $n> 2$. WLOG let $a_i$ be ordered in non-decreasing manner. Then, $\sum_{i=1}^n a_i b_i \geqslant \frac12(a_1+a_2)$ so it is enough to consider the inequality $$\prod_{i=1}^n a_i \leqslant \alpha(n) \cdot \frac{a_1+a_2}2$$
Once $a_1, a_2$ are fixed, we have $\prod_{i> 2} a_i$ maximised (by AM-GM) when all higher $a_i$ are identical, i.e. we may set $\displaystyle a_{i>2} = \frac{1-a_1-a_2}{n-2}$ for the optimum.

For convenience, let $p^2 = a_1 a_2, 2s = a_1+a_2$. Then it is enough to consider the inequality $$p^2\cdot\left(\frac{1-2s}{n-2} \right)^{n-2} \leqslant \alpha(n)s$$

where we need to optimise for $p, s$, with $0 \leqslant p \leqslant s \leqslant \frac12$. Clearly reducing $s$ makes the LHS larger and the RHS smaller. hence making the inequality tighter. Similarly increasing $p$ makes the LHS larger. Hence we should set $s=p$, i.e. $a_1 = a_2=s=p$ in the optimum. With this, we have $$s\left(\frac{1-2s}{n-2} \right)^{n-2} \leqslant \alpha(n)$$ Using univariate calculus (or AM-GM), it is easily seen LHS has a maximum when $s=\frac1{2n-2}$. Interestingly this sets $a_1 = a_2$ at half the value as all the rest. Using this, we get $\alpha(n) \geqslant \dfrac1{2(n-1)^{n-1}}$.


P.S. $n=2$ is left for you to work out...