Feasible sets represented as point clouds

Question

Does the situation in optimization ever occur in which you have a problem whose feasible set is not described in terms of explicit algebraic equations, but instead you have a large set of points that roughly approximates the feasible set?  If so, is there a term for this?
In my particular case I have a large set of samples that I know to be feasible, and the natural thing to do is surround them with balls of some fixed radius, and then use their union as my feasible set.  I'd like to know if this is delving into some well-studied area of optimization.

prubin · Answer

I don't think I've ever seen a name (let alone any research) for the case of having a collection of known feasible points but no explicit mathematical criteria for feasibility.
Before gluing together a bunch of balls, I would first ask whether the nature of the problem tells you anything about the shape of the feasible region. I'm assuming that your variables are not discrete, since the union of balls thing would not make sense for integer-valued variables (the union would contain non-integral points). Does the problem lead you to expect a convex feasible region? If so, the convex hull of your known feasible points would be a subset of the true feasible region (with no way of knowing how much of the feasible region you had not captured). If not convex, is there anything else you know about the feasible region based on the problem?

Feasible sets represented as point clouds

One Answer

Add your own answers!

Ask a Question