Given a non-convex differentiable function $f$ and a set $S$ of possible input vectors for function $f$. I am trying to find the (global) optimum input vector out of the possibilities in set $S$. Linear search can't be applied because of the size of set $S$. So probably the most common way to do it is using e.g. heuristics, but then IMHO there are two possible approaches, and I am not sure which is better (or if maybe there are other ways):
- Only trying the possible vectors (from set $S$) in my heuristic and iteratively getting to some approximate
- By not considering it as a combinatorial problem, and just finding the approximate optimum of $f$ and afterwards searching for the nearest neighbor in set $S$ (e.g. maybe using R* trees or similar data structures)
Which solution is better? I feel like solution 1 doesn't use the differentiable property of function $f$ in any way. Are there better solutions, even exact ones?
This seems like a classic sort of setup for combinatorial optimization heuristics. Most work like your approach #1. Approach #2 is interesting but is less common. (Some metaheuristics allow the solution to become infeasible (leave $S$) for a while, but then try to get back to feasibility.)
But in any case, in situations like this, it's often very hard to know ahead of time what will work well and what won't -- you'll have to experiment with different methods.
(Of course, if it's a well-known problem like TSP or network design or something, then there's lots of literature out there and you can rely on that instead of your own experimenting.)
About the differentiability of $f$, I'm not sure it's possible to use that in meaningful ways, since $S$ is a discrete set. (Wait -- is it? Your question doesn't say it's discrete, but you tagged it as discrete optimization and put combinatorial optimization in the title, so I am assuming.)