# Solving maximization problem with linear-fractional sum

I want to solve this problem :

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

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

How can I solve this?

• Linear-fractional Programming - conversion to Linear Programming problem en.wikipedia.org/wiki/… Commented Aug 30, 2022 at 14:38
• For the transformation suggested by @MarkL.Stone, note that you will need a separate $t_i$ for each summand that appears in the objective. Commented Aug 30, 2022 at 14:57
• @Mark L. Stone Thank you for your response . But how can I apply this method if I want to maximize a sum of linear fractions not only one linear fraction ? Commented Aug 30, 2022 at 15:00
• @RobPratt Could you give more details please ? From the wikipedia page it seems this method works for linear fractions but my objective is a sum of linear fractions . Is there are more general method ? Commented Aug 30, 2022 at 15:05
• Sorry, what I suggested does not work when you have constraints across $i$. Without that constraint $\sum_i x_i=S$, you would multiply numerator and denominator of each summand by a new variable $t_i$, introduce $y_i$ to represent the product $t_i x_i$, and maximize $\sum_i y_i$ subject to $a_i y_i+b_i t_i=1$, $t_i \ge 0$, and $y_i \ge 0$. Commented Aug 30, 2022 at 16:19

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;

• Great answer . I implemented this method in cvxpy and it gives the right maximum . Thanks ! Commented Aug 30, 2022 at 21:04
• @ghiloka If using CVXPY (or CVX), you can directly use inv_pos, which will do the SOCP formulation for you under the hood, including adding any needed auxiliary variables. I.e., you will essentially input (what in CVX would be) objective sum(1/a.*(1-b.*inv_pos(a.*x+b))) and constraints sum(x) == S and x >= 0, and let CVX(PY) handle the rest. under the hood. Commented Aug 30, 2022 at 23:50
• @MarkL.Stone I updated my answer to demonstrate similar newly added functionality in SAS. Commented Oct 20, 2022 at 16:31
• Maybe it's time to update the company and product names to SOAS. Statistical and Optimization Analysis System. Good to see you are on the road to being a conehead. Commented Oct 20, 2022 at 17:02
• @ghiloka, do you mind sharing your python solution? I have a similar problem to solve (except mine has c*x at the numerator), but I have troubles translating the solution into working CVXPY code... I've created a room where we could further discuss, if you will be so kind to share it chat.stackexchange.com/rooms/141441/… Commented Dec 20, 2022 at 16:26