3
$\begingroup$

This is not a homework problem. It is from a closed MITs 2016 advanced algorithms class.


Question


Here is my proposed solution:

We can run the linear program

$$\begin{array}{ll} \text{maximize} & f^T x\\ \text{subject to} & A x \geq b\\ & f^T x \geq 1\\ & -8 \leq c^T x \leq 8\end{array}$$

If the linear program is infeasible then the problem is infeasible, and if the linear program is unbounded then the solution is $0$. Suppose neither of these is the case. Then $ -8\leq \frac{c^Tx}{f^Tx} \leq 8$, and the idea is to do binary search until the possible interval that $\frac{c^Tx}{f^Tx}$ lies in is of size $\leq \epsilon$.

So for the $i$th iteration of the algorithm suppose $ L \leq \frac{c^Tx}{f^Tx} \leq U$. $\frac{c^Tx}{f^Tx} \leq \frac{L+U}{2}$ if and only if $c^Tx - \frac{(f^Tx)(L+U)}{2} \leq 0$, since $ f^Tx \geq 1$. So if we run the linear program,

$$\begin{array}{ll} \text{minimize} & c^Tx - \frac{(f^Tx)(L+U)}{2} \\ \text{subject to} & A x \geq b\\ & f^T x \geq 1\\ & -8 \leq c^T x \leq 8\end{array}$$

, and we get a value of $0$ or less, then we have $ L \leq \frac{c^Tx}{f^Tx} \leq \frac{U + L}{2}$, else we have $ \frac{L + U}{2} \leq \frac{c^Tx}{f^Tx} \leq U$. We then repeat this process until $U-L \leq \epsilon$ and we take $U$ as our answer.

The running time of this algorithm is $k$, where $\frac{16}{2^k} \leq \epsilon$ so $k\leq \log(\frac{16}{\epsilon})$.

Is this a correct solution to the problem?

Edit: There is actually a $O(\frac{1}{\epsilon})$ solution(by someone else); However I'm still not sure if my $O(log(\frac{1}{\epsilon}))$ solution is any good.

$\endgroup$
7
  • $\begingroup$ I haven't learned about the epigraph form(from the course) yet, so I don't know what that is. However, does this mean that my solution is not correct? Also when I ran the first linear program to maximize $f^Tx$ it should have told me whether $\frac{c^Tx}{f^Tx}$ is feasible or not. It also seemed like all the linear programs I run in my solution have linear constraints and linear objective functions, so I should be able to input them in the black box mentioned in the question. $\endgroup$
    – Jarry
    Commented Jul 4, 2021 at 16:34
  • $\begingroup$ I also just minimize $c^Tx-\frac{(f^Tx)(L+U)}{2}$ in order to see whether or not there exist an x such $\frac{c^Tx}{f^Tx} \leq \frac{L+U}{2}$. I think I can do this because as explained above $f^Tx$ is positive. $\endgroup$
    – Jarry
    Commented Jul 4, 2021 at 16:37
  • $\begingroup$ It's ok thankyou anyways. Will you have time so another day? And also is my solution, not clear. Since I haven't been receiving any responses. $\endgroup$
    – Jarry
    Commented Jul 4, 2021 at 16:42
  • $\begingroup$ Ok, but I don't understand why instead of doing that we just run the linear program I said above (minimize $c^Tx-\frac{(f^Tx)(L+U)}{2}$) to find an upper bound/ lower bound for $\frac{c^Tx}{f^Tx}$. Since we know in the worst case there will be a feasible solution when $-8 \leq \frac{c^Tx}{f^Tx} \leq 8$. $\endgroup$
    – Jarry
    Commented Jul 4, 2021 at 16:58
  • 1
    $\begingroup$ Please understand that I don't know you. I do not recall any other posts of yours around here. Which means I am not familiarised with your way of thinking. This does not mean that your work is not interesting. It just means that understanding your work in detail requires more than what my time-energy budget allows. When such budget allows, I will try to revisit this question. $\endgroup$ Commented Jul 4, 2021 at 19:39

1 Answer 1

2
$\begingroup$

Hint: Introduce optimization variable $y$, make the objective $y$ and append the constraint $$\frac{c^Tx}{f^Tx} \leq y$$ Note that the denominator is positive. Then, pick, say, $y =2$ and use linear programming to determine whether the constraints define an empty polytope or not. If the polytope is non-empty, then pick, say, $y = 1$ and so on. Once you find an empty polytope, use binary search to adjust $y$ till you find a "decent" approximation for the minimum. My guess is that this is what the authors meant by "within any degree of accuracy".

$\endgroup$
0

You must log in to answer this question.

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