How to solve MNP (minimum norm) problem in SVM?

Question

I'm reading an article, which says that MNP (minimum norm problem) can be solved as SVM. In the minimum norm problem, we're given a set of points in $R^d$ and need to find a point in convex hull of our points closest to the origin.

In SVM method we're minimizing the lagrangian $$\mathcal{L}(w, b, \alpha) = \dfrac{1}{2}||w||^2 + \sum_{i = 1}^m \alpha_i [y_i(w^Tx - b) - 1].$$ i.e.in dual-form maximizing the function $W(\alpha):$ $$\max_\alpha W(\alpha) = \sum_{i = 1}^m \alpha_i - \dfrac{1}{2}\sum_{i, j = 1}^m y^{(i)}y^{(j)}\alpha^{(i)}\alpha^{(j)}<x^{(i)}, x^{(j)}>.$$

1) How we can apply it for MNP-problem? Probably, 0 (origin) would stand for one support vector and the closest-point from the convex hull is for another.

2) But how will it look like a dual-form of the problem?

3) Will be $y_i$ labels $y_i = 1$ for any point of convex hull and $y_i = -1$ for origin?

4) And how can i find(if i can) $\alpha_i$ (Lagrange multipliers)?

Answer 1

I guess that if you perform a crisp linear SVM classifier between two groups, one of it being your data and the other being the null vector, either the algorithm will fail because 0 is in the convex hull of those points (groups not linearly separable), or a solution will be found, where one of the SVs will clearly be 0, and the other k vectors define the k-face of the hull nearest to the origin.

Answer 2

Quoting from this article:

the solution of the linearly separable classification problem is equivalent to finding the points of the two convex hulls [21] (each generated by the training patterns of each class) which are closest to each other and the maximum margin hyperplane a) bisects and b) is normal to the line segment joining these two closest points

So yes, you should classifying your points as belonging to one-class, and the other class should just be the origin. You should have some support vectors, as well as the classifying norm. If there's a single support vector then it is the closest point. Otherwise, you can just take the $w$ vector and see where it intersects the tangential $w'$ that goes through the support vectors (assuming separability). For non-separable case, one could still follow a similar approach, however one would have to check the intersection for each support vector separately in order to find the point closest to the origin.