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

Question

Hi

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

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

Answer 2

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?

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

What you are generally looking for is called an optimisation technique) in mathematics. In general, they apply to real-valued functions, but many can be adapted for integral-valued functions.

In particular, I would recommend looking into non-linear programming and gradient descent. Both would seem quite suitable for your application.

If you could perhaps provide any more details, I might be able to suggest somethign a little more specific.

Answer 5

Jon Skeet's answer is correct. You really do need information about f and it's derivatives even if f is everywhere continuous.

The easiest way to appreciate the difficulties of what you ask(minimization of f at integer values only) is just to think about an f: R->R (f is a real valued function of the reals) of one variable that makes large excursions between individual integers. You can easily construct such a function so that there is NO correllation between the local minimums on the real line and the minimums at the integers as well as having no relationship to the first derivative.

For an arbitrary function I see no way except brute force.

Answer 6

Sorry the formatting was so bad previously. Here's an example of the error function

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 7

So let's look at your problem in math-speak. This is all assuming I understand your problem fully. Feel free to correct me if I am mistaken.

we want to minimize the following:

\sqrt((a-a_desired)^2 + (b-b_desired)^2 + (c-c_desired)^2)

or in other notation ||Pos(x - x_desired)||_2

where x = (a,b,c) and Pos(y) = max(y, 0) means we want the "positive part"(this accounts for your if statements). Finally, we wish to restrict ourself to solutions where x is integer valued.

Unlike the above posters, I don't think genetic algorithms are what you want at all.
In fact, I think the solution is much easier (assuming I am understanding your problem).

1) Run any optimization routine on the function above. THis will give you the solution x^* = (a^*, b^*,c^*). As this function is increasing with respect to the variables, the best integer solution you can hope for is (ceil(a^*),ceil(b^*),ceil(c^*)).

Now you say that your function is possibly hard to evaluate. There exist tools for this which are not based on heuristics. The go under the name Derivative-Free Optimization. People use these tools to optimize objective based on simulations (I have even heard of a case where the objective function is based on crop crowing yields!)

Each of these methods have different properties, but in general they attempt to minimize not only the objective, but the number of objective function evaluations.