Consider the following maximization problem:

$$\max_{(x_1,\dots,x_n)\in \mathbb{R}^n}{f(\mathbf{x})=\prod_{i=1}^n x_i^{\alpha_i}}$$

subject to

$$ \sum_{i=1}^n x_i = c; \ 0\leq a_i \leq x_i \leq b_i \ \forall i \in 1,\dots, n$$

I'm not sure the right term for $f$ is multinomial: I guess that would be the correct nomenclature of all $\alpha_i$ were integer, but that's not necessarily the case. Anyway, I'd like to solve this optimization problem. My first idea was to take the log of $f$, in order to deal with a linear objective function. However, that would mess up with the first constraint (the others constraints would be fine). So what could be the best approach? Is there some specific algorithm I could use?

  • 1
    $\begingroup$ You might note that (if all $a_i > 0$) maximizing $f(x)$ is equivalent to maximizing $\log f(x) = \sum_i \alpha_i \log(x_i)$. If all $\alpha_i > 0$ that is a concave function. $\endgroup$ – Robert Israel Apr 13 '17 at 18:23
  • $\begingroup$ @RobertIsrael I noticed that too (and I do have to check if all $\alpha_i$ are positive: I'll let you know). But what about the first constraint? After taking logs, it wouldn't be linear anymore, so I couldn't use linear programming. Right? $\endgroup$ – DeltaIV Apr 13 '17 at 18:28
  • 1
    $\begingroup$ It's not linear programming, but (if the $\alpha_i$ are positive) it is convex programming, which these days is almost as good. $\endgroup$ – Robert Israel Apr 13 '17 at 18:31
  • 1
    $\begingroup$ For example, in Maple the Optimization package should be able to handle it if $n$ is not too huge. $\endgroup$ – Robert Israel Apr 13 '17 at 18:33
  • 1
    $\begingroup$ A sum of concave functions is concave. $\alpha_i \log(x_i)$ is concave. $\endgroup$ – Robert Israel Apr 13 '17 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.