Solving maximization problem with linear-fractional sum

Question

I want to solve this problem :

Maximize \begin{equation} \sum_{i=1}^{n} \frac{x_i}{a_ix_i + b_i}\end{equation} with the constraints \begin{equation}\sum_{i=1}^{n}x_i = S \ , \ x_i \geq 0 \ \forall \ i \end{equation} where $ a_1 , ... , a_n , b_1 , ... , b_n , S > 0$ are known .

Note that the functions \begin{equation}f_i(t) = \frac{t}{a_it + b_i} \end{equation} are strictly increasing and concave on $ (0 , \infty) $

How can I solve this?

Answer 1

Here's a second-order cone formulation, obtained by rewriting the objective function as $$\sum_i \frac{1}{a_i} \left(1 - \frac{b_i}{a_i x_i + b_i}\right)$$ and introducing $z_i$ to represent the denominator and $y_i$ to represent $1/z_i$: \begin{align} &\text{maximize} &\sum_i \frac{1}{a_i} (1 - b_i y_i) \\ &\text{subject to} & \sum_i x_i &= S \\ && z_i &= a_i x_i + b_i &&\text{for all $i$}\\ && w &= \sqrt 2 \\ && 2 y_i z_i &\ge w^2 &&\text{for all $i$} \tag1\label1\\ && x_i &\ge 0 &&\text{for all $i$}\\ && y_i &\ge 0 &&\text{for all $i$} \end{align} Constraint \eqref{1} is a rotated second-order cone constraint. Everything else is linear.

---

Update: The reformulation above arose from the development version of a new conic transformation feature in SAS, available in production today. The following SAS code demonstrates the automatic transformation from algebraic form:

/* generate random input data */
%let n = 3;
%let s = 2;
data indata;
   do i = 1 to &n;
      a = rand('UNIFORM');
      b = rand('UNIFORM');
      output;
   end;
run;

proc optmodel;
   /* declare parameters and read data */
   set OBS;
   num a {OBS};
   num b {OBS};
   read data indata into OBS=[i] a b;

   /* declare optimization problem */
   var X {OBS} >= 0;
   max Objective = sum {i in OBS} (1 / a[i]) * (1 - b[i] / (a[i] * X[i] + b[i]));
   con C: sum {i in OBS} X[i] = &s;

   /* optionally expand reformulated problem */
   expand / conic;

   /* call conic solver (automatically reformulating under the hood) */
   solve with conic;

   /* print solution */
   print a b X;
quit;