1
$\begingroup$

Let $1 \leq m < M$ and let $\alpha_1, \dots, \alpha_n > 0$ be fixed real numbers. I want to solve the following $n$-dimensional optimization program

$$\begin{array}{ll} \underset{\alpha_1, \dots, \alpha_n}{\text{minimize}} & \displaystyle\sum_{i=1}^n \alpha_i \frac1{x_i}\\ \text{subject to} & \displaystyle\sum_{i=1}^n x_i \leq M\\ & m \leq x_i\end{array}$$

I have done some quadratic programming but I have no idea to solve this type of problem.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Since increasing any of the $x_i$'s will lower the object function, we can replace the first constraint by an equality constraint.

Also, we can define new variables $y_i = x_i-m $, so that the second constraint is $y_i \ge 0.$

We have $$\min \sum_{i=1}^n \frac{\alpha_i }{y_i+m}$$

$$\textrm{s.t. }\sum_{i=1}^n y_i = M-n m = K$$

$$ y_i \ge 0$$

Looks like we must have $M \ge nm$ in your problem statement.

Anyway, using Lagrange multipliers,

Let $$L = \sum_{i=1}^n \frac{\alpha_i }{y_i+m} + \lambda \sum_{i=1}^n ( y_i -K). $$

Find $\frac{ \partial L }{\partial y_i}$ and $\frac{ \partial L }{\partial \lambda}$ and set these equal to zero.

$$0=\frac{ \partial L }{\partial y_i}= \lambda - \frac{\alpha_i }{(y_i+m)^2},$$

$$\sum_{i=1}^n y_i =K.$$

Solving for $y_i$,

$$y_i =\sqrt{\frac{\alpha_i}{\lambda}} - m.$$

Summing this, we get an expression for $\lambda:$

$$K= \sum_{i=1}^n \sqrt{\frac{\alpha_i}{\lambda}} - mn$$

$$M= \sum_{i=1}^n \sqrt{\frac{\alpha_i}{\lambda}} $$

$$ \lambda = \left( \frac{\sum_{i=1}^n \sqrt{\alpha_i}}{M} \right)^2.$$

Solving for $y_i$ and substituting to find $x_i$:

$$x_i = \frac{M \sqrt{\alpha_i} }{\sum_{i=1}^n \sqrt{\alpha_i}}.$$

Actually, we are not done! We have to check that each $x_i \ge m$ (or each $y_i\ge 0$). Could happen not. In that case, set any negative $y_i$ equal to zero: ($\forall i, \textrm{s.t.} y_i<0,$ $y_i \rightarrow 0$) and solve the problem again for the remaining variables.

$\endgroup$
5
  • $\begingroup$ So $x_i = \sqrt{\frac{\alpha_i}{\left(\sum \frac{\alpha_i}{M}\right)^2}}$? $\endgroup$
    – ABIM
    Commented May 3, 2020 at 18:26
  • $\begingroup$ Yes, (with a square root on the $\alpha_i$ in the denominator). $\endgroup$
    – mjw
    Commented May 3, 2020 at 18:48
  • $\begingroup$ $x_i = \frac{M \sqrt{\alpha_i} }{\sum \sqrt{\alpha_i}}.$ $\endgroup$
    – mjw
    Commented May 3, 2020 at 18:49
  • $\begingroup$ right my mistake. Thanks mjw! $\endgroup$
    – ABIM
    Commented May 3, 2020 at 19:50
  • $\begingroup$ We also have to check that each of the $x_i \ge m$. If not, set $x_i=m$ and solve again for the remaining variables. Repeat! $\endgroup$
    – mjw
    Commented May 4, 2020 at 2:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .