Given $\lambda_1,\ldots,\lambda_n \geq 0$ and an $n\times n$ matrix $A$, I wish to maximize the ratio $$ \frac{\lambda_1x_1 + \cdots + \lambda_nx_n}{x_1+\cdots+x_n}, $$ where $x_1,\ldots,x_n \geq 0$ are not all zero and $A\mathbf{x} \leq \mathbf{0}$ assuming $\mathbf{x} = (x_1,\ldots,x_n)^T$.

I would like to formulate this problem as a linear program, but I am unsure how to proceed. I first thought of letting $y_i = x_i/(x_1 + \cdots + x_i + \cdots +x_n)$, but this doesn't seem to work. I feel like I should try to translate the problem to another equivalent problem which is easier to reason about. When dealing with fractions with the variables, how should one write an LP in canonical form?

Any hint or help would be greatly appreciated.

  • $\begingroup$ Try to google "Linear fractional program". There is a really standard way in transforming this to a linear program. $\endgroup$
    – Brian Ding
    Commented Feb 16, 2015 at 3:51

1 Answer 1


This is a linear fractional program. Note that if $x$ is a solution, then so is $\alpha x$ for any $\alpha>0$. You can take advantage of this by requiring the denominator be exactly 1, turning the result into an LP: \begin{array}{ll} \text{maximize} & \sum_i \lambda_i x_i \\ \text{subject to} & \sum_i x_i = 1 \\ & A x \leq 0 \\ & x \geq 0 \end{array}

  • $\begingroup$ I never heard of linear fractional programming. Thank you for the heads up! $\endgroup$
    – Hubble
    Commented Feb 16, 2015 at 3:54
  • $\begingroup$ No problem! Note that if the denominator had a constant term, it would take a little more work to convert it to LP form. Fortunately, the Wikipedia article covers that case. Yours happens to be simpler because the denominator has no constant term. $\endgroup$ Commented Feb 16, 2015 at 3:56
  • $\begingroup$ Correction: your problem is easier because both the numerator and the denominator lack a constant term. $\endgroup$ Commented Feb 16, 2015 at 14:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .