Homework 1 is graded. The average was 17/20. Here are some comments on your solutions:
1. Several people erred by claiming that if P is nonempty it has a basic feasible solution. This is true for LPs in equational form, but not in the general form described in the problem. Most everybody had the idea of trying to turn inequalities into equalities; however only some people saw the observation that if turning an inequality into an equality makes the LP infeasible, then you can actually throw away the inequality. A few people solved the problem by using the result of Q4 and then doing binary search — that’s acceptable.
2. Most people more or less got this. Only Nathaniel made the observation that we kind of screwed up the definition in 2b: a weakly separating hyperplane always exists if you’re allowed to take a = 0, b = 0! (The proper definition should disallow a = 0.)
3. Again, most people got this. Some of you made small mistakes with the signs. A couple solutions left things in the form , and either did not attempt to say why this was OK in an LP (it is not!), or claimed the techniques of problem 2 handled this case (they don’t, since the solution space is not convex in this case!) — you’ve got to be careful with absolute values in LPs.
4. Here a common mistake was to bound the maximum numerical value of the determinant and claim that was at most the log of that quantity. But note that the size of the determinant could be large also because its value is a rational number with a huge denominator (and hence requires a lot of bits to write down, even though potentially has a small numerical value).
Leave a Reply