2D Function Minimization Algorithm or C/C++ library

Question

I need to minimize a 2D function f(x,y). I already have 1-D minimization using Brent's Method (similar to bisectional search for finding a root.) I thought a 2D version would be a pretty straightforward, common problem that would have lots of good algorithms and libraries, but I haven't found any. I'm thinking of just using Downhill Simplex from Numerical Recipes, but I thought there might be an easier one for just 2D, or a handy library.

For the interested, here are some more details:

I am actually trying to find a line that minimizes a point between two 1D functions, AKA the bitangent. The 1D functions generally look like parabolas, and they cross at some point. The crossing point gives the X of the point to minimize, and I want to find a line that tangents the parabolas that minimizes Y at that X.

So, I really am minimizing g( f1(x1), f2(x2) ).

Unfortunately, I don't have any more information about f1() and f2(). The functions are selected, or even provided, by the user. If the user provides the data, I get the functions as a set of points. I can do interpolation to get a pretty good numerical derivative at any point on the line, but that's about it. The previous developer thought minimization was the most general way to find the bitangent. I'm still trying to figure out if he was correct.

Answer 1

I understand you want to minimize g(f1(x),f2(y)) = h(x,y). Downhill Simplex might be a good solution to your problem, since it's straightforward to implement if you have NR. Another possible method may be Broyden's one. However, since you have the derivatives, you could use algorithms expoiting that information too. For e.g. Conjugate Gradient method there is a implementation in NR (or at least NR3).

In case you can provide grad(h) to be really simple, that is grad(h)[1] depending on one and grad(h)[2] on the other variable, it may be easiest to solve for grad(h) = 0 and check if it's a minimum. Even if the gradient isn't that simple you might be able to solve the problem by hand and provide a general formula which does the job if f1 and f2 follow a certain pattern (e.g. if they only differ concerning parameters).