3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think it would immensely help if you can define what roughly means. One can think of various ways to approximate, and each approximation may lead to a different sub-branch of optimization with which one can potentially attack the problem. So if you can be more specific the community will be able to answer better. $\endgroup$
    – batwing
    Jul 16, 2020 at 21:05

1 Answer 1

3
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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