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?