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
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 '20 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$ Jul 20 '20 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$ Jul 20 '20 at 17:05
  • $\begingroup$ In this case all $x_i$ where $A_i=0$ must be 0, just like the general formula $\endgroup$ Jul 20 '20 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 '20 at 17:53

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.