0

I would like to be directed to the proper literature regarding the following problem:

Given a constant sum of $x_n$ values:

$\sum_{n=1}^{N}{\left. {x_n}\right.} = C$

where $x_n ≥ 1$

Find the maximum of the following expression:

$\sum_{n=1}^{N}{\left. {a_n} \log{\left({x_n}\right) }\right.}$

where the $a_n > 0$ values are constants, and the $x_n$ values are free to change, given that their sum will remain constant.

What is the official name or category of this optimization problem? Could someone recommend a book or a website where it is explained how to solve it?

Crouching Kitten
  • 181
  • 7

1 Answers1

1

Calling $y_n = x_n - 1$ we have the equivalent problem

$$ \max \sum_{n=1}^N a_n\ln(y_n+1)\ \ \text{s. t.}\ \ \ \sum_{n=1}^N y_n = C-N $$

so the lagrangian reads

$$ L(y,\lambda) = \sum_{n=1}^N a_n\ln(y_n+1)-\lambda\left( \sum_{n=1}^N y_n - C + N\right) $$

The stationary points are the solutions for

$$ \nabla L = 0 = \left\{\begin{array}{rcl}\frac{a_n}{y_n+1}&=&\lambda\\ \sum_{n=1}^N y_n &=& C-N \end{array}\right. $$

substituting

$$ y_n = \frac{a_n}{\lambda}-1 $$

into the restriction we have

$$ \frac{1}{\lambda}\sum_{n=1}^N a_n-N = C - N $$

or

$$ \lambda = \frac 1C\sum_{n=1}^N a_n\Rightarrow y_n = \frac{a_n C}{\sum_{n=1}^N a_n}-1\Rightarrow x_n = \frac{a_n C}{\sum_{n=1}^N a_n} $$

expecting of course that $a_k, C$ are such that $\frac{a_n C}{\sum_{n=1}^N a_n}\ge 1$. Here, as $\log$ is an strict increasing function, there exist $C$ such that this positive condition is verified.

Cesareo
  • 33,252
  • Thank you, +1, I'll have a look at it when I get home. In the meantime I've found these videos from Khan Academy, which explained a lot: https://www.youtube.com/watch?v=yuqB-d5MjZA – Crouching Kitten Jul 03 '19 at 09:02
  • I understood it finally. Now I tried the same method on the linear combination of polynomials of degree 3, but it gets very messy after expressing $x_n$, and trying to substitute back into the sum constraint equation (because the lambdas are under a square root). Would you have any hints? – Crouching Kitten Jul 03 '19 at 14:16
  • Considering $x^3$ instead $\ln(x)$ we have $3a_nx_n^2=\lambda\to x_n = \sqrt{\frac{\lambda}{3a}}\to \lambda =3 \left(\frac{C^2}{\sum\sqrt{a_n}}\right)$ – Cesareo Jul 03 '19 at 15:55
  • Well I tried $f_n(x_n) = b_nx_n^3 + c_nx_n^2 + d_n*x_n + e_n$ But I guess this is a different issue now. Now I try certain tricks, like eliminating the odd powers. – Crouching Kitten Jul 03 '19 at 16:09