3

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.

Hubble
  • 2,966
  • 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 03:51

1 Answers1

6

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}

Michael Grant
  • 19,450
  • I never heard of linear fractional programming. Thank you for the heads up! – Hubble Feb 16 '15 at 03:54
  • 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. – Michael Grant Feb 16 '15 at 03:56
  • Correction: your problem is easier because both the numerator and the denominator lack a constant term. – Michael Grant Feb 16 '15 at 14:37