I've got a function of form $$f: (\mathbb{Z}_3)^n \rightarrow \mathbb{R}$$ to optimize, where $n$ is relatively large (the order of hundreds).

Is it there a gradient-like notion for these type of functions? Or does it make sense to define one?

Thank you.

• How do you define a derivative of a function with discrete domain? – Guido Kanschat Jul 21 '13 at 14:44

In many cases it's possible to extend $f$ to a function that maps $R^{n}$ (actually $[0,2]^{n}$) to $R$. If that function is convex and preferably differentiable (so that it has a gradient), then you can use conventional continuous optimization techniques to minimize the extended function. However, rounding off the minimum of the extended function is not sufficient to get a minimum of the original function. Rather, you would typically embed this into a branch and bound algorithm to find a minimum of the original function.
• Is branch and bound suitable for problems where $n > 500$ ? – user92382 Jul 22 '13 at 5:18
• It depends a lot on the particular function that you're dealing with. Some integer nonlinear programming problems with $n$ as big as 500 have certainly been solved, but other problem instances can be practically impossible to solve at much smaller sizes. You can also look at heuristic methods (simulated annealing, genetic algorithms, etc.) but these won't give you any proof that the solution you've found is in fact optimal. – Brian Borchers Jul 22 '13 at 14:08
• If you don't need a global optimum and can live with a local optimum given a notion of neighborhood, you can most certainly solve in 500 "directions" using tree/"line" searches and the like even if $f$ is non-linear. You can even combine a stochastic search with a deterministic local search. – Deathbreath Jul 29 '13 at 20:06
You have what is called an integer optimization problem. Like Brian already mentioned, there are methods that use continuations of your objective function to all of ${\mathbb R}^n$ as part of the algorithm, but ultimately you will have to deal with the integer nature of your problem.