# How to maximize function $\sum_{i=1}^{\omega}\max(0, \log(x_i))$ under the constraint that $\sum_{i=1}^{\omega}x_i = S$

I am trying to maximize this function: $\sum_{i=1}^{\omega}\max(0, \log(x_i))$ given the constraint that $\sum_{i=1}^{\omega}x_i = S$.

If the function was just $\sum_{i=1}^{\omega}\log(x_i)$ I could just use Jensen's inequality and say that the maximum value is when each $x_i = \frac{S}{\omega}$ and so maximum value is $\sum_{i=1}^{\omega}\log(\frac{S}{\omega}) = \omega\log(\frac{S}{\omega})$.

Alternatively I could use Lagrange multipliers and derive the same outcome.

But in my case max function introduces non-continuity at i's where $x_i = 1$, so I suppose Lagrange multipliers is not applicable here...

I would like at least to find an upper bound of the sum I gave, as tight as possible under the constraint I gave, if it's not possible to derive the maximum value

Is $x_i$ allowed to be negative?
The optimal value will not have any $x_i \leq 1$, so you can add in another constraint $x_i \geq 1$.
Your problem is now $max(\sum log(x_i) : x_i \geq 1, \sum x_i = S)$. The objective function is now continuous in $x_i$, and you can use something like KKT conditions or steepest descent (or ascent in this case) to find the optimal value.
• $x_i$ is not allowed to be negative. In general $0 \leq x_i \leq S$. So $x_i$ can have values less than 1 – Curious_Dim Jan 18 '18 at 3:38
• If $x_i < 1$, then you can set it to 0 and thus remove it from the problem. – David Lui Jan 18 '18 at 5:41
• The problem in that case is I don't know how many of $x_i$'s are <1 . So I don't know in the new problem the limits of the sum – Curious_Dim Jan 18 '18 at 5:48
• if I don't know the sum limits in the constraint $\sum x_i = S$ then I cannot calculate the lagrange-KKT mutlipliers – Curious_Dim Jan 18 '18 at 19:49
• I would just guess. Any non-zero element must satisfy $x_i \geq 1$ (otherwise you can make the objective higher by setting $x_i = 0$ and increasing another variable by $x_i$). Only finitely many possibilities : $floor(S)$ to be exact – David Lui Jan 18 '18 at 22:09