1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What differentiates this from a standard constrained optimization problem? $\endgroup$
    – user44191
    Jan 18, 2019 at 19:38
  • $\begingroup$ The paper you linked does not assume that the denominator is positive, and therefore does not take advantage of that. Your problem is much simpler and easier than that considered in the paper. See my answer. $\endgroup$ Jan 26, 2019 at 3:07

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.