0

I am stuck on this question:

Consider the problem:

$\underset{x}{\text{minimize}}{\frac{c^{T}x+d}{f^{T}x+g}}$

$\text{s.t. } Ax\leq b$

$f^{T}x+g>0$

Suppose we have prior knowledge that the optimal cost belongs to an interval [K,L]. Provide a procedure that allows us to compute the optimal cost within any desired degree of accuracy using a linear programming subroutine.

Attempt at solution: I considered fixing $t$ between [K,L], and then rewriting the problem as:

$\underset{x}{\text{minimize }}{t}$

$\text{s.t.}\frac{c^{T}x+d}{f^{T}x+g}\leq t$

$Ax\leq b$

$f^{T}x+g>0$

Repeat this procedure for every $t$ between [K,L] and choose the smallest feasible $t$. I'm not sure if this makes sense though, since we are minimizing a constant...

Jessica
  • 1

1 Answers1

1

Hints:

1) The objective returned by the linear programming subroutine might be less important than whether it finds the problem feasible or infeasible.

2) $\dfrac{c^T x + d}{f^T x + g} \le t$ is not a linear constraint, but there is a linear constraint equivalent to it (since we know $f^T x + g > 0$).

3) There are infinitely many $t$ between $K$ and $L$. You don't really want "every" such $t$.

Robert Israel
  • 448,999