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$
  • $\begingroup$ How do you define a derivative of a function with discrete domain? $\endgroup$ – Guido Kanschat Jul 21 '13 at 14:44
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$
  • $\begingroup$ Is branch and bound suitable for problems where $n > 500$ ? $\endgroup$ – user92382 Jul 22 '13 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$ – Brian Borchers Jul 22 '13 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$ – Deathbreath Jul 29 '13 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$
  • $\begingroup$ Thanks. If it was to name a textbook, which one would you recommend? $\endgroup$ – user92382 Jul 21 '13 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$ – Wolfgang Bangerth Jul 22 '13 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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