# how to estimate a polyhedron(convex hull) classifier from data sample

Given a set of points $X\in\Re^D$, they have labels $Y\in${$-1,+1$}. I would like to separate the data labeled +1 and the data labeled -1 by a polyhedron.

$min_w \sum_i \xi_i + \frac{1}{2}\|w\|_2^2$

subject to: $\xi_i > max_{j=1}^K[1-(w_j^Tx_i+b_j)]$, for $y_i=+1$

and $\xi_i > min_{j=1}^K[1+(w_j^Tx_i+b_j)]$, for $y_i=-1$ and $\xi_i > 0$, for all $i$.

Where K is the number of faces of the polyhedron, i represents each sample, j represents each face of the polyhedron. I assume that all positive data go inside the polyhedron while negative data are outside. Following the max-margin principle, we let the distance of the point to the face offset by a margin 1.

Optimizing with the first constraint is straightforward. But the second one seems difficult.

Is there anyway to optimize them in a fast way to the optimal?

-

The constraints of the second set (with the min over $j$) are not convex, since the minimum of a set of linear functions is concave. You will have to resort to non-convex optimization techniques that are generally slower to solve this problem.

-