4
$\begingroup$

Minimizing the following function

$f(x_1,x_2,\cdots,x_n)=\prod\limits_i^n x_i^{x_i}$

such that

$x_1+x_2+\cdots+x_n=P, 2\le x_i$ and $x_i$ are integers.

My attempt: In my opinion we obtain the result when all $x_i's$ are almost equal i.e. $|x_i-x_j|\le 0$ for all $i$ and $j$. I am trying to solve by Lagrange's multiplier and I obtained a system of equation which looks messy.

$\endgroup$
3
$\begingroup$

try as a logarithm: $$ f(x_1,x_2,\cdots,x_n)=\prod_i^nx_i^{x_i} $$ log: $$ g(\vec x)=\log(f(\vec x))=\sum_i^n x_i \log(x_i) $$ Then lagrange method: $$ \mathcal L(\vec x)=g(\vec x)+\lambda(P-\sum_i^n x_i)=\sum_i^n x_i \log(x_i)+\lambda(P-\sum_i^n x_i)= $$ $$ =\sum_i^n x_i( \log(x_i) -\lambda)+\lambda P $$ now impose $\delta \mathcal L=0$.

The logarithm is strickly monotone so extremas are preserved.

EDIT: Full calculation: $$ 0=\delta\mathcal L=\delta\left\{\sum_i^n x_i( \log(x_i) -\lambda)+\lambda P\right\}= $$ $$ =\sum_i^n \delta \left\{x_i( \log(x_i) -\lambda)\right\}+\delta\lambda P= $$ $$ =\sum_i^n \left\{\delta x_i( \log(x_i) -\lambda) +x_i( \frac{\delta x_i}{x_i} -\delta \lambda) \right\}+\delta\lambda P= $$ $$ =\sum_i^n \delta x_i\left( \log(x_i) -\lambda +1\right)+\delta\lambda(P-\sum_i^n x_i) $$ This implies both: $$ \begin{cases} \log(x_i) -\lambda +1=0\\ P-\sum_i^n x_i=0 \end{cases}\implies\begin{cases} x_i =e^{\lambda-1}\equiv\hat x\\ P-\sum_i^n x_i=0 \end{cases}\implies x_i=\frac{P}{n} $$

$\endgroup$
  • $\begingroup$ Does this show that $x_i=P/n$ are integers? @Francesco $\endgroup$ – kamran jamil Aug 31 '17 at 9:32
  • $\begingroup$ obviously not, in general the result is rational. If the $x_i$ must be integers then this is an integer programming problem and the solution is obtained case by case by very specific algorithms. Unless you choose $P$ and $n$ such that $P/n$ is integer. $\endgroup$ – Francesco Alem. Aug 31 '17 at 14:35
  • $\begingroup$ may you help in that case? $\endgroup$ – kamran jamil Sep 1 '17 at 6:09
  • $\begingroup$ the optimal solution in this case is to consider the integer part of $\frac{P}{n}$ and set all $x_i$ to that value, then add $+1$ in a uniform way until the constraint is satisfied. Example $P=4$ and $n=3$, the solutions are all permutations of $1,1,2$. However i cannot demonstrate this procedure. $\endgroup$ – Francesco Alem. Sep 1 '17 at 15:25
1
$\begingroup$

Using weighted AM-GM inequality, $$\frac{P}{\dfrac{x_1}{x_1}+\dfrac{x_2}{x_2}+\dots+\dfrac{x_n}{x_n}}\leq\Big(\prod_{i=1}^{n}x^{x_i}_i\Big)^\dfrac{1}{P}\leq \frac{x_1\cdot x_1+x_2\cdot x_2+\dots+x_n\cdot x_n}{P}\\\Rightarrow\frac{P}{n}\leq \Big(\prod_{i=1}^{n}x^{x_i}_i\Big)^\dfrac{1}{P}\leq\frac{x_1^2+x^2_2+\dots+x_n^2}{P}\leq \frac{(x_1+x_2+\dots+x_n)^2}{P}=P$$

Hence $$\Big(\dfrac{P}{n}\Big)^P\leq\Big(\prod_{i=1}^{n}x^{x_i}_i\Big)\leq P^P$$

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