0
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Jamal B.
    May 13, 2019 at 21:28
  • $\begingroup$ 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. $\endgroup$
    – LarrySnyder610
    May 13, 2019 at 23:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .