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

Question

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?

Answer 1

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.

Answer 2

The 1992 paper "Separation and approximation of polyhedral objects" by Joseph Mitchell and Subhash Suri seems relevant:

In this paper, we present efficient approximation algorithms for constructing separating families of near-optimal size.

They approximate because:

Not surprisingly, most variants of the general polyhedral separability problem are also intractable.

You can use Google Scholar to search forward in time for those 43 later papers that cite this one.