Consider the problem

min

x

cTx $+$d

fTx$+$g

s$.$t$.$ Ax $<=$ b$,$

fTx$+$g $>0.$

Assume that the problem is feasible and there exists an optimal solution.

$($a$)$ Suppose that we have prior knowledge that the optimal value belongs to an interval

$[$K$,$L$].$ Provide an algorithm that uses LPs as a subroutine allows us to compute the

optimal value with any desired accuracy.

Hint: Consider a the problem of deciding whether the optimal cost is less than or

equal to a certain number and then perform a bisection search to find the $$right

number$.$

$($b$)$ Find way to estimate the numbers K and L in part $($a$)$