Minimization of f(x,y) where x and y are integers

Question

I was wondering if anyone had any suggestions for minimizing a function, f(x,y), where x and y are integers. I have researched lots of minimization and optimization techniques, like BFGS and others out of GSL, and things out of Numerical Recipes. So far, I have tried implenting a couple of different schemes. The first works by picking the direction of largest descent f(x+1,y),f(x-1,y),f(x,y+1),f(x,y-1), and follow that direction with line minimization. I have also tried using a downhill simplex (Nelder-Mead) method. Both methods get stuck far away from a minimum. They both appear to work on simpler functions, like finding the minimum of a paraboloid, but I think that both, and especially the former, are designed for functions where x and y are real-valued (doubles). One more problem is that I need to call f(x,y) as few times as possible. It talks to external hardware, and takes a couple of seconds for each call. Any ideas for this would be greatly appreciated.

Here's an example of the error function. Sorry I didn't post this before. This function takes a couple of seconds to evaluate. Also, the information we query from the device does not add to the error if it is below our desired value, only if it is above

double Error(x,y)
{
  SetDeviceParams(x,y);
  double a = QueryParamA();
  double b = QueryParamB();
  double c = QueryParamC();
  double _fReturnable = 0;
  if(a>=A_desired)
  {
    _fReturnable+=(A_desired-a)*(A_desired-a);
  }
  if(b>=B_desired)
  {
    _fReturnable+=(B_desired-b)*(B_desired-b);
  }
  if(c>=C_desired)
  {
    _fReturnable+=(C_desired-c)*(C_desired-c);
  }
  return Math.sqrt(_fReturnable)
}

Answer 1

There are many, many solutions here. In fact, there are entire books and academic disciplines based on the subject. I am reading an excellent one right now: How to Solve It: Modern Heuristics.

There is no one solution that is correct - different solutions have different advantages based on specific knowledge of your function. It has even been proven that there is no one heuristic that performs the best at all optimization tasks.

If you know that your function is quadratic, you can use Newton-Gauss to find the minimum in one step. A genetic algorithm can be a great general-purpose tool, or you can try simulated annealing, which is less complicated.

Answer 2

Have you looked at genetic algorithms? They are very, very good at finding minimums and maximums, while avoiding local minimum/maximums.

Answer 3

How do you define f(x,y) ? Minimisation is a hard problem, depending on the complexity of your function.

Genetic Algorithms could be a good candidate.

Resources:

Genetic Algorithms in Search, Optimization, and Machine Learning

Implementing a Genetic Algorithms in C#

Simple C# GA

Answer 4

If it's an arbitrary function, there's no neat way of doing this.

Suppose we have a function defined as:

f(x, y) = 0 for x==100, y==100
          100 otherwise

How could any algorithm realistically find (100, 100) as the minimum? It could be any possible combination of values.

Do you know anything about the function you're testing?