Thursday, December 13, 2012

Pop Quiz

Yesterday I was chatting with Professor 1 about some research when Professor 2 came in very excitedly and described a problem that he wanted to solve with P1's help. I'm simplifying this a bit, but the problem is the same:

Given a set of points $x_i$, find a linear discriminator $w$ and a bias $b$ so that all of the points $x_i$ are on the "positive" side of the hyperplane described by $w$ and $b$. Easy enough, but also make sure that $b$ is as large as possible (in the signed sense). In other words,

$$\max b \quad\textrm{s.t. }\|w\|^2 \leq 1\textrm{ and }w'x_i \geq b.$$

P2 and I were convinced by the formulation that this is a convex program and should be straightforward to solve.

P1 says nope. Not a convex problem in general. P1 is correct. What's the exception? And why isn't the problem convex in this case?

P.S. P1, you are not allowed to spoil the solution!