Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.