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.