# Geometric program with reciprocal objective function

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.

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.

• So $x_i = \sqrt{\frac{\alpha_i}{\left(\sum \frac{\alpha_i}{M}\right)^2}}$?
– ABIM
Commented May 3, 2020 at 18:26
• Yes, (with a square root on the $\alpha_i$ in the denominator).
– mjw
Commented May 3, 2020 at 18:48
• $x_i = \frac{M \sqrt{\alpha_i} }{\sum \sqrt{\alpha_i}}.$
– mjw
Commented May 3, 2020 at 18:49
• right my mistake. Thanks mjw!
– ABIM
Commented May 3, 2020 at 19:50
• 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!
– mjw
Commented May 4, 2020 at 2:06