Given constants $c\_i \in \mathbb{R}$ and $d\_i \in \mathbb{R}$ and variables $x\_i \in \mathbb{R}$, where $c\_i > 0, d\_i > 0, x\_i > 0$ can we easily solve the following optimization problem:


$$min\_{x\_i} \sum\_i \frac{1}{c\_i + d\_i x\_i}
$$
subject to $\sum\_i x\_i = C$, where $C > 0$ is another constant.


If it helps $C$ and $x\_i$ can also be restricted to be integers. In that case there is a naive solution where we enumerate all combinations. This is still too expensive though.


I found the paper [A Global Optimization Algorithm for Sum of Linear Ratios Problem](https://www.hindawi.com/journals/jam/2013/276245/) that talks about a general version of the above problem but it is somewhat involved.


I am wondering if there is a simpler solution since the above problem looks like a special case.



Minimizing sum of ratio of linear functions (Sum of Linear Ratios Problem)
Because the denominator must be positive, the objective function, and hence the optimization problem is convex, and can be readily formulated and solved using CVX or a similar convex optimization tool.



```
cvx_begin
variable x(n)
minimize(sum(inv_pos(c + d.* x)))
x >= 0
sum(x) == C
cvx_end

```

You change `x >= 0` to `x >= small_number` if you prefer. Strict inequalities are treated by the solvers as if they are non-strict inequalities.


It does not help to restrict x to integer values. That would make the problem more computationally difficult to solve. Nevertheless, to do so, merely change `variable x(n)` to `variable x(n) integer` .


Here is a test problem without integer restriction:



```
>> n=6; C=7.4 ;c = 5*rand(n,1); d = 2*rand(n,1);
>> disp(c)
   2.107028387658593
   0.400055793339331
   0.396769045866593
   0.361881245993311
   4.501705030405445
   4.846541494332056

>> disp(d)
   0.782613917623122
   0.627170209734511
   1.106627159874890
   1.584096124994781
   1.596628166160420
   1.726517081119803

```

and here is the output from running the above program:



```
Calling SDPT3 4.0: 25 variables, 12 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 12
 dim. of sdp    var  = 12,   num. of sdp  blk  =  6
 dim. of linear var  =  6
 dim. of free   var  =  1 *** convert ublk to lblk
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|1.7e+01|3.4e+00|1.9e+03| 1.261398e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|1.000|0.598|3.9e-06|1.4e+00|5.6e+02| 1.429249e+02 -3.878636e+01| 0:0:00| chol  1  1 
 2|1.000|0.966|1.0e-06|4.9e-02|7.2e+01| 5.719567e+01 -6.592350e+00| 0:0:00| chol  1  1 
 3|1.000|0.540|2.8e-08|2.3e-02|1.0e+01| 3.460381e+00 -5.835158e+00| 0:0:00| chol  1  1 
 4|1.000|0.442|1.6e-07|1.3e-02|4.8e+00|-2.227469e-01 -4.589011e+00| 0:0:00| chol  1  1 
 5|0.921|0.925|1.7e-08|9.6e-04|4.7e-01|-1.759148e+00 -2.201532e+00| 0:0:00| chol  1  1 
 6|1.000|0.575|1.1e-09|4.1e-04|1.7e-01|-1.906104e+00 -2.063560e+00| 0:0:00| chol  1  1 
 7|0.981|0.919|3.2e-09|3.3e-05|1.3e-02|-1.939996e+00 -1.951918e+00| 0:0:00| chol  1  1 
 8|0.961|0.971|2.6e-10|9.6e-07|3.9e-04|-1.941595e+00 -1.941964e+00| 0:0:00| chol  1  1 
 9|0.956|0.918|7.3e-11|9.8e-07|3.3e-05|-1.941656e+00 -1.941686e+00| 0:0:00| chol  1  1 
10|0.980|0.964|1.7e-11|8.4e-08|1.6e-06|-1.941660e+00 -1.941661e+00| 0:0:00| chol  1  1 
11|1.000|0.966|3.2e-13|3.9e-09|1.3e-07|-1.941660e+00 -1.941660e+00| 0:0:00| chol  1  1 
12|1.000|0.984|4.6e-14|3.2e-10|5.5e-09|-1.941660e+00 -1.941660e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 12
 primal objective value = -1.94166032e+00
 dual   objective value = -1.94166032e+00
 gap := trace(XZ)       = 5.46e-09
 relative gap           = 1.12e-09
 actual relative gap    = 1.02e-09
 rel. primal infeas (scaled problem)   = 4.58e-14
 rel. dual     "        "       "      = 3.23e-10
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 2.7e+00, 4.2e+00, 1.0e+01
 norm(A), norm(b), norm(C) = 6.9e+00, 3.4e+00, 1.4e+01
 Total CPU time (secs)  = 0.20  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 7.9e-14  0.0e+00  5.4e-10  0.0e+00  1.0e-09  1.1e-09
-------------------------------------------------------------------

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +1.94166

>> disp(x) % this is the optimal value of x
   0.399054349910791
   2.815385122487830
   2.241149560765849
   1.944410952569123
   0.000000007535945
   0.000000006728979

```

The last 2 elements of x would be exactly zero if the optimization problem were solved exactly. The slight difference from zero is due to solver optimality tolerance.


