# Computational complexity of maximizing sum of rational functions

I have a optimization problem:

$$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $$W_i$$, $$D_i$$ are constants and $$z_i$$ are integer variables. Assume each $$D_i >k$$.

The optimal solution obviously satisfies $$\sum_{i=1}^n z_i =k$$. But it seems there is no efficient way to get the optimum other than trying out all partitions.

Also, I know the above problem can be formulated as linear integer programming.

Is there any hint of proving the hardness of the above problem?

Suppose $$n-2$$ variables (without loss of generality, say $$z_3,\ldots,z_n$$) are fixed, then the objective becomes maximizing $$\frac{W_1}{D_1-z_1}+\frac{W_2}{D_2-z_2}$$ where $$z_1+z_2\le k-(z_3+\cdots+z_n):=K$$. Let $$f(z)=\frac{W_1}{D_1-z}+\frac{W_2}{D_2-(K-z)}, 0\le z\le K,$$ then $$f''(z)=\frac{2W_1}{(D_1-z)^3}+\frac{2W_2}{(D_2-K+z)^3}\ge0,$$ which means $$f(z)$$ is convex on $$[0,K]$$, thus the maximum value is achieved at either $$z=0$$ or $$z=K$$. This suggests that we can adjust an optimal solution such that either $$z_1=0$$ or $$z_2=0$$.
We can repeat this adjustment until there are only one non-zero variable among $$z_1,\ldots,z_n$$. So to solve your primary problem, just try the solutions $$(k,0,\ldots,0),(0,k,\ldots,0),\ldots,(0,\ldots,0,k)$$ and choose the optimal one among them.