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!
Hmm. you're computing the max of the lower envelope of a collection of trig functions. not sure why it's EVER convex except on the line, where it reduces to the min of the x_i.
ReplyDeleteWell I could apply the polar transformation to the SVM program and also make it non-convex in $r$ and $\theta$. But SVM is convex in $w$ and $b$.
ReplyDelete