Homework 1 — comments

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 r \leq | a_i c - b_i|, 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 size(det(A)) 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 det(A) potentially has a small numerical value).


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: