Minimizing sum of ratio of linear functions (Sum of Linear Ratios Problem)

Question

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 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.

Answer 1

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.