optimization problem: finding an hyperplane separating one point from a set of pointy maximizing the distance

Question

I have this problem:

I have a set of n-dimensional points $P$. I have one more n-dimensional point $q$.

The points in $P$ are linearly separable from $q$ (i.e. it always exists an hyperplane $n^t x + d = 0$ leaving $q$ on one side and all the points on the other side).

I'm trying to find the hyperplane (n, d) that best separates the points, using as optimality criteria maximizing the distance from the hyperplane and q.

I'm trying to solve this problem by local optimization (i.e. gradient descent), but I'm having trouble defining a cost function that achieves the best solution possible (I'm stuck in finding some "equilibria" hyperplane which is somewhere between P and q, but is not sticking to some points in $P$).

Here's a figure in R² to clarify the problem:

the magenta point is $q$ and the blue points are the points in $P$. the blue line shows an hyperplane (not the optimal one, which would be passing for at least two points of $P$)

any idea?

Answer 1

I think what you want here is just a special case of the typical linear support vector machine. In most SVM applications you'll have multiple points on each side of the hyperplane, but there's nothing wrong with having just one here. The SVM will require solving a quadratic program or second-order cone program with $n+1$ variables, I believe, and $|P|+1$ inequalities.

Furthermore, the maximum margin classifier will typically return the hyperplane in the center of the gap as well as the margin; but all you would need to do is shift the hyperplane away from $q$ and towards the points $P$ by that margin.

Answer 2

• Construct the convex hull of $P$, thereby reducing the number of points in the set that you actually care about. (This picks out extremal points and ignores "interior" points.) Call the hull $H$.
• Find the distance from each point in $H$ to $q$. Let the point with smallest distance by $h$.
• For (first, trial) separating plane, use the plane through $h$ perpendicular to the line from $q$ to $h$. Call it $S$. This plane may fail to separate $q$ and $P$.
• Check that no points of $P$ are on the wrong side of $S$. If there are none, then you are done. ($P$'s hull had a vertex poking out at $q$.)
• If there are points of $P$ on the wrong side of $S$, then the optimal plane is parallel to and contains one of the simplices in $H$ containing some or all of the points $h$ and those $P$ on the wrong side of $S$. Iterate through these simplices finding which produces a plane closest to $q$. ($P$'s hull presents a "face" or an "edge" to $q$.)