# maximize $\prod_{i=1}^{N}{\left(1+x_{i}\right)}$

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.

-
Hint Consider taking logarithms of the objective and constraint. – Daryl Nov 1 '12 at 9:39
Do you want to maximize or minimize this expression? For two variables you have $(1+x_1)(1+x_2)$. If $c\le 1$ then the minimum is attained for $x_1=x_2=\sqrt{c}$ and it is equal to $1+2\sqrt{c}+c$. The maximum seems to be attained for $x_1=1$, $x_2=c$ with the value $2+2c$. – Martin Sleziak Nov 1 '12 at 9:57
@Daryl the hint gets me closer, but not all the way there. I updated the question. – StrongBad Nov 1 '12 at 10:12
@MartinSleziak apparently my math is really rusty. I forgot how to do the second derivative check. I updated the question. – StrongBad Nov 1 '12 at 10:13

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).$$

-
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. – Nick Alger Nov 1 '12 at 11:26

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<t_1\leq t_2$, 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<y_1\leq y_2$, 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)$.

-
Is the expression for $g\prime$ correct? It seems to be missing an $e^-t$ and I think it has to be less than zero (isn't that what it means to be decreasing?) – StrongBad Nov 1 '12 at 11:11
@Daniel E. Shub: The expression is correct, but of course it is $<0$, as described in the text. – Christian Blatter Nov 1 '12 at 11:52