# Combinatorial optimization of non-convex differentiable function

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):

1. Only trying the possible vectors (from set $$S$$) in my heuristic and iteratively getting to some approximate
2. 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.)
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.)
• Thanks so far. Yes $S$ is discrete. So there is no useful information which can be gained from the gradient? The gradient could be useful for approach #2. You say it's less common, can you name some example works on this topic? – Jamal B. May 13 at 21:28
• Are you thinking of $S$ as the set of integer points in a larger region? I think I was thinking of $S$ as a feasible set that might be defined by other types of constraints. Metaheuristics sometimes allow the solution to leave $S$ and then come back to it. But now I think you are suggesting solving the continuous relaxation, then essentially rounding to get the nearest integer point? If so, I think that could work, provided that (a) you have a good enough method for doing the global optimization, and (b) your objective function is "flat" enough that it contains a bunch of integer points. – LarrySnyder610 May 13 at 23:17