# A linear program for maximizing a fraction

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.

• Try to google "Linear fractional program". There is a really standard way in transforming this to a linear program. – Brian Ding Feb 16 '15 at 3:51

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}