4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ How do you define a derivative of a function with discrete domain? $\endgroup$ Jul 21, 2013 at 14:44

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Is branch and bound suitable for problems where $n > 500$ ? $\endgroup$
    – user92382
    Jul 22, 2013 at 5:18
  • $\begingroup$ 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. $\endgroup$ Jul 22, 2013 at 14:08
  • $\begingroup$ 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. $\endgroup$ Jul 29, 2013 at 20:06
2
$\begingroup$

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.

There are many text books on this topic. Find one in your local library to get the basics of solution algorithms for the kind of problem you are considering.

$\endgroup$
2
  • $\begingroup$ Thanks. If it was to name a textbook, which one would you recommend? $\endgroup$
    – user92382
    Jul 21, 2013 at 20:24
  • $\begingroup$ I've used D. Bertsimas and J. N. Tsitsiklis: Introduction to linear optimization, 1997, Athena Scientific, before. It has a chapter on integer optimization. But I'm not an expert -- there are certainly books exclusively devoted to the subject. As I said, see what you library's catalog has to offer under "integer optimization". $\endgroup$ Jul 22, 2013 at 0:47

Your Answer

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

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