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.
我需要最小化2D函数f（x，y）。我已经使用布伦特方法进行一维最小化（类似于二分搜索找到一个根。）我认为一个2D版本将是一个非常简单，常见的问题，会有很多好的算法和库，但我还没有找到任何。我正在考虑使用Numerical Recipes中的Downhill Simplex，但我认为对于2D或者一个方便的库来说可能更容易。
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.
我实际上试图找到一条线，最小化两个1D函数之间的点，AKA的bitangent。一维功能通常看起来像抛物线，它们在某些时候交叉。交叉点使得点的X最小化，并且我想找到一条与抛物线相切的线，该线在该X处使Y最小化。
So, I really am minimizing g( f1(x1), f2(x2) ).
所以，我真的最小化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.
不幸的是，我没有关于f1（）和f2（）的更多信息。用户选择或甚至提供这些功能。如果用户提供数据，我将函数作为一组点。我可以进行插值以在线上的任何点获得非常好的数值导数，但这就是它。以前的开发人员认为最小化是找到比特的最常用方法。我还在试图弄清楚他是否正确。
3 个解决方案
#1
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).
我知道你想最小化g（f1（x），f2（y））= h（x，y）。 Downhill Simplex可能是您问题的一个很好的解决方案，因为如果您有NR，它可以直接实施。另一种可能的方法可能是Broyden的方法。但是，既然你有衍生品，你也可以使用算法来展示这些信息。对于例如共轭梯度方法在NR（或至少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).
如果你可以提供grad（h）非常简单，那就是grad（h）[1]取决于一个而grad（h）[2]在另一个变量上，它可能最容易解决为grad（h） = 0并检查它是否是最小值。即使梯度不那么简单，您也可以手动解决问题，并提供一个通用公式，如果f1和f2遵循某种模式（例如，如果它们只是参数不同）。
#2
1
Conjugate gradient minimization will probably do.
共轭梯度最小化可能会做。
But your problem can also be formulated as a system of two equations in two unknowns instead.
但是你的问题也可以表示为两个未知数的两个方程组。
You know the curves and their slopes, so for a given X1 you can find the ordinate Z1(X1) where the tangent to curve 1 intersects the vertical through X. And similarly Z2(X2). At the same time consider the ordinate of the intersection between the vertical and the line through the two tangency points, Z(X1, X2).
您知道曲线及其斜率，因此对于给定的X1，您可以找到纵坐标Z1（X1），其中曲线1的切线与垂直穿过X相交。类似于Z2（X2）。同时考虑垂直线与两条相切点Z（X1，X2）之间的交点的纵坐标。
Z1(X1) = Y1(X1) + Y1'(X1).(X1 - X)
Z2(X2) = Y2(X2) + Y2'(X2).(X2 - X)
Z(X1, X2) = ((X1 - X).Y2(X2) - (X2 - X).Y1(X1)) / (X1 - X2)
You now have to solve Z1(X1) = Z2(X2) = Z(X1, X2), possibly using the same method that you used to find the value of X.
您现在必须使用与查找X值相同的方法求解Z1（X1）= Z2（X2）= Z（X1，X2）。
#3
1
The Gnu Scientific Library has the minimization functions I need, so I'm integrating it. The answers provided were quite good, but they didn't quite turn out to be the best solution in my case. Largely because I didn't state the problem clearly enough.
Gnu科学图书馆具有我需要的最小化功能，所以我正在整合它。提供的答案非常好，但在我的案例中，它们并不是最好的解决方案。很大程度上是因为我没有明确说明问题。
#1
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).
我知道你想最小化g（f1（x），f2（y））= h（x，y）。 Downhill Simplex可能是您问题的一个很好的解决方案，因为如果您有NR，它可以直接实施。另一种可能的方法可能是Broyden的方法。但是，既然你有衍生品，你也可以使用算法来展示这些信息。对于例如共轭梯度方法在NR（或至少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).
如果你可以提供grad（h）非常简单，那就是grad（h）[1]取决于一个而grad（h）[2]在另一个变量上，它可能最容易解决为grad（h） = 0并检查它是否是最小值。即使梯度不那么简单，您也可以手动解决问题，并提供一个通用公式，如果f1和f2遵循某种模式（例如，如果它们只是参数不同）。
#2
1
Conjugate gradient minimization will probably do.
共轭梯度最小化可能会做。
But your problem can also be formulated as a system of two equations in two unknowns instead.
但是你的问题也可以表示为两个未知数的两个方程组。
You know the curves and their slopes, so for a given X1 you can find the ordinate Z1(X1) where the tangent to curve 1 intersects the vertical through X. And similarly Z2(X2). At the same time consider the ordinate of the intersection between the vertical and the line through the two tangency points, Z(X1, X2).
您知道曲线及其斜率，因此对于给定的X1，您可以找到纵坐标Z1（X1），其中曲线1的切线与垂直穿过X相交。类似于Z2（X2）。同时考虑垂直线与两条相切点Z（X1，X2）之间的交点的纵坐标。
Z1(X1) = Y1(X1) + Y1'(X1).(X1 - X)
Z2(X2) = Y2(X2) + Y2'(X2).(X2 - X)
Z(X1, X2) = ((X1 - X).Y2(X2) - (X2 - X).Y1(X1)) / (X1 - X2)
You now have to solve Z1(X1) = Z2(X2) = Z(X1, X2), possibly using the same method that you used to find the value of X.
您现在必须使用与查找X值相同的方法求解Z1（X1）= Z2（X2）= Z（X1，X2）。
#3
1
The Gnu Scientific Library has the minimization functions I need, so I'm integrating it. The answers provided were quite good, but they didn't quite turn out to be the best solution in my case. Largely because I didn't state the problem clearly enough.
Gnu科学图书馆具有我需要的最小化功能，所以我正在整合它。提供的答案非常好，但在我的案例中，它们并不是最好的解决方案。很大程度上是因为我没有明确说明问题。