8
$\begingroup$

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?

$\endgroup$
7
  • 3
    $\begingroup$ Linear-fractional Programming - conversion to Linear Programming problem en.wikipedia.org/wiki/… $\endgroup$ Aug 30, 2022 at 14:38
  • 2
    $\begingroup$ For the transformation suggested by @MarkL.Stone, note that you will need a separate $t_i$ for each summand that appears in the objective. $\endgroup$
    – RobPratt
    Aug 30, 2022 at 14:57
  • $\begingroup$ @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 ? $\endgroup$
    – ghiloka
    Aug 30, 2022 at 15:00
  • $\begingroup$ @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 ? $\endgroup$
    – ghiloka
    Aug 30, 2022 at 15:05
  • 1
    $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Aug 30, 2022 at 16:19

1 Answer 1

10
$\begingroup$

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;
$\endgroup$
5
  • $\begingroup$ Great answer . I implemented this method in cvxpy and it gives the right maximum . Thanks ! $\endgroup$
    – ghiloka
    Aug 30, 2022 at 21:04
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 30, 2022 at 23:50
  • 1
    $\begingroup$ @MarkL.Stone I updated my answer to demonstrate similar newly added functionality in SAS. $\endgroup$
    – RobPratt
    Oct 20, 2022 at 16:31
  • $\begingroup$ 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. $\endgroup$ Oct 20, 2022 at 17:02
  • $\begingroup$ @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/… $\endgroup$
    – iulian
    Dec 20, 2022 at 16:26

Your Answer

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

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