3
$\begingroup$

I am trying to find the set of $x_{i}$ that maximize $\prod_{i=1}^{N}{\left(1+x_{i}\right)}$ given that $\prod_{i=1}^{N}{x_{i}} = c$ and $0\leq x_{i} \leq 1$ for all $i$. As far as I can tell unless the solution set is $x_{i}$ is equal to $\sqrt[n]{c}$ for all $i$, then there is not going to be a unique solution, so an extra constraint along the lines of $x_{i} \leq x_{i+1}$ is also fine.

For $N$ equal to 2, the solution appears to be $x_{i}$ is equal to $\sqrt[n]{c}$ for all $i$. I get this by expanding the product, taking the derivative, then solving for when the derivative is equal to zero, and then confirming it is a maximum with the second derivative. But apparently my math is rustier than I thought, and I have in fact confirmed that $\sqrt[n]{c}$ is a minimum since the second derivative is positive.

I might be able to use the same approach for $N$ equal to 3, but there are more terms and you need to take partial derivatives. The problem is it doesn't get me closer to a general solution.

Using the logarithm hint makes everything look nicer. The problem then become to maximize $\sum_{i=1}^{N}{\log{\left(1+x_{i}\right)}}$. I think I want to find where all the partial derivatives are equal to zero. The partial derivative is $\frac{1}{1+x_{i}}$ which is never zero. I think this means my maximum lies on the boundary, but I don't understand what a multivariate boundary is.

  • 0
    @MartinSleziak apparently my math is really rusty. I forgot how to do the second derivative check. I updated the question.2012-11-01

2 Answers 2

4

We can show by induction that the inequality $\prod_{i=1}^N (1+x_i) \le 2^{N-1}(1+c)$ holds for any $x_i\in[0,1]$ such that $x_1x_2\dots x_n=c$.

For two variables: The following inequalities are equivalent to each other: $ \begin{align*} (1+x_1)(1+x_2)&\le 2(1+c)\\ 1+x_1+x_2+x_1x_2&\le 2(1+c)\\ 1+x_1+x_2+x_1x_2&\le 2+2x_1x_2\\ 0&\le 1-x_1-x_2+x_1x_2\\ 0&\le (1-x_1)(1-x_2). \end{align*} $ Since the last inequality is true for $x_{1,2}$ fulfilling the given condition, the first is true, too. The equality is attained only if $x_1=1$ or $x_2=1$.

Inductive step: Suppose that the above inequality is true for $n-1$ variables. We will show that it holds for $n$ variables.

We have $x_1\dots x_{n_1}x_n=c$, then $x_1\dots x_{n_1}=\frac c{x_n}$.

So for any fixed $x_n$ we have (using inductive hypothesis) $(1+x_1)\dots(1+x_{n-1})(1+x_n) \le 2^{n-2}(1+\frac{c}{x_n})(1+x_n).$ What is maximal possible value of $(1+\frac{c}{x_n})(1+x_n)$? This is precisely the case of two variables, which we have already solved. (For $y_1=\frac{c}{x_n}$ and $y_2=x_n$ we are trying to maximize $(1+y_1)(1+y_2)$ with the condition that $y_1y_2=c$.) Hence $(1+\frac{c}{x_n})(1+x_n)\le 2(1+c)$, where the maximum is attained if $x_1\dots x_{n-1}=1$ or $x_n=1$. Together we have $(1+x_1)\dots(1+x_{n-1})(1+x_n) \le 2^{n-1}(1+c).$

  • 1
    No need for the inductive step. Just note that if two entries $x_i$ and $x_j$ are not equal to 1, then you can increase the objective while satisfying the constraint by setting $\tilde x_i = x_i \cdot x_j$ and $\tilde x_j = 1$, and therefore it is not a maximum. The only conclusion is that at most one of the entries is not 1 at the maximum.2012-11-01
4

Put $x_i:=e^{-y_i}$ Then we have to maximize $f(y):=\sum_{i=1}^N \log\bigl(1+e^{-y_i}\bigr)$ under the constraints $y_i\geq0\quad(1\leq i\leq N),\qquad \sum_{i=1}^Ny_i=\log{1\over c}\ .$ This implies that the domain of admissible $y$ is a simplex in ${\mathbb R}^N$, so is a compact set. The function $g(t):=\log(1+e^{-t})$ has $g'(t)=-{1\over 1+e^t}<0,\quad g''(t)={e^t\over(1+e^t)^2}>0\qquad(t\geq0)\ .$ Therefore $g$ is decreasing and convex for $t\geq0$. Looking at the graph of $g$ we can say the following: Given two values $0, putting $t_1'=0$, $t_2':=t_1+t_2$ leaves $t_1'+t_2'=t_1+t_2$, but makes $g(t_1')+g(t_2')>g(t_1)+g(t_2)$ since the gain on the left is larger than the loss at the right.

This allows for the following conclusion: Given an admissible $y$, as long as there are two $y_i>0$, say $0, we can make $f(y)$ larger by replacing $y_1$, $y_2$ by $y_1':=0$, $y_2':=y_1+y_2$ and still satisfy the constraints. It follows that $f$ takes its maximum when all $y_i$ but one are zero and the last one has value $\log{1\over c}$.

Going back to the original problem this means that we should choose $x_i:=1$ for all $i$ but one and give the remaining $x_i$ the value $c$. So the maximal value of the considered expression is $2^{N-1}(1+c)$.

  • 0
    @Daniel E. Shub: The expression is correct, but of course it is <0, as described in the text.2012-11-01