4
$\begingroup$

\begin{align}\min&\quad\sum_{i=1}^N\frac{A_i}{x_i}\\\text{s.t.}&\quad\sum x_i \le X\\&\quad x_i \ge 0\end{align}

wherein $A_i>0, (i\in\{1,\dots,N\})$ is constant, $x_i, (i\in\{1,\dots,N\})$ is a continuous optimization variable.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

If some $A_i$ is negative the problem is unbounded: we can make the objective arbitrarily small by making $x_i$ arbitrarily close to 0.

Assuming $A_i \geq 0$, the optimality is obtained when all $\frac{A_i}{x_i^2}$ are equal (KKT optimality conditions), or equivalently all $\frac{x_i^2}{A_i}$ are equal, and $\sum x_i = X$ (otherwise you can increase some $x_i$ and reduce the objective).

Stating $x_i = \sqrt{A_i} y$, you can deduce $y = \frac{X}{\sum \sqrt{A_i}}$ from the equality.

Therefore $x_i = \frac{\sqrt{A_i}}{\sum \sqrt{A_j}}X$

$\endgroup$
9
  • $\begingroup$ This does not work if some $A_i=0$. $\endgroup$
    – RobPratt
    Jul 20, 2020 at 16:53
  • $\begingroup$ Yes. I was too lazy to spell it out, but you need an $A_i \gt 0$ for the equality to hold. Thanks $\endgroup$
    – Ggouvine
    Jul 20, 2020 at 17:02
  • $\begingroup$ (As far as I can tell you just need one, though. And if all are zero the problem is trivial) $\endgroup$
    – Ggouvine
    Jul 20, 2020 at 17:05
  • $\begingroup$ In this case all $x_i$ where $A_i=0$ must be 0, just like the general formula $\endgroup$
    – Ggouvine
    Jul 20, 2020 at 17:10
  • 1
    $\begingroup$ No, I mean if even one $A_i=0$ your argument that all $A_i/x_i^2$ are equal fails. Furthermore, you cannot have $x_i=0$ ever because it appears in the denominator of a summand in the objective. $\endgroup$
    – RobPratt
    Jul 20, 2020 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.