0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ $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 $\endgroup$ – Curious_Dim Jan 18 '18 at 3:38
  • $\begingroup$ If $x_i < 1$, then you can set it to 0 and thus remove it from the problem. $\endgroup$ – David Lui Jan 18 '18 at 5:41
  • $\begingroup$ 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 $\endgroup$ – Curious_Dim Jan 18 '18 at 5:48
  • $\begingroup$ if I don't know the sum limits in the constraint $\sum x_i = S$ then I cannot calculate the lagrange-KKT mutlipliers $\endgroup$ – Curious_Dim Jan 18 '18 at 19:49
  • $\begingroup$ 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 $\endgroup$ – David Lui Jan 18 '18 at 22:09

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.