Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
Hint Consider taking logarithms of the objective and constraint. –  Daryl Nov 1 '12 at 9:39
2  
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
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. –  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)$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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